Algorithms, Fall 2007
http://cc.ee.ntu.edu.tw/~ywchang/Courses/Alg/alg.html
ANNOUNCEMENTS - Handout #5 (Homework #2; Oct. 19, 2007)
- Handout #4 (Programming Assignment #1; Oct. 19, 2007)
- Click here to submit your programming assignment #1.
- Click here to retrieve the on-line resource for this assignment.
- Please notice that the TA has office hours 12-1pm on Tuesdays (in BL 406). You are welcome to discuss with the TA for homework assignments and other matters.
- We will have a make-up class at 2:20pm on December 15 for the December 12 one.
TEXTBOOK AND REFERENCES
Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, 2nd Ed., McGraw Hill/The MIT Press, 2001. - Bug reports of the text.
- References
- M. Garey and D. Johnson, Computers and Intractability: A guide to the theory of NP-completeness, Freeman, 1979.
- A Web compendium of known NP-complete problems so far.
INSTRUCTOR: YAO-WEN CHANG (±iÄ£¤å)
TEACHING ASSISTANTS
Grading Policy
- Five homework assignments (+ in-class quizzes to be held on the due dates): 30%
- Three mini programming assignments: 20%
- Two in-class tests: one midterm on November 7: 20% + final exam on January 16: 30%
- Bonus for class participation
HANDOUTS
- Handout #1 (Syllabus; Sept. 19, 2007)
- Handout #2 (Homework #1; Sept. 26, 2007)
- Handout #3 (Quiz #1; Oct. 17, 2007)
- Handout #4 (Programming Assignment #1; Oct. 19, 2007)
- Click here to submit your programming assignment #1.
- Click here to retrieve the on-line resource for this assignment.
- Handout #5 (Homework #2; Oct. 19, 2007)
- Handout #6 (Sample Solutions to Homework #1; Oct. 19, 2007)
- Handout #7 (Sample Solutions to Quiz #1; Oct. 19, 2007)
LECTURE NOTES
- Schedule:
- Mathematical foundations + administrative matters (6 hrs)
- Sorting and order statistics (5 hrs)
- Data structures: heap, binary search trees, RB trees, disjoint sets (5 hrs)
- Dynamic programming, greedy algorithms, amortized analysis (12 hrs)
- Graph algorithms: graph representations, searching, minimum spanning tree, single-source and all-pair shortest paths, network flow, matching (14 hrs)
- NP-completeness (5 hrs)
- Approximation algorithms (1 hr)
- General-purpose algorithms: Linear programming, as time permits.
- Others: Exams (6 hrs)
- Lecture Notes
- Lecture Note #1 [One Page/Slide Format] (Mathematical foundations; Sept. 19, 2007)
- Lecture Note #2 [One Page/Slide Format] (Sorting and order statistics; Sept. 30, 2007)
- Lecture Note #3 [One Page/Slide Format] (Data structures on trees)
- Lecture Note #4 [One Page/Slide Format] (Dynamic programming)
- Lecture Note #5 [One Page/Slide Format] (Greedy algorithms)
- Lecture Note #6 [One Page/Slide Format] (Amortized analysis)
- Lecture Note #7 [One Page/Slide Format] (Disjoint sets)
- Lecture Note #8 [One Page/Slide Format] (Graph algorithms)
- Lecture Note #9 [One Page/Slide Format] (Coping with NP-completeness)
OTHER INFORMATION
- S. Skiena's The Stony Brook Algorithm Repository contains implementations (in six programming languages) for numerous algorithms.
- The LEDA package consists of numerous implementations for data structures, graph algorithms, etc.
- A very good source on the implementations of graph algorithms: "Leda : A Platform for Combinatorial and Geometric Computing" by Kurt Mehlhorn and Stefan Naher.
- Kirk Pruhs, How to design dynamic programming algorithms sans recursion, SIGACT News, Vol. 29, No. 1, pp. 32-35, March 1998.
- Some pointers to code for max-flow and other network optimization problems is available on the Linear Programming FAQ. See especially Andrew Goldberg's library of programs.
- M. X. Goemans' course notes on linear programming, approximation algorithms, etc.
- A Web compendium of known NP-complete problems so far.
- Steve Seiden's cheat sheet on theoretical computer science consisting of ten pages of commonly used formulas and other useful information for computer scientists.
- Micha Hofri's collection of useful formulas for theoretical computer science.
- Pointer to algorithms related courses on the web.
- The Amazon web site for book information.
- ACM web site.
- ACM SIGACT (Special Interest Group on Algorithms and Computational Theory)
- IEEE web site.
- IEEE Computer Society.
- IEEE Spectrum.
- 2005-2007 IC/CAD Contests (hosted by the Ministery of Education).
- 2002-2004 IC/CAD Contests (hosted by the Ministery of Education).
- 2000--2001 IC/CAD Contests (hosted by the Ministery of Education).
For any questions, send e-mails to ywchang@cc.ee.ntu.edu.tw.
Last modified: September 18, 2007