Course pages 2019–20

# Algorithms

## Lectures

Mon-Wed-Fri 1000-1100 in Arts School A, from Fri 2020-01-17 to Wed 2020-03-11 inclusive (12 with FMS + 12 with DJW = 24 lectures).

## Handouts and other resources

Spare copies of handouts are available at student reception at the Computer Laboratory.

**Course handout**for lectures 1–12, distributed in lecture 1**Course handout 2**for lectures 13–19, distributed in lecture 13**Course handout 3**for lectures 20–24, distributed in lecture 20

**Examinable material**for lectures 13–24**Code snippets**on Azure Notebooks, updated as the course proceeds**Slides**for lectures 13– are on Moodle- Video for section 6.1 (max-flow min-cut)

## Example sheets

**Examples for lectures 1–12****Example sheet 5**(graph traversal, path finding)**Example sheet 6**(flows, subgraphs)**Example sheet 7**(amortized analysis, heaps)**Example sheet 8**(revision questions)

## Ticks

Submission instructions are on Moodle.

Tick 1 ∗ Tick 1* ∗ Tick 2 ∗ Tick 2* ∗ Tick 3 ∗ Tick 3* ∗ Tick 4*

## Errata Corrige

Negative lines counted from bottom of page.

### Handout for lectures 1-12 (rev 13)

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

(1)65 | 22 | 4.45 | 3.92 | 2020-02-03 | Tom Quinnell |

(1)68 | 8 | until it's 6 bits long | until it's 5 bits long | 2020-02-03 | Chua Xian Wei |

(1)75 | -11 | bcde", we simply pick | abcde", we simply pick | 2020-01-30 | Author |

(1)96 | 8 | The maximum and minimum | The minimum and maximum | 2020-02-05 | Alex Huntley |

(2)2 | A cycle is a path ... | A cycle should not be allowed to repeat edges, nor vertices (except for the start and end). Otherwise, the definition of forest doesn't make sense. | 2020-02-14 | A. Student | |

(2)4 | we'll see it visit B,E,F,A,C,D,G | B,E,F,G,A,C,D | 2020-02-13 | Author | |

(2)36 | Let the there be | Let there be | 2020-02-15 | D. Cordeiro |

## Hard-to-find reference material

### The Algorithm March

Take a step forward! Fall in

Take a step! Like a VIP!

Just turn around and take a bow!

Walk to the side! Keep looking looking!

Move your arms like the breast stroke then

Bend and pick up a chestnut again

Put some air in the flat tyre!

Full of air now! Whoosh! Whoosh!

It's about time now to end (x3)

It's the end