News | Info | Lectures | homework | Recommended books | Links
Weeks | Lectures | Topics | Readings | Dates |
#1 | Lecture 1
slides1 , slides2 | Introduction | [0] ch 4.3, [1] ch 5.1.4, [2] ch 21, [3] ch 1.5 | Sep. 13 (Tuesday) |
Lecture 2 slides | Fundamentals | [0] ch 1.8-1.14, [1] ch 0, [2] ch 3, [3] ch 1.4 | Sep. 16 (Friday) | |
#2 | Lecture 3 slides | Induction&Sort(I) | [0] ch 5, [1] ch 1 | Sep. 20 (Tuesday) |
#3 | Lecture 4 slides , Demo Partition | Divide and Conquer | [0] ch 1.5, 1.7, 5.2, 5.3, 6.3, 6.6 [1] ch 2.3, 2.4, [2] ch 6, 7, 8, [3] ch 2 | Sep. 27 (Tuesday) |
Lecture 5 slides , Demo Heapsort | Heapsort | [0] ch 5.2, 5.3 [1] ch 2.3, 2.4, [2] ch 6, 7, 8, [3] ch 2 | Sep. 30 (Friday) | |
#4 | Holiday | Oct. 4 (Tuesday) | ||
#5 | Lecture 6 slides , Demo DFS , Demo BFS Demo Topological sort Demo KosarajuSharir | Graph Traversal | [0] ch 9 [1] ch 3 [2] ch 22 [3] ch 4 | Oct. 11 (Tuesday), Oct. 14 (Friday) |
#6 | Lecture 7 slides , Demo BellmanFord Demo Dijkstra, Demo FloydWahall | Shortest paths | [0] ch 4.2, 8.2, [1] ch 4, [2] ch 24, [3] ch 4 | Oct. 18 (Tuesday), Oct. 25 (Tuesday) |
#7 | Lecture 8 slides | Greedy approach | [0] ch 8, [1] ch 5, [2] ch 16 | Oct. 28 (Friday) |
#8, #9 | Lecture 9 slides | Dynamic programming | [0] ch 7, [1] ch 6, [2] ch 15 | Nov. 1 (Tuesday), Nov. 8 (Tuesday) |
#10 | Lecture 10 slides | Network flow | [0] ch 16,17, [1] ch 6, [2] ch 26 | Nov. 11 (Friday), Nov. 15 (Tuesday) |
#11 | Lecture 12 | String | Nov. 22 (Tuesday) | |
Lecture 13 | Data compression | Nov. 25 (Friday) | ||
#12 | Lecture 14 | P and NP | [0] ch 10, [1] ch 8, [2] ch 34 | Nov. 29 (Tuesday), Dec. 6 (Tuesday) |
#13 | Lecture 15 | Lower bounds | [0] ch 12, [2] ch 8.1 | Dec. 9 (Friday) |
#14 | Lecture 15 | Approximation algorithms | [0] ch 15, [1]ch 9.2, [2] ch 35 | Dec. 13 (Tuesday), Dec. 20 (Tuesday) |
#15 | Lecture 16 | Computational geometry | [0] ch 18, [2] ch 33 | Dec. 23 (Friday) |
#16 | Wrap up | Review | Dec. 27 (Tuesday) |
[0] M.H. Alsuwaiyel. Algorithms: design techniques and analysis, World Scientific Pub. Co. Inc. 1999.
[1] S. Dasgupta, C. H. Papadimitriou, U. V. Vazirani. Algorithms, 2006
[2] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms, Third edition, 2009
[3] R. Sedgewick, K. Wayne. Algorithms, Fourth edition, 2011
“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”
“有人天生喜欢“遍历”，踏遍千山万水，遍享万种风情......
有人一生“贪婪”，眼界不宽，及时行乐；
有人注定适用“穷搜”，辛辛苦苦勤勤恳恳一辈子，付出很多，收获有限；
有人善用“时空权衡”，用最少的时间办最多的事情，的确精明；
有人会“分治”，再多的难题也能迎刃而解；
有人常“回溯”，错的太多，后悔太多；
有的人压根没有算法，于是盲目生活，盲目做事，最后所获无几；……”
--- 邹恒明 《算法之道》