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 2023

The lecturer on this unit is Raphaël Clifford. The teaching assistants are Archie Walton and James Millan.

Lectures

Tuesdays 9:00 and Thursdays 15:00 in Ada Lovelace SM4. Please do read as much of the linked "Readings" as possible as well as it will help you understand the material more deeply.

Office hours

Problems classes

There are 5 in person problems classes scheduled on Wednesdays at 10:00 in Ada Lovelace SM4. These will occur in weeks 3, 5, 7, 8 and 12 (that is Oct 11, 25, Nov 8, 15 and Dec 13).

Asynchronous support

• Please sign up to Piazza for the unit discussion forum. This is the best way to ask questions for this unit.

Full book titles (for CLRS, MU etc.) and references are given at the bottom of the page. There will also be 5 problems classes which will take place during a normal lecture slot in the Ada Lovelace building, room SM2.

Lecture	Topic	Slides	Readings
1 Week 1	Mathematical preliminaries	Slides Shorter	MIT Course Notes I, MIT Course Notes II, MIT Course Notes III. See also CLRS, Appendix C.1–C.3
2 Week 1	Hash functions	Slides Shorter	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 Week 2	Static perfect hashing	Slides Shorter	CLRS 11.5
4 Week 2	Cuckoo hashing	Slides Shorter	Cuckoo hashing for undergraduates.
5 Week 3	Bloom filters	Slides Shorter	Survey.
- Week 3	Problems class		Problem Sheet 1
6 Week 3	van Emde Boas tree	Slides Shorter	Chapter 20 of CLRS
7 Week 4	Orthogonal range queries	Slides Shorter	Chapter 5 of BCKO
8 Week 4	Suffix trees	Slides Shorter	See Gusfield, Part II
9 Week 5	Suffix arrays	Slides Shorter	Section 3 of this paper
- Week 5	Problems class		Problem Sheet 1, Solutions
10 Week 5	Range Minimum Queries (RMQ)	Slides Shorter	Simplified LCA paper
11 Week 7	Lowest common ancestor (LCA)	Slides Shorter
- Week 7	Problems class		Problem Sheet 2, Solutions
12 Week 7	Approximation algorithms I	Slides Shorter
13 Week 8	Approximation algorithms II	Slides Shorter
- Week 8	Problems class		Problem Sheet 3, Solutions
14 Week 8	Approximation algorithms III	Slides Shorter
- Week 12	Problems class		Problem Sheet 4, Solutions