COT6405: Analysis of Algorithms (Fall 2014)

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:00 or by appointment
TA: Kianoush Gholami. Office Hours: Wednesday 14:00 -- 16:00 at ECS 231.



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

Syllabus:

• Asymptotics, Recurrence
• Divide-and-Conquer (Strassen, FFT)
• Basic Data Structures: Trees, Hash Tables, Priority Queues, etc
• Graphs & Graph Algorithms
• Dynamic Programming
• Greedy Algorithms
• NP-Completeness
• Network Flow
• String Matching

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 Tuesday September 16, 2014.
• Homework 2: due Friday October 3, 2014.
• Homework 3: due Thursday October 16, 2014.
• Homework 4: due Sunday November 16, 2014.
• Homework 5: due Sunday November 30, 2014.

Announcements:

• September 9: Homework 1 is out, due Tuesday September 16, 2014.
• September 26: Homework 2 is out, due Friday October 3, 2014.
• October 9: Homework 3 is out, due Thursday October 16, 2014.
• October 9: The in-class midterm exam is scheduled on Tuesday October 21, 2014.
• November 4: The final exam is scheduled on Tuesday December 9, 2014, 12:00 -- 2:00 PM in ECS 136.
• November 8: Homework 4 is out, due Sunday November 16, 2014.
• November 23: Homework 5 is out, due Sunday November 30, 2014.

Schedule:

• Lecture 1 (Aug. 26): Pre-semester Test. Introduction
• Lecture 2 (Aug. 28): Asymptotics, Running Time Analysis, Merge Sort (Chapter 1, 2, Section 3.1, 4.4)
• Lecture 3 (Sept. 2): Master Theorem, Strassen's Algorithm (Section 4.2, 4.5)
• Lecture 4 (Sept. 4): Polynomial Representations (Section 30.1)
• Lecture 5 (Sept. 9): Fast Fourier Transform (FFT) (Section 30.2)
• Lecture 6 (Sept. 11): Heaps, Heap Sort and Priority Queues (Chapter 6)
• Lecture 7 (Sept. 16): Probabilistic Analysis and Randomized Algorithms (Chapter 5)
• Lecture 8 (Sept. 18): Medians and Order Statistics (Section 9.1, 9.2)
• Lecture 9 (Sept. 23): Quicksort (Chapter 7)
• Lecture 10 (Sept. 25): Hash Tables (Section 11.1, 11.2)
• Lecture 11 (Sept. 30): Applications of Hash Tables (Section 11.3, 17.1)
• Lecture 12 (Oct. 2): String Matching, Karp-Rabin (Section 32.1, 32.2)
• Lecture 13 (Oct. 7): Graphs Representations and BFS (Appendix B.4, Section 22.1, 22.2)
• Lecture 14 (Oct. 9): Bipartite Graphs, DFS (Section 22.3)
• Lecture 15 (Oct. 14): Topological Sort, Strongly Connected Components (Section 22.4, 22.5)
• Lecture 16 (Oct. 16): Shortest Paths, Bellman-Ford (Section 24.0, 24.1)
• Lecture 17 (Oct. 21): In-class Midterm Exam
• Lecture 18 (Oct. 23): Dijkstra's Algorithm (Section 24.3)
• Lecture 19 (Oct. 28): Greedy Algorithms, Activity-selection (Section 16.0, 16.1)
• Lecture 20 (Oct. 30): Huffman Codes (Section 16.2, 16.3)
• Lecture 21 (Nov. 4): Dynamic Programming I (Section 15.1, 15.2, 15.3)
• Lecture 22 (Nov. 6): Dynamic Programming II (Section 15.4)
• Lecture 23 (Nov. 11): No Class (Veteran's day)
• Lecture 24 (Nov. 13): Dynamic Programming III (Space-efficient DP, Longest Increasing Subsequence)
• Lecture 25 (Nov. 18): NP Completeness I (Section 34.0, 34.1, 34.2)
• Lecture 26 (Nov. 20): NP Completeness II (Section 34.3, 34.4)
• Lecture 27 (Nov. 25): NP Completeness III (Section 34.5)
• Lecture 28 (Dec. 2): Maximum Flow I (Section 26.1)
• Lecture 29 (Dec. 4): Maximum Flow II (Section 26.2, 26.3)