Course pages 2013–14

Algorithms

Lectures

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)

CLRS3: 6.5

Handout: pages 74-79

2014-02-14 Fri (Amortized Analysis, Aggregate Analysis and Potential Method)

CLRS3: 17.1-17.3

Handout: pages 80-84

Slides: full (for reading on a computer), compressed (for printing), 4-up (for printing)

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

Slides: full (for reading on a computer), compressed (for printing), 4-up (for printing)

2014-02-19 Wed (Fibonacci Heap, Amortized Costs, Bounding Maximum Degree)

CLRS3: 19.1-19.3 (amortized analysis), 19.4

Handout: pages 92-95

Slides: full (for reading on a computer), compressed (for printing), 4-up (for printing)

2014-02-21 Fri (Proto VEB Trees)

CLRS3: 20.1, 20.2

Handout: pages 95-100

Slides: full (for reading on a computer), compressed (for printing), 4-up (for printing)

2014-02-24 Mon (Proto VEB Trees (cont.), Van Emde Boas Trees)

CLRS3: 20.2, 20.3

Handout: pages 100-103

Slides: full (for reading on a computer), compressed (for printing), 4-up (for printing)

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

Slides: full (for reading on a computer), compressed (for printing), 4-up (for printing)

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

Slides: full (for reading on a computer), compressed (for printing), 4-up (for printing)

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

Slides: full (for reading on a computer), compressed (for printing), 4-up (for printing)

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

Slides: full (for reading on a computer), compressed (for printing), 4-up (for printing)

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

Slides: full (for reading on a computer), compressed (for printing), 4-up (for printing)

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-138

Slides: full (for reading on a computer), compressed (for printing), 4-up (for printing)

2014-03-12 Wed (Parallel Algorithms continued, Geometric Algorithms)

CLRS3: 27.1, 33.1 (you may skip 33.2), 33.3 (you may skip 33.4)

Handout: pages 139-149

Slides: full (for reading on a computer), compressed (for printing), 4-up (for printing)

Examination Guidance for the Computer Science Tripos PDF

Undergraduate Research Opportunities Programme (UROP) Link

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.

Lecture handout

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.

Supervisions

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

Microchallenges

2014-01-31: segmented least squares

My heroes!

• Charlie Barton
• Daria Dicu
• Isaac Dunn
• Gabor Igloi
• Gabriela Sklencarova
• Lauren Pick

...and, shortly after the deadline, also...

• Siddhant Jayakumar
• Daniel Wong

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.