COT6405: Analysis of Algorithms (Fall 2015)

Instructor: Ning Xie (office ECS 380)
Location: ECS 145
Time: Tuesday and Thursday 12:30 -- 13:45
Office Hours: Tuesday 17:00 -- 18:00 and Thursday 16:00 -- 17:00, or by appointments
TA: TBA



(Disclaimer: All information on this page about the course is tentative and subject to further changes.)

Syllabus:

• Asymptotics, Recurrence
• Divide-and-Conquer (Strassen, FFT)
• Advanced Data Structures
• Graphs & Graph Algorithms
• Dynamic Programming
• Greedy Algorithms
• NP-Completeness
• 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:

• Homework 1: due Thursday September 17, 2015.
• Homework 2: due Friday October 2, 2015.
• Homework 3: due Sunday October 18, 2015.
• Homework 4: due Saturday November 21, 2015.
• Homework 5: due Wednesday December 2, 2015.

Announcements:

• September 10: Homework 1 is out, due Thursday September 17.
• September 25: Homework 2 is out, due Friday October 2.
• October 11: Homework 3 is out, due Sunday October 18.
• October 13: The in-class midterm exam is scheduled on Tuesday October 20, in *Room VH-133*.
• November 14: Homework 4 is out, due Saturday November 21.
• November 24: Homework 5 is out, due Wednesday December 2.
• December 1: The final exam is scheduled on Tuesday December 8, 12PM -- 2PM, in *Room VH-133*.

Schedule:

• Lecture 1 (Aug. 25): Introduction, Asymptotics (Section 3.1)
• Lecture 2 (Aug. 27): Recurrence, Strassen's Algorithm (Section 4.2, 4.5)
• Lecture 3 (Sept. 1): Polynomial Representations (Section 30.1)
• Lecture 4 (Sept. 3): Fast Fourier Transform (FFT) (Section 30.2)
• Lecture 5 (Sept. 8): Dynamic Programming I (Section 15.1, 15.2)
• Lecture 6 (Sept. 10): Dynamic Programming II (Section 15.2, 15.3)
• Lecture 7 (Sept. 15): Dynamic Programming III (Section 15.4)
• Lecture 8 (Sept. 17): Dynamic Programming IV
• Lecture 9 (Sept. 22): Greedy Algorithms I (Section 16.1)
• Lecture 10 (Sept. 24): Greedy Algorithms II (Section 23.1, 23.2)
• Lecture 11 (Sept. 29): Greedy Algorithms III (Section 16.2, 16.3)
• Lecture 12 (Oct. 1): Greedy Algorithms IV
• Lecture 13 (Oct. 6): Amortized Analysis I (Section 17.1, 17.2)
• Lecture 14 (Oct. 8): Amortized Analysis II (Section 17.3, 17.4)
• Lecture 15 (Oct. 13): Binomial Heaps
• Lecture 16 (Oct. 15): Homework Review
• Lecture 17 (Oct. 20): Midterm Exam
• Lecture 18 (Oct. 22): Midterm Review
• Lecture 19 (Oct. 27): Fibonacci Heaps I (Section 19.1, 19.2)
• Lecture 20 (Oct. 29): Fibonacci Heaps II (Section 19.3, 19.4)
• Lecture 21 (Nov. 3): Fibonacci Heaps III, Disjoint Sets I (Section 21.1)
• Lecture 22 (Nov. 5): Disjoint Sets II (Section 21.2)
• Lecture 23 (Nov. 10): NP-completeness I (Section 34.1)
• Lecture 24 (Nov. 12): NP-completeness II (Section 34.2, 34.3)
• Lecture 25 (Nov. 17): NP-completeness III (Section 34.4)
• Lecture 26 (Nov. 19): NP-completeness IV (Section 34.5)
• Lecture 27 (Nov. 24): NP-completeness V (Section 34.5)
• Lecture 28 (Dec. 1): Maximum Flow I (Section 26.1, 26.2)
• Lecture 29 (Dec. 3): Maximum Flow II (Section 26.3)