Lecturer: Xiaohui Bei ()

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

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

- Welcome to the course!
- The lecture on 11 September will be canceled.
- The mid-term exam will take place on October 8
- Date and time: Monday, October 8, 10:30am - 12:00pm
- Venue: MAS Executive Classroom 1 (MAS-03-06)

- The make up lecture will take place on Thursday, 8 November, from 5:30pm - 7:30pm.
- Venue: SPMS-TR+12

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 13, 2018. Introduction, Algorithm Basics (full slides)
- Lecture 2. August 14, 2018. Big-O Notation, Graph Basics (full slides)
- Lecture 3. August 20, 2018. Graph Traversal Algorithms (full slides)
- Lecture 4. August 21, 2018. Graph Traversal Algorithms (2), Greedy Algorithms (full slides)
- Lecture 5. August 27, 2018. Minimum Spanning Tree (full slides)
- Lecture 6. August 28, 2018. Union Find, Minimum Spanning Tree(2) (full slides)
- Lecture 7. September 3, 2018. Dijkstra Algorithm, Priority Queue (full slides)
- Lecture 8. September 4, 2018. Divide and Conquer, Sorting (full slides)
- Lecture 9. September 10, 2018. Dynamic Programming (full slides)
- Lecture 10. September 17, 2018. Dynamic Programming, All Pair Shortest Paths (full slides)
- Lecture 11. September 18, 2018. Network Flow (full slides)
- Lecture 12. September 24, 2018. Linear Programming (full slides)
- Lecture 13. September 25, 2018. Linear Programming (2) (full slides)
- Lecture 14. October 9, 2018. Regular Language (full slides)
- Lecture 15. October 15, 2018. Regular Language (2) (full slides)
- Lecture 16. October 16, 2018. Regular Language (3) (full slides)
- Lecture 17. October 22, 2018. Turing Machines (full slides)
- Lecture 18. October 23, 2018. Class P and NP (full slides)
- Lecture 19. October 29, 2018. Class P and NP (2), Reduction (full slides)
- Lecture 20. October 30, 2018. Reduction, SAT (full slides)
- Lecture 21. November 5, 2018. NP-Completeness (full slides)
- Lecture 22. November 8, 2018. NP-Completeness (2) (full slides)
- Lecture 23. November 12, 2018. Undecidability (full slides)
- Lecture 24. November 13, 2018. Undecidability (2) (full slides)

**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 August 26, 2018.
- Homework2, due September 9, 2018.
- Homework3, due September 23, 2018.
- Homework4, due October 28, 2018.
- Homework5, due November 11, 2018.

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 (third edition)*" by Sipser