This course introduces computability and computational complexity theory and the theory and practice of basic concepts and techniques in algorithms.
You can find the lecture notes on Canvas.
A list of topics and approximate times follows.
| Topic | Approximate Time | Chapter(s) |
|---|---|---|
| Background | 1 week | Sipser ch0 |
| Regular Languages | 2 week | Sipser ch1 |
| Context-free Languages | 1 week | Sipser ch2 |
| Decidability | 1-2 weeks | Sipser ch3, ch4 |
| Reducibility | 1 week | Sipser ch5 |
| Complexity | 1 week | Sipser ch7 |
| Analyzing Algorithms | 1 week | CLRS ch2 |
| Sorting and Divide and Conquer | 1 week | CLRS ch4, ch6 |
| Greedy | 1 week | CLRS ch16 |
| Dynamic Programming | 1 week | CLRS ch15 |
| Graph Algorithms | 1 week | CLRS ch22-25 |
| Advanced Data Structures | 1 week |
Learning Outcomes:
By the end of the course, the student must be able to:
- Understand the NP-completeness concept
- Explain the P vs. NP problem
- Analyze computation models
- Design a reduction between two computational problems
- Characterize different complexity classes
- Design algorithms for new problems
- Analyze algorithms