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).



Breadth First Search
and Depth First Search
Slides
Reading: JE 18/CLRS 22
Shortest Paths:
Priority Queues (Pt 1)
Slides
Reading: CLRS 6.5
Shortest Paths:
Dijkstra's Algorithm (Pt 2)
Slides
Reading: CLRS 24.3
Dynamic Programming (Pt 1)
Slides
Reading: CLRS 15/JE 5
Dynamic Programming (Pt 2)
Slides
Reading: CLRS 15/JE 5
Bloom filters
Slides
Reading: Survey
Dynamic Search Structures:
Self-balancing Trees (Pt 1)
Slides
Reading: CLRS 13 (R-B trees)
Dynamic Search Structures:
Skip Lists (Pt 2)
Slides
Reading: JE 10.2
Computational Geometry:
Line Segment Intersections
Slides
Reading: CLRS 33.2/BKCO 2
Shortest Paths Revisited:
Negative Weights (Pt 1)
Slides
Reading: CLRS 24
Shortest Paths Revisited:
All-Pairs (Pt 2)
Slides
Reading: CLRS 25
Minimum Spanning Trees
via Disjoint Sets
Slides
Reading: CLRS 23/JE 17


Advanced Algorithms

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 II
More 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 20
Notes 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.

Links and Resources

[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.