The lectures, especially the later ones, have, to some extent, been
based on lecture
notes developed by Dave Mount.
Copies of slides used for the lectures will be posted before the lectures
(pointers at the schedule below).
The slides are usually given in Postscript (ps) 4-to-a-page
Postscript (4ps) and in Portable Document Format (pdf), although a few are in
Word (doc) format.
Cancellation of face-to-face lectures: Special Instructions
April 12, 2003: As broadcast by email, due to the SARS virus, we will be cancelling face-to-face lectures for the rest of the semester (more details). Instead, you are responsible for learning the material on your own from the lecture notes below and the given reading assignments. Pleas email any questions to me at golin@cs.ust.hk; I will keep a running log of all questions asked and post the ones of general interest and the answers to this site.
For material taught prior to April 12, 2003 you are responsible for everything taught in class, regardless of whether it appears in the class notes or not. For material after April 12, 2003 (in green) you are only responsible for what is in the posted notes on the web site and the assigned readings (CLRS is the class textbook; Introduction to Algorithms, second edition, by Cormen, Leiserson, Rivest and Stein).
The lecture dates given for classes after April 12, 2003 are the days by which you are recommended to have read the stated material. The material in the final two assignments will assume that you are following these recommendations.
| Lecture | Date | Topic | Slides | Readings | Other |
| 01 | 04/02/03 | Introduction | PS 4PS PDF Revised 05/02/03 | Insertion-Sort Analysis PDF | |
| 06/02/03 | Extra Credit Answer | ||||
| 02 | 11/02/03 | Maximum Contiguous Subarray | PS 4PS PDF | ||
| 03 | 13/02/03 | More Divide&Conquer Polynomial Multiplication | PS 4PS PDF | ||
| 04 | 18/02/03 | Even More Divide&Conquer Linear Time Selection | PS PDF | Selection Example | |
| 20/02/03 | |||||
| 25/02/03 | |||||
| 05 | 27/02/03 | Introduction to Graphs | PS 4PS PDF | ||
| 06 | 04/03/03 | Breadth First Search | PS 4PS PDF | ||
| 07 | 06/03/03 | Depth First Search | PS 4PS PDF | ||
| 08 | 11/03/03 | DFS & Topological Sort | PS 4PS PDF | ||
| 09 | 13/03/03 | Dijkstra's algorithm | PS 4PS PDF | ||
| 10 | 18/03/03 | MSTs and Prim's algorithm | PS 4PS PDF | Prim vs. Dijkstra | |
| 11 | 21/03/03 | Kruskal's algorithm | PS 4PS PDF | Union Find | |
| 25/03/03 | |||||
| 12 | 27/03/03 | Dynamic Programming: The 0/1 Knapsack Problem | PS PDF | ||
| 13 | 15/04/03 | Chain Matrix Multiplication | PS 4PS PDF Revised 17/04/03 | CLRS Section 15.2 | DP: Extra Credit Problem |
| 14 | 17/04/03 | All-Pairs Shortest Paths | PS PDF Revised 01/05/03 | CLRS Sect. 25.1 | |
| 15 | The Floyd-Warshall Algorithm | PS 4PS PDF | CLRS Sect. 25.2 | ||
| 16 | 24/04/03 | Greedy Algorithms | DOC PDF | CLRS Sect. 16.2 | |
| 17 | Huffman Encoding | PS PDF | CLRS Sect. 16.3 | ||
| 18 | 29/04/04 | Complexity Classes:P & NP | PS 4PS PDF Revised 01/05/03 | CLRS Chapter 34: pp 966-982 | |
| 19 | 06/05/03 | NP Completeness 1 | PS 4PS PDF Revised 25/05/03 | CLRS Chapter 34: pp. 984-986 & pp.995-1007 | |
| 20 | 13/05/03 | NP Completeness 2 | PS 4PS PDF | CLRS Chapter 34: pp. 1008-1013 | |
| 21 | 15/05/03 | Heuristics and Approximation | No Notes | CLRS Chapter 35 (Will not be on exam) |
Return to COMP271 Home page