COT6405: Analysis of Algorithms (Fall 2013)
Instructor: Ning Xie (office ECS 380)
Location: ECS 136
Time: Tuesday and Thursday 12:30 -- 13:45
Office Hours: Tuesday and Thursday 14:00 -- 15:30 or by appointment
TA: Kianoush Gholami, office hours: Wed. 16:00 - 17:00 at ECS 232B
(Disclaimer: All information on this page about the course is tentative and subject to further changes.)
Syllabus:
- Dynamic Programming
- Greedy Algorithms
- Advanced Data Structures
- NP-Completeness
- Divide-and-Conquer (Strassen, FFT)
- Network Flow
Textbook:
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein,
Introduction to Algorithms, Third Edition
(MIT Press, 2009).
Grading: Grading will be based on homework assignments, a midterm, and a final exam.
The midterm and final exam will be in-class, and all students must attend the on campus exam.
Any exceptions must be discussed with the instructor, and approved in advance.
The timing will be determined in a manner that avoids conflicts with other classes.
The tentative scheme for grading is:
- Homeworks 30%
- Midterm Exam 30%
- Final Exam 40%.
Homework Policy:
- Late homework will generally NOT be accepted. If there are extenuating circumstances, you
should make prior arrangements with the instructor.
- You can collaborate on homework problems with other students in the class.
However, you must write up each problem solution by yourself without assistance.
- Homework submissions must be typeset. Handwritten submissions will NOT be accepted. These
must be uploaded to SCIS moodle in PDF format only.
Assignments:
Announcements:
- September 9: Homework 1 is out, due Tuesday September 17.
- September 25: Homework 2 is out, due Wednesday October 2.
- October 1: The due day of Homework 2 is now extended to Friday October 4.
- October 8: Homework 3 is out, due Friday October 18.
- October 10: Midterm exam is scheduled on Tuesday October 22, in class.
- November 7: Homework 4 is out, due Sunday November 17.
- November 7: Final exam is scheduled on Tuesday December 10, 12:00 PM -- 2:00 PM, in ECS 136 (regular classroom).
- November 24: Homework 5 is out, due Monday December 2.
Schedule:
- Lecture 1 (Aug. 27): Introduction, Asymptotics (Section 3.1)
- Lecture 2 (Aug. 29): Dynamic Programming I (Section 15.1)
- Lecture 3 (Sept. 3): Dynamic Programming II (Section 15.2)
- Lecture 4 (Sept. 5): Dynamic Programming III (Section 15.3)
- Lecture 5 (Sept. 10): Dynamic Programming IV (Section 15.4)
- Lecture 6 (Sept. 12): Dynamic Programming V (Longest Increasing Subsequence, Structural DP)
- Lecture 7 (Sept. 17): Greedy Algorithms I (Section 16.1)
- Lecture 8 (Sept. 19): Greedy Algorithms II (Lateness Minimization and Interval Coloring)
- Lecture 9 (Sept. 24): Greedy Algorithms III (Optimal Caching and Huffman Codes, Section 16.3)
- Lecture 10 (Sept. 26): Greedy Algorithms IV (Huffman Codes and Dijkstra's Algorithm, Section 16.3 and Section 24.3)
- Lecture 11 (Oct. 1): Amortized Analysis I (Bellman-Ford Section 24.1, Aggregate Analysis, Section 17.1)
- Lecture 12 (Oct. 3): Amortized Analysis II (Section 17.1, 17.2)
- Lecture 13 (Oct. 8): Amortized Analysis III (Section 17.3, 17.4)
- Lecture 14 (Oct. 10): Fibonacci Heaps I (Section 19.1, 19.2)
- Lecture 15 (Oct. 15): Fibonacci Heaps II (Section 19.2, 19.3)
- Lecture 16 (Oct. 17): Fibonacci Heaps III (Section 19.4)
- Lecture 17 (Oct. 22): Midterm Exam
- Lecture 18 (Oct. 24): B-trees I (Section 18.1)
- Lecture 19 (Oct. 29): Midterm Review
- Lecture 20 (Oct. 31): B-trees II (Section 18.2, 18.3)
- Lecture 21 (Nov. 5): NP-completeness I (Section 34.1)
- Lecture 22 (Nov. 7): NP-completeness II (Section 34.2, 34.3)
- Lecture 23 (Nov. 12): NP-completeness III (Section 34.3, 34.4)
- Lecture 24 (Nov. 14): NP-completeness IV (Section 34.5)
- Lecture 25 (Nov. 19): Strassen's algorithm (Section 4.2)
- Lecture 26 (Nov. 21): Polynomial representations (Section 30.1)
- Lecture 27 (Nov. 26): Fast Fourier Transforms (Section 30.2)
- Lecture 28 (Dec. 3): Maximum Flow I (Section 26.1, 26.2)
- Lecture 29 (Dec. 5): Maximum Flow II (Section 26.2, 26.3)