# Algorithms Lecture Slides

## (by Benjamin Sach)

The following slides are from two current courses that I teach in the Computer Science department at the University of Bristol. The main course pages are only available to current students in the department. I have decided to make my lectures from these courses publicly available for personal educational use.

Except where stated, all of the lecture slides below were produced by me. If you want to use them for anything else (for example at another university) please contact me at ben@cs.bris.ac.uk. Also, feel free to contact me with any typos :).

## Data Structures and Algorithms

These lecture slides are from our core (compulsory) second-year course on Data Structures and Algorithms. There are also links to external notes and book references under "Readings". Full book titles (for CLRS, MU etc.) and references are given at the bottom of the page. Many of the readings are from the excellent notes by Jeff Erickson (referred to as JE below).

These lecture slides are from our optional third-year course on Advanced Algorithms. There are also links to external notes and book references in the "Readings" column. Full book titles (for CLRS, MU etc.) and references are given at the bottom of the page.

 Lecture Topic Slides Readings 1 Mathematical preliminaries Slides MIT Course Notes. 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 3 Static perfect hashing Slides CLRS 11.5 4 Cuckoo hashing Slides Cuckoo hashing for undergraduates. 5 Suffix trees Slides External notes I and External notes II. See also Gusfield, Part IIMore on suffix trees, see External notes III. 6 Suffix arrays Slides Gusfield p. 149–156. Section 3 of this paper.This comparison of three methods. 7 Range Minimum Queries (RMQ) Slides Simplified LCA paper 8 Lowest common ancestor (LCA) Slides 9 Hamming distance Slides The original paper (Algorithm B and Algorithm C). Beware of the old-school notation 10 k-mismatches Slides The original paper (upto Section 4) 11 Orthogonal range searching Slides BCKO, Ch. 5, External Notes (based on BCKO, Ch. 5) 12 Van Emde Boas trees Slides CLRS, Chapter 20Notes 1, notes 2. 13 P, NP and constant factor approximations Slides External notes 14 Further constant factor approximations Slides External notes, KT Chapter 11 15 (Fully) Polynomial time approximation schemes Slides External notes 16 Asymptotic Polynomial time approximation schemes Slides AxA Chapter 9

These last five lectures have been given in previous years but were not included last year. Lectures A3, A4 and A5 were produced and delivered by Markus Jalsenius, who has kindly agreed to allow them to be included here.

 Lecture Topic Slides Readings A1 Deterministic Communication Complexity Slides External Notes. A2 Randomised Communication Complexity Slides External Notes. A3 Linear Programming Slides DPV 7.1, 7.4 A4 Maximum flow and minimum cut Slides CLRS, Chapter 26 (p.708–727) DPV 7.2, 7.3 A5 Approximation using Linear Programming Slides No external notes.

[CLRS] Cormen, Leiserson, Rivest and Stein. Introduction to Algorithms (3rd Edition).

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

[DPV] S. Dasgupta, C.H. Papadimitriou and U.V. Vazirani. Algorithms.

[Gusfield] D. Gusfield. Algorithms on Strings Trees and Sequences.

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

[BCKO] M. de Berg, O. Cheong, M. van Kreveld, M. Overmars. Computational Geometry.

[AxA] V. V. Vazirani. Approximation Algorithms.

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