Resources

Text Book

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (fourth edition) The MIT Press, 2022. This will be referred to as CLRS4.

  • The second edition errata or third can also be used. The third edition will be referred to as CLRS3.

Note that it is now possible to access library resources online without being on the University network or using a VPN. You will be prompted for you CAS login. You need to go through the library search system. For the fourth edition follow this CLRS4 and for the third edition follow this CLRS3.

Even when the book is available for free via the University library I recommend that you buy the book. It is one of the best textbooks on algorithms available.

At the moment most of the reading guides refer to the third edition, but I will update the reading guide for the fourth edition as I go along.

Reference Book

The following book, underlying most of the slides that have been used in previous years, can also be used but does not cover Section 4.3 and Chapters 21 and 32 of CLRS3:

Algorithms and Data Structures

Some useful books and links

Python

The learning of sufficient skills on the Python programming language is within your time budget for this course, but this should not take more than a couple hours. To the best of our knowledge, almost no student on this course has officially learned Python at UU, so nobody is at a disadvantage.

  • Python programming language: official website; the skeleton codes for all the assignment problems are written in Python 3.

LaTeX and Demo Report

We highly recommend you learn or use LaTeX for typesetting your assignment reports in a professional way, but this is optional. The learning of LaTeX is outside your time budget for this course, but very well-invested as you will find out during the course or later. Here are some LaTeX resources:

Extra Slides for Revision

When Pierre Flener taught the course he used slides by Kevin Wayne. For some of the lectures I use Kevin Wayne’s slides, but for lectures where I do not, you are still encouraged to look at Kevin Wayne’s slides. They contain a number of useful examples.

TopicSlidesExtra Material (recommended)CLRS3 Textbook
Introduction and Logisticsslides numbered 1-7 of Introduction.pdf;
Chapters 1-2
Reminders: Growth of Functions, Recurrences, and Divide & Conquerslides numbered 1-3, 6-23, 30-32, 35, 39, 42-43, 46-49 of AlgorithmAnalysis.pdf;
slides 1-14 of DemoMerge.pdf;
DemoBinarySearch.pdf;
slides 1-13 of DivideAndConquerI.pdf;
slides 1-13, 26-41 of DivideAndConquerII.pdf
AD1-excerpts.pdf (some slides from when I taught AD1)Chapters 3-4, except Section *4.6
Dynamic Programmingslides numbered 1-18, 30-38, 54 of DynamicProgramming.pdfslides 39-51 of DynamicProgramming.pdfChapter 15; the slides have other examples: you are encouraged to self-study the textbook examples
Reminder: Elementary Graph Algorithmsslides 1-24, 33-43 of Graphs.pdfChapter 22, except Section 22.4 (which is not needed for AD2)
Greedy Algorithmsslides 1-8 of GreedyAlgorithmsI.pdfslides 9-15 of GreedyAlgorithmsI.pdf plus DemoEarliestFinishTimeFirst.pdf (corresponding to Section 16.1);
slides 16-23 of GreedyAlgorithmsI.pdf plus DemoEarliestStartTimeFirst.pdf
Chapter 16, except Sections *16.4 and *16.5; the slides have other examples: you are encouraged to self-study the textbook examples
Minimum Spanning Trees (MST)slides numbered 21, 23-24, 28-34, 36, 43-45, 57 of GreedyAlgorithmsII.pdf;
slides 23-40 of DemoMST.pdf
visualisation of Prim's algorithmChapter 23 (we only study Prim's algorithm)
Single-Source Shortest Pathsslides 1-15 of GreedyAlgorithmsII.pdf;
DemoDijkstra.pdf
visualisation of Dijkstra's algorithmChapter 24: pages 643-650 and Section 24.3 (we only study Dijkstra's algorithm)
Maximum Flowslides 1-42, 48-49, 56-57, 73-79 of NetworkFlowI.pdf;
DemoFordFulkerson.pdf;
slides numbered 1-12, 17-20, 24-44 (all without the proofs) of NetworkFlowII.pdf
visualisation of Ford-Fulkerson's algorithm;
slides 42-57 of NetworkFlowI.pdf if you are interested;
slides numbered 45-81 of NetworkFlowII.pdf if you are interested
Chapter 26, except Sections *26.4 and *26.5
Disjoint Setsslides 1-42, 46 of UnionFind.pdfvisualisation;
section 5.1.4 of another textbook
Chapter 21, except Sections 21.2 and *21.4
String Matchingslides 1-14, 27 of StringMatching-A.pdf;
StringMatching-B.pdf
Chapter 32, except Sections 32.3 and *32.4
P versus NPPversusNP.pdftalk by Prof. Michael SipserChapter 34