Algorithms Lecture Slides
(by Raphaël Clifford)
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.
Advanced Algorithms. Autumn 2020
The lecturer on this unit is Raphaël Clifford. The teaching assistant is Dom Hutchinson and Kheeran Nadu.Live online sessions
Asynchronous support
- Please sign up to Piazza for the unit discussion forum.
- 2018/19 exam with solutions
- 2017/18 exam with solutions (mostly). Questions 2 and 3 only.
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.
| Lecture | Topic | Slides | Readings |
| 1 | Mathematical preliminaries | Slides Video |
MIT Course Notes I, MIT Course Notes II, MIT Course Notes III. See also CLRS, Appendix C.1–C.3 |
| 2 | Hash functions | Slides Video |
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 Video |
CLRS 11.5 |
| 4 | Cuckoo hashing | Slides Video |
Cuckoo hashing for undergraduates. |
| 5 | Bloom filters | Slides Video |
Survey. |
| - | Problems class | Problem Sheet 1,Solutions | |
| 6 | van Emde Boas tree | Slides Video |
Chapter 20 of CLRS |
| - | Problems class | Problem Sheet 1 | |
| 7 | Orthogonal range queries | Slides Video |
Chapter 5 of BCKO |
| - | Problems class | Problem Sheet 2 | |
| 8 | Suffix trees | Slides Video |
See Gusfield, Part II |
| 9 | Suffix arrays | Slides Video |
Section 3 of this paper |
| 10 | Range Minimum Queries (RMQ) | Slides Video |
Simplified LCA paper |
| 11 | Lowest common ancestor (LCA) | Slides Video |
|
| - | Problems class | Problem Sheet 3 | |
| 12 | Approximation algorithms I | Slides Video |
|
| 13 | Approximation algorithms II | Slides Video |
|
| 14 | Approximation algorithms III | Slides Video |
|
| 15 | Approximation algorithms IV | Slides Video |
|
| - | Problems class | Problem Sheet 4 |
Links and Resources
[CLRS] Cormen, Leiserson, Rivest and Stein. Introduction to Algorithms (3rd Edition). Freely available online (as well as physical copies) via the Bristol library system.[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.
Past papers and revision guide
The 2018/19 revision guide is here. You should use this guide for the January 2021 exams. The syllabus changes fairly regularly and so past papers may cover topics that were not covered this year. The following exam questions follow the current syllabus.