Algorithms, Fall 2016
http://cc.ee.ntu.edu.tw/~ywchang/Courses/Alg/alg.html
(Classroom: BL 112)
ANNOUNCEMENTS
- Grading Information (as of January 31, 2017)
- Handout #28 (Sample Solutions to Midterm #2; Jan. 15, 2017)
- Handout #23 (Sample Solutions to Midterm #1; Dec. 29, 2016)
- Please notice that the TAs (Zhi-Wen and Yen-Chun) offer office hours 12:30-1:30pm on Wednesdays and Thursdays in BL 406. You are welcome to
discuss with the TAs for homework/programming assignments and other matters.
TEXTBOOK AND REFERENCES
- Cormen, Leiserson, Rivest, and Stein,
Introduction to Algorithms, 3rd Ed., McGraw Hill/The MIT Press, 2009.
- Bug reports of the text (3rd Edition):
1st Printing;
2nd Printing;
3rd Printing;
4th Printing.
- 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
- Zhi-Wen Lin (ªL´Ó¤å) : E-mail Zhi-Wen at lzw@eda.ee.ntu.edu.tw.
- Office: BL-406; Tel: 23635251 # 6406.
- Office Hours: 12:30-1:30pm Wednesdays.
- Yen-Chun Liu (¼B«Û§g) : E-mail Yen-Chun at ycliu@eda.ee.ntu.edu.tw.
- Office: BL-406; Tel: 23635251 # 6406.
- Office Hours: 12:30-1:30pm Thursdays.
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 subject to duplication checking; those with
>= 40% similarity will be penalized)
- Two in-class tests: one midterm on November 10: 20% + final exam on January 12: 30%
- Bonus for class participation
HANDOUTS
- Handout #1 (Syllabus; Sept. 22, 2016)
- Handout #2 (Homework #1; Sept. 22, 2016)
- Handout #3 (Programming Assignment #1; Sept. 22, 2016)
- Handout #4 (Homework #2; Oct. 9, 2016)
- Handout #5 (Quiz #1; Oct. 13, 2016)
- Handout #6 (Sample Solutions to Homework #1; Oct. 19, 2016; Revised on Problem 17(a) on Nov. 2, 2016)
- Handout #7 (Sample Solutions to Quiz #1; Oct. 19, 2016)
- Handout #8 (Practice Midterm #1; Nov. 2, 2016)
- Handout #9 (Homework #3; Nov. 2, 2016; New deadline: December 8th, in-class)
- Handout #10 (Quiz #2; Nov. 3, 2016)
- Handout #11 (Programming Assignment #2; Nov. 3, 2016)
- Handout #12 (Sample Solutions to Homework #2; Nov. 4, 2016)
- Handout #13 (Midterm #1; Nov. 10, 2016)
- Handout #14 (Programming Assignment #3; Dec. 5, 2016)
- Handout #15 (Homework #4; Dec. 6, 2016)
- Handout #16 (Quiz #3; Dec. 8, 2016)
- Handout #17 (Sample Solutions to Quiz #2; Dec. 16, 2016)
- Handout #18 (Sample Solutions to Quiz #3; Dec. 20, 2016)
- Handout #19 (Sample Solutions to Homework #3; Dec. 20, 2016)
- Handout #20 (Quiz #4; Dec. 22, 2016)
- Handout #21 (Homework #5; Dec. 22, 2016)
- Handout #22 (Sample Solutions to Quiz #4; Dec. 25, 2016)
- Handout #23 (Sample Solutions to Midterm #1; Dec. 29, 2016)
- Handout #24 (Practice Midterm #2; Jan. 1, 2017)
- Handout #25 (Sample Solutions to Homework #4; Jan. 2, 2017)
- Handout #26 (Sample Solutions to Homework #5; Jan. 10, 2017)
- Handout #27 (Midterm #2; Jan. 12, 2017)
- Handout #28 (Sample Solutions to Midterm #2; Jan. 15, 2017)
LECTURE NOTES
- Schedule (51 hrs in total this semester):
- Mathematical foundations + administrative matters (6 hrs)
- Sorting and order statistics (5 hrs)
- Data structures: heap, binary search trees, RB trees, interval trees, disjoint sets (4 hrs)
- Dynamic programming, greedy algorithms, amortized analysis (9 hrs)
- Graph algorithms: graph representations, searching, minimum spanning tree, single-source and all-pair shortest paths, network flow, matching (14 hrs)
- NP-completeness (6 hrs)
- Approximation algorithms (1 hr)
- General-purpose algorithms: simulated annealing, Linear programming, as time permits.
- Others: Exams (6 hrs)
- Lecture Notes
- Lecture Note #1 [One Page/Slide Format] (Mathematical foundations)
- Lecture Note #2 [One Page/Slide Format] (Sorting and order statistics)
- Lecture Note #3 [One Page/Slide Format] (Tree data structures)
- 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] (Graph algorithms)
- Lecture Note #8 [One Page/Slide Format] (Coping with NP-completeness)
OTHER INFORMATION
- Some interesting sites for algorithms and data structures animation:
- Related interesting papers:
- S. Brin and L. Page, "The Anatomy of a Large-Scale Hypertext Web Search Engine," The 7th Int. Conf. World Wide Web Conference, 1998.
- M. Burrows, ¡§Constrained searching of an Index,¡¨ Patent US6105019 A, 1999.
- D. Gale and L. S. Shapley, "College Admissions and the Stability of Marriage,"
The American Mathematical Monthly, Vol. 69, No. 1, pp. 9-15, Jan., 1962.
- "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.
- Pointer to algorithms related courses on the web.
- ACM web site.
- ACM SIGACT (Special Interest Group on Algorithms and Computational Theory)
- IEEE web site.
- IEEE Computer Society.
- IEEE Council on Electronic Design Automation (CEDA).
- IEEE Spectrum.
For any questions, send e-mails to ywchang@ntu.edu.tw.
Last modified: November 3rd, 2016