Algorithms and Computation

Instructor: Hossein Jowhari
Semester: Fall 2021 (99-2)
Time: SAT, MON 10:30-12:00
Textbook: Algorithm Design by Klienberg and Tardos,
Introduction to the Theory of Computation by Michael Sipser,
and Randomized algorithms by Rajeev Motwani and Prabhakar Raghavan
Evaluation: Homeworks(30%), Midterm (30%), Final(60%),

Lectures :

Lecture Subject Material References
0 Introduction to the course, Basics of algorithm analysis slides -
1 Greedy algorithms slides -
2 Greedy algorithms, Dynamic programming slides
3 Maximum flow slides
4 NP-completeness slides
5 Reductions, NP-complete problems slides
6 Algorithms for NP-complete problems slides -
7 Approximation for NP-hard problems slides
8 Space complexity slides
9 Randomized algorithms, Karger's min-cut algorithm slides
10 ZPP, Randomized algorithm for 3-SAT slides
11 Concentration bounds, Balls and bins slides
12 Markov chains and random Walks, Randomized 2-SAT algorithm slides
13 Markov chains and random walks, cover time slides