These lecture notes are intended for use with the textbook
Algorithm Design
by Jon Kleinberg and Éva Tardos.

† denotes slides that have not been edited.

TOPICS | READING | IN-CLASS DEMOS |
---|---|---|

Stable matching | Chapter 1 | Propose-and-reject |

Algorithm analysis | Chapter 2 | |

Graphs | Chapter 3 | Topological order |

Greedy algorithms | Chapter 4.1 - 4.4 | Interval scheduling · Dijkstra |

Minimum spanning tree | Chapter 4.5 - 4.7 | |

Divide-and-conquer | Chapter 5.1 - 5.5 | Merge · Merge and invert |

Convolution and FFT | Chapter 5.6 | |

Dynamic programming | Chapter 6.1 - 6.7 | |

Bellman-Ford | Chapter 6.8 - 6.10 | |

Max flow, min cut | Chapter 7.1 - 7.3 | Ford-Fulkerson |

Network flow applications | Chapter 7.5 - 7.12 | |

Assignment problem † | Chapter 7.13 | |

Intractability | Chapter 8.1 - 8.2 | |

Poly-time reductions | Chapter 8.5 - 8.8, 8.10 | The Longest Path [mp3] |

NP-completeness | Chapter 8.3 - 8.4, 8.9 | |

PSPACE | Chapter 9 | |

Extending limits of tractability | Chapter 10 | |

Approximation algorithms | Chapter 11 | List scheduling |

Local search | Chapter 12 | |

Randomized algorithms | Chapter 13 |