Algorithms, Fall 2011
http://cc.ee.ntu.edu.tw/~ywchang/Courses/Alg/alg.html
ANNOUNCEMENTS
TEXTBOOK AND REFERENCES
-
Cormen, Leiserson, Rivest, and Stein,
Introduction to Algorithms, 3rd Ed., McGraw Hill/The MIT Press, 2009.
- 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 ASSISTANT
- Shao-Yun Fang (¤èÊo¤ª): E-mail Shao-Yun at yuko703@eda.ee.ntu.edu.tw.
- Office: BL-406; Tel: 23635251 # 6406.
- Office Hours: 12:20-1:20pm Tuesdays.
Grading Policy
- Six homework assignments (+ in-class quizzes to be held on the due dates): 30%
- Three mini programming assignments: 20% (all submissions will be checked for duplication; those with
>= 50% similarity will be penalized)
- Two in-class tests: one midterm on November 9: 20% + final exam on January 11: 30%
- Bonus for class participation
HANDOUTS
- Handout #1 (Syllabus; Sept. 14, 2011)
- Handout #2 (Homework #1; Sept. 21, 2011)
- Handout #3 (Programming Assignment #1; Oct. 5, 2011)
- Handout #4 (Quiz #1; Oct. 5, 2011)
- Handout #5 (Sample Solutions to Homework #1; Oct. 18, 2011)
- Handout #6 (Sample Solutions to Quiz #1; Oct. 18, 2011)
- Handout #7 (Homework #2; Oct. 23, 2011)
- Handout #8 (Practice Midterm; Nov. 1, 2011)
- Handout #9 (Sample Solutions to Homework #2; Nov. 6, 2011)
- Handout #10 (Midterm Exam; Nov. 9, 2011)
- Handout #11 (Programming Assignment #2; Nov. 15, 2011)
- Handout #12 (Homework #3; Nov. 30, 2011)
- Handout #13 (Quiz #2; Dec. 14, 2011)
- Handout #14 (Homework #4; Dec. 21, 2011)
- Handout #15 (Sample Solutions to Homework #3; Jan. 2, 2012)
- Handout #16 (Sample Solutions to Quiz #2; Jan. 2, 2012)
- Handout #17 (Homework #5; Jan. 2, 2012)
- Handout #18 (Programming Assignment #3; Jan. 2, 2012)
- Handout #19 (Practice Exam #2; Jan. 2, 2012)
- Handout #20 (Richard Karp's Turing Award Lecture on NP-completeness; Jan. 2, 2012)
- Handout #21 (Quiz #3; Jan. 4, 2012)
- Handout #22 (Sample Solutions to Homework #4; Jan. 6, 2012)
- Handout #23 (Sample Solutions to Homework #5; Jan. 6, 2012)
- Handout #24 (Sample Solutions to Quiz #3; Jan. 10, 2012)
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 (4 hrs)
- Dynamic programming, greedy algorithms, amortized analysis (11 hrs)
- Graph algorithms: graph representations, searching, minimum spanning tree, single-source and all-pair shortest paths, network flow, matching (13 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. 14, 2011)
- Lecture Note #2 [One Page/Slide Format] (Sorting and order statistics; Sept. 27, 2011)
- Lecture Note #3 [One Page/Slide Format] (Tree data structures; Oct. 12, 2011)
- Lecture Note #4 [One Page/Slide Format] (Dynamic programming; Oct. 24, 2011)
- Lecture Note #5 [One Page/Slide Format] (Greedy algorithms; Nov. 1, 2011)
- Lecture Note #6 [One Page/Slide Format] (Amortized analysis; Nov. 15, 2011)
- Lecture Note #7 [One Page/Slide Format] (Disjoint sets; Nov. 15, 2011)
- Lecture Note #8 [One Page/Slide Format] (Graph algorithms; Nov. 29, 2011)
- Lecture Note #9 [One Page/Slide Format] (Coping with NP-completeness; Dec. 21, 2011)
OTHER INFORMATION
- "The Last Lecture" given by Prof. Randy Pausch of CMU on Sep. 18, 2007 (See http://www.TheLastLecture.com. for more detail.)
- 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 othe
