Announcements |
Always check http://www.cs.ust.hk/~dekai/271/
for up-to-the-minute announcements. 2005.05.11 ASSIGNMENT 3 will be due May 17 at 3pm in 4209 (L19/20) (ps pdf). Please review the PLAGIARISM and COLLABORATION policy below CAREFULLY. 2005.03.31 ASSIGNMENT 2 will be due Apr 19 (ps pdf). Please review the PLAGIARISM and COLLABORATION policy below CAREFULLY. 2005.03.30 MIDTERM is on Apr 12, 18:30-20:30. Lecture 1 is in Rm 3008, and Lecture 2 is in Rm 3007. There will be no other lecture that day. 2005.03.03 ASSIGNMENT 1 will be due Mar 17 (ps pdf). Please review the PLAGIARISM and COLLABORATION policy below CAREFULLY. |
Policies |
All information for tutorials is at http://course.cs.ust.hk/comp271/tutorials/.
There will be one midterm worth 350 points, and one final exam worth 450 points.
There will be 3 assignments, which together will account for a total of 200 points.
If you achieve | 900 points | you will receive no less than a | A | grade. |
800 points | B | |||
700 points | C | |||
600 points | D |
Theme | Date | Wk | Event | Notes | Chapters | Assignments |
Introduction and Review | Feb 01 | 1 | lec | Introduction (ps pdf) | 1.1-4.2 | |
Feb 03 | lec | Review (slides reference) | ||||
Divide and Conquer | Feb 08 | 2 | lec | Maximum contiguous subarray problem (ps pdf) | ||
Feb 10 | Lunar New Year | |||||
Feb 15 | 3 | lec | Polynomial multiplication (ps pdf) | |||
Feb 17 | lec | Randomized selection and randomized quicksort (ps pdf) | 7 | |||
Feb 22 | 4 | lec | Deterministic linear-time selection (ps pdf) | 9.2, 9.3 | ||
Graph Algorithms | Feb 24 | lec | Depth-first search and its applications (ps pdf) | 22.3 | ||
Mar 01 | 5 | lec | Depth-first search and its applications (cont) | |||
Mar 03 | lec | Minimum spanning tree and Prim's algorithm (ps pdf) | 23 | |||
Mar 08 | 6 | lec | Minimum spanning tree and Prim's algorithm (cont) | |||
Mar 10 | lec | Kruskal's algorithm (ps pdf) | 23 | |||
Mar 15 | 7 | lec | Disjoint set union and find (ps pdf) | 21.3 | ||
Mar 17 | lec | Dijktra's algorithm (ps pdf) | 24.3 | A1 due (ps pdf) | ||
Dynamic Programming | Mar 22 | 8 | lec | 0-1 Knapsack (ps pdf) | ||
Mar 24 | lec | 0-1 Knapsack (cont) | ||||
Mar 29 | 8 | lec | Matrix chain multiplication (ps pdf written notes (jpeg) 1 2 3 4) | 15.2, 15.3 | ||
Mar 31 | lec | All-pairs shortest paths (ps pdf written notes (jpeg) 1 2 3 4 5 6 7 8) | 25.1, 25.2 | |||
Apr 5 | 9 | Ching Ming Festival | ||||
Apr 7 | lec | All-pairs shortest paths (cont) | ||||
Apr 12 | 10 | exam | Midterm (18:30-20:30, Rm3008 for L1, Rm3007 for L2) | |||
Greedy Algorithms | Apr 14 | lec | Fractional Knapsack (ps pdf written notes (jpeg) 1 2 3 4) | 16.2 | ||
Apr 19 | 11 | lec | Huffman coding (ps pdf written notes ps pdf) | 16.3 | A2 due (ps pdf) | |
Apr 21 | lec | Huffman coding (cont) | ||||
More Algorithms | Apr 26 | 12 | lec | String matching (ps pdf written notes ps pdf) | 32.1, 32.4 | |
Apr 28 | lec | String matching (cont) | ||||
NP-completeness | May 03 | 13 | lec | Introduction to NP (ps pdf) | 34.1, 34.2 | |
May 05 | lec | Introduction to NP (cont) | ||||
May 10 | 14 | lec | Introduction to NP (cont) | |||
May 12 | lec | Polynomial time reduction (ps pdf written notes (jpeg) 1 2 3 4) | 34.3, 34.5 | |||
May 17 | 15 | (15:00, Rm 4209, Lifts 19/20) | A3 due (ps pdf) | |||
May 21 | exam | Final (08:30-11:30, LG4204) |