Algorithms Lecture Slides

The following slides are for the Advanced Algorithms unit of the Computer Science department at the University of Bristol. The authors of the lecture slides are stated on the front page of each set of slides. To report typos please post to the unit discussion board.

- Office hours: Mondays at 11am. For the first half with Christian Konrad in room 3.06 MVB, for the second half in room 3.15 MVB.
- Outside of office/drop-in sessions hours please ask on the unit discussion board on Piazza. Please do regiser using your university email so we can form a community of people studying Advanced Algorithms.
- There are also excellent external question and answer websites which are directly relevant to university students. I particularly recommend CS stackexchange and Math stackexchange as well as stackoverflow of course.

Full book titles (for CLRS, MU etc.) and references are given at the bottom of the page. We will put up lectures slides as the unit progresses. We will also have problems classes which will take place during a normal lecture slot in the same lecture theatre as usual.

The list of lectures is preliminary in the sense that lectures and problems sheets will be added as the term progresses.Lecture | Topic | Slides | Readings |

1 |
Mathematical preliminaries | Slides | MIT Course Notes I, MIT Course Notes II, MIT Course Notes III. 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 Very nice exploration of theoretically sound practical hashing |

3 |
Static perfect hashing | Slides | CLRS 11.5 |

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

5 |
Bloom filters | Slides | Survey. |

- |
Problems class | Problem Sheet 1 | |

6 |
van Emde Boas tree | Slides | Chapter 20 of CLRS |

- |
Problems class | Problem Sheet 1 | |

7 |
Orthogonal range queries | Slides | Chapter 5 of BCKO |

- |
Problems class | Problem Sheet 2 | |

8 |
Suffix trees | Slides | See Gusfield, Part II |

9 |
Suffix arrays | Slides | Section 3 of this paper |

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

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

- |
Problems class | Problem Sheet 3 | |

12 |
Approximation algorithms I | Slides | |

13 |
Approximation algorithms II | Slides | |

14 |
Approximation algorithms III | Slides | |

15 |
Approximation algorithms IV | Slides | |

- |
Problems class | Problem Sheet 4 |

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

[DPV] S. Dasgupta, C.H. Papadimitriou and U.V. Vazirani. *Algorithms*. A draft is available online.

[Gusfield] D. Gusfield.
*Algorithms on Strings Trees and Sequences*. Freely available online (as well as a physical copy) via the Bristol library system.

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

[BCKO] M. de Berg, O. Cheong, M. van Kreveld, M. Overmars.
* Computational Geometry: algorithms and applications*. Available online. (If anyone has reason to believe this copy is not legally provided, please contact me and I will take it down.)

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

- 2017/18 exam with solutions (mostly). Questions 2 and 3 only.