Computer Laboratory

Course pages 2014–15

Algorithms

Lectures

Mon-Wed-Fri 1000-1100 in Arts School A, from 2014-01-16 to 2014-03-11.

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. Write to the author if you discover any errors.

Slides

A printed (and condensed) version of all slides for Lectures 13-24 has been distributed during Lecture 13. An electronic copy is also available. The long versions will be made available after each lecture. Write to the author if you discover any errors. A list of corrections can be found here.

  • Lecture 13 (Amortized Analysis) PDF, 13/02/2015, Handout: pages 81-85, CLRS: Chapter 17.1, 17.2, 17.3
  • Lecture 14 (Fibonacci Heaps, Implementation and Operations) PDF, 16/02/2015, Handout: pages 86-92, CLRS: Chapter 19.1, 19.2, 19.3
  • Lecture 15 (Fibonacci Heaps, Amortized Analysis) PDF, 18/02/2015, Handout: pages 93-96, CLRS: Chapter 19.1, 19.2, 19.3
  • Lecture 16 (Disjoint Sets, Graph Representations) PDF, 20/02/2015, Handout: pages 97-103, CLRS: Chapter 21.1, 21.2, 21.3
  • Lecture 17 (Searching in Graphs (BFS and DFS), Spanning Trees) PDF, 23/02/2015, Handout: pages 104-108, CLRS: Chapter 22.2, 22.3, 23.1
  • Lecture 18 (Spanning Trees) PDF, 25/02/2015, Handout: pages 109-113, CLRS: Chapter 23.1, 23.2
  • Lecture 19 (Single-Source Shortest Paths: Bellman-Ford) PDF, 27/02/2015, Handout: pages 113-115, CLRS: Chapter 24.1
  • Lecture 20 (Single-Source Shortest Paths: Dijsktra, All-Pairs Shortest Paths: Matrix Multiplication, Johnson) PDF, 02/03/2015, Handout: pages 116-121, CLRS: Chapter 24.3, 25.1, 25.3
  • Lecture 21 (Maximum Flow: Greedy, Ford Fulkerson) PDF, 04/03/2015. Handout: pages 121-125, CLRS: Chapter 26.1, 26.2
  • Lecture 22 (Maximum Flow: Max-Flow Min-Cut Theorem, Analysis of Ford Fulkerson), PDF, 06/03/2015, Handout: page 121-125, CLRS: 26.2
  • Lecture 23 (Maximum Flow: Application to Matchings, Geometric Algorithms: Line Intersection) PDF, 09/03/2015, Handout: pages 126-129, CLRS: Chapter 26.2, Chapter 33.1
  • Lecture 24 (Geometric Algorithms: Convex Hull) PDF, 11/03/2015, Handout: pages 129-133, CLRS: Chapter 33.3

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 smooth out the transition, here is a legacy exercise sheet in pdf but new exercises will only be added to Otter from now on.

Past exam questions for Algorithms I, Algorithms II, Data Structures and Algorithms and Algorithms 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

2015-01-16: microchallenge 0

My heroes!

  • Silviu Daniel Ungureanu
  • Matthew Jadczak
  • Devan Kuleindiren
  • Andrej Ivašković
  • Alex Coplan
  • Stella Lau
  • Laszlo Makk
  • Milos Stanojevic
  • Momchil Peychev
  • Dimitrios Los

2015-01-19: microchallenge 1

My heroes!

  • Andrej Ivašković
  • Devan Kuleindiren
  • Gábor Szarka
  • Milos Stanojevic
  • Matthew Jadczak
  • Dimitrios Los
  • Laszlo Makk
  • Tudor Tiplea
  • Stella Lau
  • Richard Tynan
  • Suraj Patel
  • Momchil Peychev

2015-01-23: Algorithms Tick

See the dedicated tab. Everybody on this course must do the tick, unlike the microchallenges which are only for those who are really keen. Information about getting a star.

2015-01-24: crowd-sourced peer review meta-microchallenge 1

My heroes²!

  • Gábor Szarka
  • Milos Stanojevic
  • Matthew Jadczak
  • Laszlo Makk
  • Tudor Tiplea
  • Stella Lau
  • Richard Tynan
  • Momchil Peychev

2015-01-30: microchallenge 2

My heroes!

2015-02-06: microchallenge 3

My heroes!

2015-02-18: puzzle 4

My heroes!

  • Peerasak Sae-Ung
  • Gábor Szarka
  • Alastair Holmes
  • Patrik Turzák
  • Ryan Lau
  • Stella Lau
  • Milos Stanojevic

2015-02-20: microchallenge 5

Fibonacci Heap Microchallenge, Problem and Solution: PDF

My heroes!

2015-02-27: microchallenge 6

Directed Graph and Outcome of DFS PDF

My heroes!

2015-03-06: microchallenge 7

Problem and Solution PDF

My heroes!

  • Alex Dalgleish
  • Andrej Ivašković ★
  • Stella Lau ★
  • Momchil Peychev ★
  • Milos Stanojevic ★
  • Gábor Szarka ★

Instructions for lecturers: how to edit this page