|
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
“有人天生喜欢“遍历”，踏遍千山万水，遍享万种风情......
有人一生“贪婪”，眼界不宽，及时行乐；
有人注定适用“穷搜”，辛辛苦苦勤勤恳恳一辈子，付出很多，收获有限；
有人善用“时空权衡”，用最少的时间办最多的事情，的确精明；
有人会“分治”，再多的难题也能迎刃而解；
有人常“回溯”，错的太多，后悔太多；
有的人压根没有算法，于是盲目生活，盲目做事，最后所获无几；……”
--- 邹恒明 《算法之道》
Oct 14. Here are the slides of the first exercise class, and the solutions of HW1-4.
