General Information

Lecturer:

WingKai Hon


wkhon @ cs



Tutors:

Simon, Cindy, HsinPei, Terry


Henry, Rick, Andrew, MinHsin


Check iLMS for details



Meeting Time:


Wed 10101200, Fri 10101100



Announcements

Welcome to the Class!

References
1. Introduction to Algorithms, by Cormen et al.
2. Algorithms in C++, by Sedgewick
3. The Art of Computer Programming, by Knuth

Scoring Method
6 Assignments (0%)
3 Exams (2 * 40% + 1 * 20%)

Total = 100%


Course Materials

Lecture

Topics

Related Files

1

Getting Started

[pdf]

2

Growth of Function

[pdf]

3

Recurrences

[pdf]

4

Heapsort

[pdf]

5

Quicksort

[pdf]

**

Probability and Expectation

[pdf]

6

Sorting in Linear Time

[pdf]

7

Lower Bound on Comparison Sorts

[pdf]

8

Order Statistics

[pdf]

9

Dynamic Programming I (Assembly Line, Memoization)

[pdf]

10

Dynamic Programming II (Matrix Chain Multiplication)

[pdf]

11

Dynamic Programming III (Optimal BST)

[pdf]

12

Dynamic Programming IV (Longest Common Subsequence)

[pdf]

13

Greedy Algorithm

[pdf]

14

Amortized Analysis I (Aggregate Method)

[pdf]

15

Amortized Analysis II (Accounting Method, Potential Method)

[pdf]

16

Amortized Analysis III (Dynamic Table)

[pdf]

17

Binomial Heap

[pdf]

18

Fibonacci Heap I (Insertion, Union, ExtractMin)

[pdf]

19

Fibonacci Heap II (DecreaseKey, Delete, MaxDeg)

[pdf]

20

Disjoint Sets I (Linked List)

[pdf]

21

Disjoint Sets II (Union by Size, Union by Rank, Path Compress)

[pdf]

22

Graph Algorithms I (BFS)

[pdf]

23

Graph Algorithms II (DFS)

[pdf]

24

Graph Algorithms III (Topological Sort)

[pdf]

25

Graph Algorithms IV (Strongly Connected Components)

[pdf]

26

Minimum Spanning Trees

[pdf]

27

SingleSource Shortest Paths

[pdf]

Teaching Plan

1

Basics

Lecture 01 to Lecture 03

2

Sorting & Order Statistics

Lecture 04 to Lecture 08

3

Advanced Design Techniques

Lecture 09 to Lecture 13

4

Advanced Analysis Technique

Lecture 14 to Lecture 16

5

Advanced Data Structures

Lecture 17 to Lecture 21

6

Graph Algorithms

Lecture 22 to Lecture 26

7

Selected Topics

KMP, NPhardness

Last updated: February 12, 2017
