Algorithms Lecture Slides

The following slides are from two current courses that I teach in the Computer Science department at the University of Bristol. The main course pages are only available to current students in the department. I have decided to make my lectures from these courses publicly available for personal educational use.

Except where stated, all of the lecture slides below were produced by me. If you want to use them for anything else (for example at another university) please contact me at ben@cs.bris.ac.uk. Also, feel free to contact me with any typos :).

These lecture slides are from our core (compulsory) second-year course on Data Structures and Algorithms. There are also links to external notes and book references under "Readings". Full book titles (for CLRS, MU etc.) and references are given at the bottom of the page. Many of the readings are from the excellent notes by Jeff Erickson (referred to as JE below).

Breadth First Search and Depth First Search Slides Reading: JE 18/CLRS 22 |
Shortest Paths: Priority Queues (Pt 1) Slides Reading: CLRS 6.5 |
Shortest Paths: Dijkstra's Algorithm (Pt 2) Slides Reading: CLRS 24.3 |

Dynamic Programming (Pt 1) Slides Reading: CLRS 15/JE 5 |
Dynamic Programming (Pt 2) Slides Reading: CLRS 15/JE 5 |
Bloom filters Slides Reading: Survey |

Dynamic Search Structures: Self-balancing Trees (Pt 1) Slides Reading: CLRS 13 (R-B trees) |
Dynamic Search Structures: Skip Lists (Pt 2) Slides Reading: JE 10.2 |
Computational Geometry: Line Segment Intersections Slides Reading: CLRS 33.2/BKCO 2 |

Shortest Paths Revisited: Negative Weights (Pt 1) Slides Reading: CLRS 24 |
Shortest Paths Revisited: All-Pairs (Pt 2) Slides Reading: CLRS 25 |
Minimum Spanning Trees via Disjoint Sets Slides Reading: CLRS 23/JE 17 |

These lecture slides are from our optional third-year course on Advanced Algorithms. There are also links to external notes and book references in the "Readings" column. Full book titles (for CLRS, MU etc.) and references are given at the bottom of the page.

Lecture | Topic | Slides | Readings |

1 |
Mathematical preliminaries | Slides | MIT Course Notes. See also CLRS, Appendix C.1–C.3 |

2 |
Hash functions | Slides | MIT Notes covering lectures 2,3 and 4. CLRS 11.3.3, MU p. 90–93, 314–328 |

3 |
Static perfect hashing | Slides | CLRS 11.5 |

4 |
Cuckoo hashing | Slides | Cuckoo hashing for undergraduates. |

5 |
Suffix trees | Slides | External notes I and External notes II. See also Gusfield, Part II More on suffix trees, see External notes III. |

6 |
Suffix arrays | Slides | Gusfield p. 149–156. Section 3 of this paper. This comparison of three methods. |

7 |
Range Minimum Queries (RMQ) | Slides | Simplified LCA paper |

8 |
Lowest common ancestor (LCA) | Slides | |

9 |
Hamming distance | Slides | The original paper (Algorithm B and Algorithm C). Beware of the old-school notation |

10 |
k-mismatches | Slides | The original paper (upto Section 4) |

11 |
Orthogonal range searching | Slides | BCKO, Ch. 5, External Notes (based on BCKO, Ch. 5) |

12 |
Van Emde Boas trees | Slides | CLRS, Chapter 20 Notes 1, notes 2. |

13 |
P, NP and constant factor approximations | Slides | External notes |

14 |
Further constant factor approximations | Slides | External notes, KT Chapter 11 |

15 |
(Fully) Polynomial time approximation schemes | Slides | External notes |

16 |
Asymptotic Polynomial time approximation schemes | Slides | AxA Chapter 9 |

These last five lectures have been given in previous years but were not included last year. Lectures **A3**, **A4** and **A5** were produced and delivered by Markus Jalsenius, who has kindly agreed to allow them to be included here.

Lecture | Topic | Slides | Readings |

A1 |
Deterministic Communication Complexity | Slides | External Notes. |

A2 |
Randomised Communication Complexity | Slides | External Notes. |

A3 |
Linear Programming | Slides | DPV 7.1, 7.4 |

A4 |
Maximum flow and minimum cut | Slides | CLRS, Chapter 26 (p.708–727) DPV 7.2, 7.3 |

A5 |
Approximation using Linear Programming | Slides | No external notes. |

[JE] Excellent notes by Jeff Erickson. These are freely available.

[DPV] S. Dasgupta, C.H. Papadimitriou and U.V. Vazirani.
*Algorithms*.

[Gusfield] D. Gusfield.
*Algorithms on Strings Trees and Sequences*.

[MU] M. Mitzenmacher and E. Upfal.
*Probability and Computing*.

[BCKO] M. de Berg, O. Cheong, M. van Kreveld, M. Overmars.
* Computational Geometry*.

[AxA] V. V. Vazirani. Approximation Algorithms.

[KT] J. Kleinerg and E. Tardos. Algorithm Design.