Course pages 2013–14
Mon-Wed-Fri 1000-1100 in Arts School A, from 2014-01-17 to 2014-03-12.
The official syllabus has its own page. More accurately, here is what we actually did in lectures and is considered examinable, with reference to CLRS3 and mentioning any book sections you may skip from the relevant chapters.
2014-01-17 Fri (Intro; insert sort, correctness, asymptotic notation)
CLRS3: 1.1, 1.2, 2.1, 2.2, (2.3 in a future lecture), 3.1. You may skip 3.2.
Handout: pages 1-19.
2014-01-20 Mon (Costs; other quadratic sorting)
CLRS3: 2.2, 2.3, 8.1. You may skip chapters 4 and 5.
Handout: pages 19-24.
2014-01-22 Wed (Mergesort, quicksort, order statistics)
CLRS3: 2.3, 7.1, 7.2, 7.3, 9.1, 9.2. You may skip 7.4, 9.3. Chapters 6 and 8 in future lectures.
Handout: pages 24-32.
2014-01-24 Fri (Heapsort, stability, counting sort)
CLRS3: 6.1, 6.2, 6.3, 6.4 (6.5 in a future lecture), 8.2.
Handout: pages 33-37.
2014-01-27 Mon (Bucket sort. Radix sort. Dynamic programming)
CLRS3: 8.4. 8.3. 15.2, 15.3. You may skip 15.1 but read the "15.0" at the start.
Handout: pages 40-43.
2014-01-29 Wed (Dynamic programming)
CLRS3: 15.3, 15.4. You may skip 15.5.
Handout: pages 40-43.
2014-01-31 Fri (Greedy algorithms; algorithm design strategies)
CLRS3: 16.1, 16.2. You may skip 16.3, 16.4, 16.5. 2.3.
Handout: pages 43-48.
2014-02-03 Mon (Data structures; Abstract data types)
CLRS3: 10.1, 10.2, 10.3, 10.4.
Handout: pages 49-62.
2014-02-05 Wed (Binary search trees; Red-black trees)
CLRS3: 12.1, 12.2, 12.3. You may skip 12.4. 13.1 and 13.2.
Handout: pages 62-65.
2014-02-07 Fri (Red-black trees; 2-3-4 trees; B-trees)
CLRS3: 13.3, 13.4. 18.1, 18.2.
Handout: pages 64-69
2014-02-10 Mon (B-trees; hash tables)
CLRS3: 18.3. 11.1, 11.2, 11.4. You may skip 11.3 and 11.5.
Handout: pages 70-73
2014-02-12 Wed (Priority queues, binary heaps, binomial heaps)
Handout: pages 74-79
2014-02-14 Fri (Amortized Analysis, Aggregate Analysis and Potential Method)
Handout: pages 80-84
2014-02-17 Mon (Fibonacci Heap, Basic Structure, Operations: Insert, Extract-Min, Decrease-Key)
CLRS3: 19.1-19.3 (without amortized analysis)
Handout: pages 85-91
(slight update to make process of unmarking nodes more explicit and to point out the differences to CLRS3; the process of unmarking is also explained in detail on page 89 of your handout)
2014-02-19 Wed (Fibonacci Heap, Amortized Costs, Bounding Maximum Degree)
CLRS3: 19.1-19.3 (amortized analysis), 19.4
Handout: pages 92-95
Thanks to Charlie Barton for pointing out that on Slide 4 "marks(H') = marks(H)" has to be replaced by "marks(H') <= marks(H)"
2014-02-21 Fri (Proto VEB Trees)
CLRS3: 20.1, 20.2
Handout: pages 95-100
2014-02-24 Mon (Proto VEB Trees (cont.), Van Emde Boas Trees)
CLRS3: 20.2, 20.3
Handout: pages 100-103
2014-02-26 Wed (Disjoint Sets, Graph Algorithms: Representation of Graphs, Searching)
CLRS3: 21.1, 21.2, 21.3 (you may skip 21.4), 22.1, 22.2, 22.3
Handout: pages 104-111
2014-02-28 Fri (Searching: BFS and DFS, Topological Sort)
CLRS3: 22.2, 22.3, 22.4 (you may skip 22.5)
Handout: pages 112-114
2014-03-03 Mon (Minimum Spanning Trees: Kruskal and Prim, Single-Source Shortest Path: Bellman-Ford (without analysis))
CLRS3: 23.1, 23.2, 24.1
Handout: pages 115-122
Thanks to Andrei Ruskuc for pointing out that on Slide 18, Convergence Property, "shortest path from u to v" has to replaced by "shortest path from s to v"
2014-03-05 Wed (Single-Source Shortest Path: Bellman-Ford (analysis), Dijkstra, All-Pairs Shortest Path: Matrix Multiplication)
CLRS3: 24.1, 24.3, 24.5 (you may skip 24.2 and 24.4), 25.1
Handout: page 123-126
Thanks to an anonymous student for pointing out that on Slide 7, Pass 4, the edge (t,z) was not relaxed properly
2014-03-07 Fri (All-Pairs Shortest Path: Matrix Multiplication and Johnson's Algorithm, Maximum Flows)
CLRS3: 25.1, 25.3 (you may skip 25.2), 26.1, 26.2 (you may skip pages 721-731)
Handout: pages 127-131
2014-03-10 Mon (Maximum Flows continued, Application to Bipartite Matching, Parallel Algorithms)
CLRS3: 26.3 (you may skip 26.4, 26.5), 27.1 (you may skip 27.2, 27.3)
Handout: pages 132-142
2014-03-12 Wed (Geometric Algorithms)
CLRS3: 33.1 (you may skip 33.2), 33.3 (you may skip 33.4)
Handout: pages 143-149
If you find any errors in the slides or handout, please send an email to tms41 at cam.ac.uk or approach me after the lecture.
Distributed during the first lecture. It will be to your advantage to bring your handout to every lecture, together with a notebook with non-detachable pages and a few coloured pens. Further printed copies of the handout are available from the student administration office in the William Gates Building. An electronic copy is also available.
Please use the online Otter system, which is still somewhat experimental, and help us make it work for you by providing constructive feedback on how it could be improved. We are aware that there may be teething problems but please support us. To help you in the meantime, here are last year's exercise sheets for Algorithms I and Algorithms II, covering similar ground to the first and second half of the course respectively. New exercises and exams will only be added to Otter from now on.
Past exam questions for Algorithms I, Algorithms II, Data Structures and Algorithms (old) and Algorithms (old) may be of interest. If you want to own this material rather than just memorize it, attempt the questions as seriously as if you were taking the exam yourself and do not open the solution notes until after having irrevocably committed (no more changes) to your own solution. The best students already understand the wisdom of this advice; for the others, yeah, the pressure is high, the temptation is strong, the flesh is weak...
2014-01-31: segmented least squares
- Charlie Barton
- Daria Dicu
- Isaac Dunn
- Gabor Igloi
- Gabriela Sklencarova
- Lauren Pick
...and, shortly after the deadline, also...
- Siddhant Jayakumar
- Daniel Wong
Template for drawing Van Emde Boas Trees, cf. Exercise 55 (2014-02-24) PDF
Exercises on DFS (2014-03-03) PDF
IBM Ethical Hacking Event
Tuesday 11th March, 2.30pm-5.30pm, Intel Teaching Lab, Sign up here
Places are limited, so please sign-up now to make sure you get a place.