About the course:
This first part of the course will introduce the fundamentals of design and analysis of algorithms. Algorithm design techniques such as divide and conquer,
randomization, greedy, and dynamic programming will be presented with applications. The second part
will introduce Turing machines, undecidability, time and space complexity, and NP-completeness.
Schedule:
First class: Aug. 13, Monday, 9.30am at SPMS TR+15
Mon: 9.30am-11.30am, SPMS TR+15
Fri: 9.30am-11.30pm, SPMS TR+15
Textbooks/References:
We will cover material mainly from the following texts in addition to other sources (all books are on reserve at the Lee Wee Nam library):
G. Pandurangan. Algorithms (pdf).
2. Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein (available online for free at NTU library).
3. Introduction to Theory of Computation, by Sipser.
4. Computational Complexity, by Papadimitriou.
5. Algorithm Design, by Kleinberg and Tardos.
6. Theoretical Computer Science Cheat Sheet (by S. Seiden). A useful collection of math formulas and facts.
Lecture Notes:
Course Information, Introduction, Mathematical Concepts