Introduction to the Theory of Computation by Michael Sipser,

and Randomized algorithms by Rajeev Motwani and Prabhakar Raghavan

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 |