Instructor: Ning Xie (office ECS 380)

Location: ECS 235

Time: Tuesday and Thursday 9:30 AM -- 10:45 AM

Office Hours: Tuesday/Thursday 2:30 PM -- 3:30 PM, or by appointments

TA: Shuai Xu (username: sxu010). Office Hours: Wednesday 12:00 -- 14:00 at ECS 257.

**
(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 8, 2016.
- Homework 2: due Wednesday October 5, 2016.
- Homework 3: due Saturday October 15, 2016.
- Homework 4: due Sunday November 13, 2016.
- Homework 5: due Wednesday November 30, 2016.

** Announcements: **

- September 1: Homework 1 is out, due Thursday September 8.
- September 28: Homework 2 is out, due Wednesday October 5.
- October 8: Homework 3 is out, due Saturday October 15.
- October 11: The in-class midterm exam is scheduled on Thursday October 20.
- November 6: Homework 4 is out, due Sunday November 13.
- November 22: Homework 5 is out, due Wednesday November 30.
- November 22: The final exam is scheduled on Tuesday December 6, 9:30 AM -- 11:30 AM, in ECS 235.

** Schedule: **

- Lecture 1 (Aug. 23): Introduction, Asymptotics (Section 3.1)
- Lecture 2 (Aug. 25): Recurrence, Strassen's Algorithm (Section 4.2, 4.5)
- Lecture 3 (Aug. 30): Polynomial Representations (Section 30.1)
- Lecture 4 (Sept. 1): Fast Fourier Transform (FFT) (Section 30.2)
- Lecture 5 (Sept. 6): Linear time computing median (Section 9.3), Dynamic Programming I (Section 15.1)
- Lecture 6 (Sept. 8): Dynamic Programming II (Section 15.2, 15.3)
- Lecture 7 (Sept. 13): Dynamic Programming III (Section 15.4)
- Lecture 8 (Sept. 15): Dynamic Programming IV
- Lecture 9 (Sept. 20): Recitation I
- Lecture 10 (Sept. 22): Dynamic Programming V, Greedy Algorithms I (Section 16.1)
- Lecture 11 (Sept. 27): Greedy Algorithms II (Section 23.1, 23.2)
- Lecture 12 (Sept. 29): Greedy Algorithms III (Section 16.2, 16.3)
- Lecture 13 (Oct. 4): Greedy Algorithms IV
- Lecture 14 (Oct. 6): Cancelled due to Hurricane Matthew
- Lecture 15 (Oct. 11): Amortized Analysis I (Section 17.1, 17.2)
- Lecture 16 (Oct. 13): Recitation II
- Lecture 17 (Oct. 18): Amortized Analysis II (Section 17.3, 17.4)
- Lecture 18 (Oct. 20): Midterm Exam
- Lecture 19 (Oct. 25): Review of Midterm Exam
- Lecture 20 (Oct. 27): Binomial Heaps (CLRS 2nd edition: Section 19.1, 19.2)
- Lecture 21 (Nov. 1): Fibonacci Heaps I (Section 19.1, 19.2)
- Lecture 22 (Nov. 3): Fibonacci Heaps II (Section 19.3, 19.4)
- Lecture 23 (Nov. 8): NP-completeness I (Section 34.1)
- Lecture 24 (Nov. 10): NP-completeness II (Section 34.2, 34.3)
- Lecture 25 (Nov. 15): NP-completeness III (Section 34.4)
- Lecture 26 (Nov. 17): NP-completeness IV (Section 34.5)
- Lecture 27 (Nov. 22): NP-completeness V (Section 34.5)
- Lecture 28 (Nov. 29): Recitation III