Algorithms, Fall 2009
http://cc.ee.ntu.edu.tw/~ywchang/Courses/Alg/alg.html
ANNOUNCEMENTS
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 (張耀文)
TEACHING ASSISTANTS
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 5: 18% + final exam on January 14: 32%
- Bonus for class participation
HANDOUTS
- Handout #1 (Syllabus; Sept. 17, 2009)
- Handout #2 (Homework #1; Sept. 24, 2009) (Correction: 4. Problem 2-3: Page 39; instead of Page 38)
- Handout #3 (Programming Assignment #1; Oct. 1, 2009)
- Handout #4 (Extended Homework #1; Oct. 8, 2009)
- Handout #5 (Sample Solutions to Homework #1; Oct. 14, 2009)
- Handout #6 (Sample Solutions to Extended Homework #1; Oct. 14, 2009)
- Handout #7 (Homework #2; Oct. 15, 2009)
- Handout #8 (Practice Midterm #1; Oct. 22, 2009) Please ignore Problem 6 since it is a greedy algorithm problem which is out of scope for this midterm.
- Handout #9 (Extended Homework #2; Oct. 29, 2009)
- Handout #10 (Sample Solutions to Homework #2; Oct. 31, 2009)
- Handout #11 (Sample Solutions to Extended Homework #2; Oct. 31, 2009)
- Handout #12 (Midterm #1; Nov. 5, 2009)
- Handout #13 (Programming Assignment #2; Nov. 12, 2009)
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. 17, 2009)
- Lecture Note #2 [One Page/Slide Format] (Sorting and order statistics; Sept. 24, 2009)
- Lecture Note #3 [One Page/Slide Format] (Data structures; Oct. 7, 2009)
- Lecture Note #4 [One Page/Slide Format] (Dynamic programming; Oct. 21, 2009)
- Lecture Note #5 [One Page/Slide Format] (Greedy algorithms; Oct. 28, 2009)
- Lecture Note #6 [One Page/Slide Format] (Amortized analysis; Nov. 12, 2009)
- Lecture Note #7 [One Page/Slide Format] (Disjoint sets; Nov. 18, 2009)
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 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.
- 2010 IC/CAD Contests
(hosted by the Ministry of Education).
- 2005-2007 IC/CAD Contests
(hosted by the Ministry of Education).
- 2002-2004 IC/CAD Contests
(hosted by the Ministry of Education).
- 2000--2001 IC/CAD Contests
(hosted by the Ministry of Education).
For any questions, send e-mails to ywchang@cc.ee.ntu.edu.tw.
Last modified: September 17, 2008