Course pages 2016–17

# Algorithms

## Lectures

Mon-Wed-Fri 1000-1100 in Mill Lane Lecture Room 9, from Fri 2017-01-20 to Wed 2017-03-15 inclusive (12 with FMS + 12 with DJW = 24 lectures).

## Lecture handout

**For lectures 1–12:**Distributed during the first lecture. A [pdf] is also available. Write to the author if you discover any errors and you'll be credited in the next edition.**For §5.1–5.10:**Distributed in lecture 13, and available as [pdf]**For §5.11–5.13:**Distributed in lecture 17, and available as [pdf]**For §6:**Distributed in lecture 20, and available as [pdf]**For §7:**Distributed in lecture 24, and available as [pdf]- Dijkstra's algorithm

It will be to your advantage to bring the handouts to every lecture, together with a notebook with non-detachable pages and a few coloured pens. Further printed copies of the handouts are available from the student administration office in the William Gates Building.

### Errata Corrige

Negative lines counted from bottom of page.

Page | Line | Errata | Corrige | Reported on | by |
---|---|---|---|---|---|

70 | -7 | rotated is n edge | rotated is an edge | 2017-02-06 | author |

102 | 11 | If it hasn't | If it isn't | 2017-05-03 | author |

§5.6 | Problem statement | for every pair of vertices | for every vertex v compute the weight of the minimal-weight path from s to v | 2017-02-17 | Jakub Perlin |

Example sheet week 5 | Question 5 | O(V+E) | O(E+V log V) | 2017-02-20 | |

Example sheet week 5 | Question 6 | `assert w.active == True` |
`assert (w.active == True) or (w is not v's first neighbour)` |
2017-02-24 | Adam Kucz |

§5.10 | top of page | Kruskal [...] has the same running time [as Prim's algorithm] | Delete the comment about running time | 2017-03-01 | |

§5.12, in Graphs part 2 Page 6 | half way down | either f(v→w)<c(v→w) or f(v→w)>0 |
either f(v→w)<c(v→w) or f(w→v)>0 |
2017-03-01 | |

§5.12, in Graphs part 2 Page 8 | 3rd paragraph | total running time is O(E V F^{*}) |
total running time is O(E f^{*}) |
2017-03-03 | |

§6.2, in Adv.Data Page 7 | line 6 of code snippet | `newroots[x.degree] = null` |
`newroots[x.degree-1] = null` |
2017-03-08 | A. Student |

§6.2, in Adv.Data page 8 | equations for total amortized cost | -Φ(S_{0})+c_{1}+Φ(S_{0}) |
-Φ(S_{0})+c_{1}+Φ(S_{1}) |
2017-03-08 | A. Student |

§6.2, in Adv.Data page 8 | equations for total amortized cost | +Φ(S_{0})-Φ(S_{k}) |
-Φ(S_{0})+Φ(S_{k}) |
2017-03-08 | A. Student |

§6.1, in Adv.Data page 3 | line 17 of code snippet | `making the smaller child a root of the larger` |
`making the larger child a root of the smaller` |
2017-04-09 | J. Perlin |

§7.2, in Geometry page 3 | description of algorithm | If two points have the same smallest angle, use the one that's furthest from p |
If two points have the same smallest angle, use the one that's furthest from q |
2017-05-30 | J. Hargreaves |

## Supervisions

We are happy when people use the homebrew online Otter system, which is still somewhat experimental. Please help us make it work for you by providing constructive feedback on how it could be improved. Alternatively, here are exercise sheets in pdf.

- Legacy exercise sheet, covering the first half of the course [pdf]
- Exercise sheet for week 5 [pdf]
- Exercise sheet for week 6 [pdf]
- Exercise sheet for weeks 7/8 [pdf]
- Exercise sheet for week 8 [pdf]

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

### If you are a supervisor

Thanks for supervising. Please email frank dot stajano hyphen hyphen algs @cl.cam.ac.uk with your CRSID and ask your supervisor to tell Frank that she or he agrees that you should be supervising this course. You will then be granted access to the "information for supervisors" tab and added to the list of people who should know about supervisor-relevant stuff.

## Microchallenges

### 2017-01-30: microchallenge 1

**My heroes!**

- Sompob Shanokprasith
**Alicja Chaszczewicz***- Krzysztof Zamarski
**Vlad Badelita**- Huiyao Zheng *
- Martin Gazo
- Matteo G. Pozzi

...and also these latecomers...

- Adam Kucz *
- Zhipeng Wang

### 2017-02-06: microchallenge 1 bis

**My heroes!**

- Vlad Badelita
**Zhipeng Wang**- Sompob Shanokprasith
- Huiyao Zheng *
- Alicja Chaszczewicz *
**Adam Kucz*****Matteo G. Pozzi**- Krzysztof Zamarski

### 2017-02-10: microchallenge 2

**My heroes!**

**Zijun Joe Yan**- David Chong
- Alicja Chaszczewicz *
- Huiyao Zheng *
- Keith Collister
- Adam Kucz *

### 2017-02-13: microchallenge 3

**My heroes!**

- Jesús Arjona Martínez
**Thien Thanh BUI (Albert)**- Thomas Gessey-Jones
- Sean Seet
- Alonso J. Campos-Hernandez
**Zhipeng Wang**- David Chong
- Huiyao Zheng *
- Dan Seremet
- Adam Kucz *
- Alicja Chaszczewicz *
**István Kádár**- Krzysztof Zamarski