Lecturer: Xiaohui Bei ()

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

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

- Welcome to the course!
- There will be no lecture on August 21 and 22.
- A make-up lecture will be held on Thursday, August 31
- Date and time: Thursday, August 31, 2:30pm - 4:30pm
- Venue: SPMS-TR+17

- The mid-term exam will take place on October 9
- Date and time: Monday, October 9, 10:30am - 12:00pm
- Venue: MAS Executive Classroom 1 (MAS-03-06)

- The lectures are over. Thank you all for the participation!

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 automata theory, NP-completeness, and computability.

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

**Homework policy: You are allowed (and encouraged) to discuss with your peers on the questions and solutions. But everyone needs to write and submit their own 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).

- Homework1, due September 3, 2017.
- Homework2, due September 10, 2017.
- Homework3, due September 24, 2017.
- Homework4, due October 29, 2017. [Solutions]
- Homework5, due November 12, 2017. [Solutions]

Exercise questions are for you to review the lecture contents. The solutions are also provided. It is strongly recommended to solve the exercise problems first and then compare your solutions to the standard answers, rather than to check the answers directly.

If you spot any mistakes in the questions or solutions (there definitely might be!), please do not hesitate to send me an email to check.

- Midterm Exam [solutions]
- Exercises on Regular Languages [solutions]
- Exercises on Turing Machines [solutions]
- Exercises on Class P, NP and NP-Completeness [solutions]

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