Algorithms Lecture Slides (by Raphaël Clifford)

Advanced Algorithms. Autumn 2021

The lecturer on this unit is Raphaël Clifford. The teaching assistants are Alex Carpentar and Kheeran Naidu.

Lectures

Lecture slides and videos are provided online and linked below. Please do read as much of the linked "Readings" as possible as well as it will help you understand the material more deeply.

Live online sessions

There will be a live online question and answer session every Tuesday at 5pm. The Zoom link is on the Welcome page of the unit's blackboard page. Please come along with any questions you have about the lecture material.

Problems classes

There are 5 in person problems classes scheduled below.

Each is at 3pm on a Thursday in the Ada Lovelace building room SM2 (the old Maths building).

There will be no lectures or problems classes on Mondays despite what may be in your calendars.

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

Revision guide and past papers

The guide to examinable material is now available. You can also find past papers on the blackboard page.

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.