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. Spring 2020

The lecturers on this unit are Christian Konrad and Raphaël Clifford. The teaching assistants are Hazel Doughty and Jake Witter who will run drop-in sessions on Tuesdays 4-5pm in MVB 1.11 and attend the problems classes. On Tuesday February 11 the room will be QB 1.7 instead.

Lectures

  • Mondays in QB 1.18, 10-11am
  • Thursdays in QB 1.15, 12-1pm
  • Office hours, drop-in sessions and other help

    • 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

    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. The syllabus changes every year and so past papers may cover topics that were not covered this year. I have tried to indicate where this has occurred.