News | Info | Tentative Schedule | Recommended books | Links
| Weeks | Lectures | Topics | Readings | Dates |
| #1 | Lecture 1 ( pdf , key ) | Introduction | [1] ch 1, [2] ch 0 | Sep. 6 (Tuesday) |
| #2 | Lecture 2( pdf , key ) | Preliminaries | [1] ch 2, [2] ch 0, [3] ch 3 | Sep. 13 (Tuesday) |
| Lecture 3( pdf , key ) | Induction | [1] ch 5, [2] ch 1 | Sep. 16 (Friday) | |
| #3 | Lecture 4 ( pdf , key ) | Sorting | [1] ch 1.7, 5.2, [2] ch 2.3, [3] ch 8 | Sep. 20 (Tuesday) |
| #4 | Lecture 5 ( pdf , key ) | Divide-and-conquer (I) | [1] ch 6, [2] ch 2, [3] ch 4,9 | Sep. 27 (Tuesday) |
| Lecture 6 ( pdf , key ) | Divide-and-conquer (II) | [1] ch 6, [2] ch 2, [3] ch 4,9 | Sep. 30 (Friday) | |
| #5 | Recitation 1 | Lecture 1-6 | Oct. 9 (Sunday) | |
| #6 | Lecture 7 ( pdf , key ) | Graph traversal | [1] ch 9, [2] ch 3,4, [3] ch 22 | Oct. 11 (Tuesday) |
| Lecture 8 ( pdf , key ) | Distances and Heap data structure | [1] ch 4.2, 8.2, [2] ch 4, [3] ch 6, 24 | Oct. 14 (Friday) | |
| #7 | Oct. 18 (Tuesday) | |||
| #8 | Lecture 9 ( pdf , key ) | Minimum spanning tree and Disjoint sets | [1] ch 4.3, 8.3, 8.4, [2] ch 5.1, [3] ch 21,23 | Oct 25 (Tuesday) |
| Lecture 10 ( pdf , key ) | Greedy approach | [1] ch 8, [2] ch 5, [3] ch 16 | Oct. 28 (Friday) | |
| #9 | Lecture 11 ( pdf , key ) | Dynamic programming (I) | [1] ch 7, [2] ch 6, [3] ch 15 | Nov. 1 (Tuesday) |
| #10 | Lecture 12 ( pdf , key ) | Dynamic programming (II) | [1] ch 7, [2] ch 6, [3] ch 15 | Nov. 8 (Tuesday) |
| Lecture 13 ( pdf , key ) | Netwrok flow and Bipartite matching | [1] ch 16,17, [2] ch 6, [3] ch 26 | Nov. 11 (Friday) | |
| #11 | Recitation 2 | Lecutre 7-13 | Nov. 15 (Tuesday) | |
| #12 | Lecture 14 ( pdf , key ) | P, NP, reductions, and NPC | [1] ch 10, [2] ch 8, [3] ch 34 | Nov. 22 (Tuesday) |
| Nov. 25 (Friday) | ||||
| #13 | Lecture 15 ( pdf , pptx ) | Backtracking | [1] ch 13, [2] ch 9.1 | Nov. 29 (Tuesday) |
| #14 | Lecture 16 ( pdf , key ) | Randomized algorithms | [1] ch 14, [3] ch 5 | Dec. 6 (Tuesday) |
| Lecture 17 ( pdf , key ) | Approximation algorithms | [1] ch 15, [2]ch 9.2, [3] ch 35 | Dec. 9 (Friday) | |
| #15 | Lecture 18 ( pdf , key ) | Computational geometry | [1] ch 18, [3] ch 33 | Dec. 13 (Tuesday) |
| #16 | Lecture 19 ( pdf , key ) | Lower bounds | [1] ch 12, [3] ch 8.1 | Dec. 20 (Tuesday) |
| Recitation 3 ( pdf , key ) | Lecture 1-19 | Dec. 23 (Friday) |
[1] M.H. Alsuwaiyel. Algorithms: design techniques and analysis, World Scientific Pub. Co. Inc. 1999.
[2] S. Dasgupta, C. H. Papadimitriou, U. V. Vazirani. Algorithms, 2006
[3] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms, Third edition, 2009
“Computer Science is the study of algorithms.” -- Donald E. Knuth
“……This book tells the story of the other intellectual enterprise that is crucially fueling the computer revolution:
efficient algorithms.
It is a fascinating story.
Gather ‘round and listen close…….”
---- Papadimitriou et al. “Algorithms”
“有人天生喜欢“遍历”，踏遍千山万水，遍享万种风情......
有人一生“贪婪”，眼界不宽，及时行乐；
有人注定适用“穷搜”，辛辛苦苦勤勤恳恳一辈子，付出很多，收获有限；
有人善用“时空权衡”，用最少的时间办最多的事情，的确精明；
有人会“分治”，再多的难题也能迎刃而解；
有人常“回溯”，错的太多，后悔太多；
有的人压根没有算法，于是盲目生活，盲目做事，最后所获无几；……”
--- 邹恒明 《算法之道》
Last updated: Dec 22 , 2011