Lecturer: Xiaohui Bei ()

- Monday 10:30am - 12:30am, SPMS-TR+8
- Tuesday 09:30am - 11:30am, SPMS-TR+10

- Tutorial: Tuesday 10:30am - 11:30am, SPMS-TR+10 (biweekly) - Office hour: Tuesday 11:30am - 12:30am, SPMS-05-46

- Welcome to the course!
- There will be no lecture on Tuesday, August 9.
- There will be no lecture on Monday, September 12.
- The mid-term exam will be held on Monday, October 3, 10:30am - 12:00am in TR120 (located at SS4-01-26). It is a closed book exam and the duration will be 90 minutes. The relevant material is from lectures 1-10.

The class consists of two parts: algorithms and complexity. The first part will give a introduction to general algorithm design paradigms as well as algorithms for several specific problems. The second part will talk about topics of NP-completeness, computability, automata theory, and circuit complexity.

- Lecture 1. August 8, 2016. Introduction, Algorithm Basics, Big-O Notation
- Lecture 2. August 15, 2016. Graph Basics, Graph Traversal Algorithms
- Lecture 3. August 16, 2016. Breadth First Search and Depth First Search
- Lecture 4. August 22, 2016. Greedy Algorithms, Minimum Spanning Tree
- Lecture 5. August 23, 2016. Minimum Spanning Tree
- Lecture 6. August 29, 2016. Shortest Path, Dijkstra Algorithm
- Lecture 7. August 30, 2016. Divide and Conquer, Sorting
- Lecture 8. September 5, 2016. Dynamic Programming
- Lecture 9. September 6, 2016. Dynamic Programming, All Pair Shortest Paths
- Lecture 10. September 13, 2016. Network Flow
- Lecture 11. September 19, 2016. Linear Programming
- Lecture 12. September 20, 2016. Linear Programming (2)
- Lecture 13. October 10, 2016. Regular Language (Reading materials: Sipser Section 1.1, 1.2)
- Lecture 14. October 11, 2016. Regular Language (2) (Reading materials: Sipser Section 1.3, 1.4)
- Lecture 15. October 17, 2016. Turing Machines (Reading materials: Sipser Section 3.1, 3.2)
- Lecture 16. October 18, 2016. Class P, NP (Reading materials: Sipser Section 7.2, 7.3)
- Lecture 17. October 24, 2016. Class P, NP, Reduction (Reading materials: Sipser Section 7.3)
- Lecture 18. October 25, 2016. Reduction, SAT (Reading materials: Sipser Section 7.3, 7.4)
- Lecture 19. October 31, 2016. NP Completeness (Reading materials: Sipser Section 7.4, 7.5)
- Lecture 20. November 1, 2016. NP Completeness (2) (Reading materials: Sipser Section 7.4, 7.5)
- Lecture 21. November 7, 2016. Undecidability (Reading materials: Sipser Section 4.2, 5.1)
- Lecture 22. November 8, 2016. Undecidability (2) (Reading materials: Sipser Section 4.2)

**Updated homework policy: starting from the 4th homework, the group work is not allowed anymore. You are still allowed (and encouraged) to discuss with your peers on the questions and solutions. But everyone needs to write and submit their own solutions.**

- Homework 1, due August 20, 2016.
- Homework 2, due September 1, 2016.
- Homework 3, due September 15, 2016.
- Homework 4, due October 20, 2016. (Solutions)
- Homework 5, due November 3, 2016. (Solutions)

Homework can be submitted by (as PDF files obtained from LaTeX or Word sources), or by pushing a hard copy under my office door (MAS-05-46).

There is no required textbook for this course. However, the following books are recommended:

- "
*Algorithm Design*" by Kleinberg, Tardos - "
*Introduction to Algorithms*" by Cormen, Leiserson, Rivest, Stein - "
*Introduction to the Theory of Computation (second edition)*" by Sipser