Course pages 2012–13

# Algorithms I

**Principal
lecturer:** Dr Frank
Stajano

Email to the address frank.stajano--algs1 at cl cam
ac uk (a special address containing two consecutive hyphens) will be
given priority over that sent to other addresses.

## Syllabus

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.

### 2013-03-08 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-20.

### 2013-03-11 Mon (Other quadratic sorting; mergesort)

CLRS3: 2.3. You may skip chapters 4 and 5.

Handout: pages 21-27.

### 2013-03-13 Wed (Quicksort, order statistics)

CLRS3: 7.1, 7.2, 7.3, 9.1, 9.2. You may skip 7.4, 9.3.

Handout: pages 24-32.

### 2013-04-26 Fri (Heapsort)

CLRS3: 6.1, 6.2, 6.3, 6.4, (6.5 in a future lecture).

Handout: pages 33-36.

### 2013-04-29 Mon (Faster sorting; dynamic programming)

CLRS3: 8.1, 8.2, 8.3, 8.4, 15.2. You may skip 15.1.

Handout: pages 36-42.

### 2013-05-01 Wed (Dynamic programming)

CLRS3: 15.2, 15.3, 15.4. You may skip 15.1 and 15.5.

Handout: pages 42-43.

### 2013-05-03 Fri (Greedy algorithms; algorithm design strategies)

CLRS3: 16.1, 16.2. You may skip 16.3, 16.4 and 16.5.

Handout: pages 43-48.

### 2013-05-06 Mon (String matching)

CLRS3: 32.1, 32.2, 32.3.

Handout: pages 49-53.

### 2013-05-08 Wed (String matching; data structures)

CLRS3: 32.3, 10.2, 10.3, 10.4. You may skip 32.4.

Handout: pages 53-61.

### 2013-05-10 Fri (Abstract data types)

CLRS3: 10.1, 10.2.

Handout: pages 61-70.

### 2013-05-13 Mon (Binary search trees)

CLRS3: 12.1, 12.2, 12.3. You may skip 12.4.

Handout: pages 70-72.

### 2013-05-15 Wed (Red-black trees)

CLRS3: 13.1, 13.2, 13.3, 13.4.

Handout: 72-76.

### 2013-05-17 Fri (B-trees)

CLRS3: 18.1, 18.2, 18.3.

Handout: 76-79.

### 2013-05-20 Mon (Hash tables)

CLRS3: 11.1, 11.2, 11.4. You may skip 11.3 and 11.5.

Handout: 79-81.

### 2013-05-22 Wed (Priority queues)

CLRS3: 6.5.

Handout: 82-86.

## Lecture handouts

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 do not print it again yourself and please do not circulate it outside cam.ac.uk.

## Errata corrige

Negative line numbers are counted from the bottom of the page. Top line (excluding headers) is 1. Bottom line (excluding footers) is -1.

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

44 | 14 | used in dynamic programming.) | used in dynamic programming.) If, conversely, the optimal solution doesn't include ai, then by the same argument the union of ai, the optimal solution for SiL and the optimal solution for SiR is still the best solution we can produce that includes ai. | 2013-04-30 | author |

44 | 22 | We can then either use recursion | [Add this
footnote.] | 2013-04-30 | author |

50 | -9 | [formula of 27346 mod 7] | [Every
binary operation in the formula (say a @ b) must be converted not just
toa mod q @ b mod q but to((a mod q) @ (b mod q)) mod q, otherwise the result might reach or exceed
q.] | 2013-05-09 | Hauke Neitzel |

51 | 11 | where c is the number of actual matches of P in T. | where c is the number of times the residues match (whether true or false positives) while shifting P alongside T. | 2013-05-06 | author |

54 | -10 | y is shorter | y is not longer | 2013-05-05 | author |

If you find any more errors, please mail them to me and I'll credit you here and in the next version of the handout.

## Microchallenges

### 2013-05-06: segmented least squares

My heroes!

- Petar Veličković (C++)
- Mistral Contrastin (Ruby)
- Matej Hamas (Java)
- Artjoms Iskovs (Python)
- Herschel Chawdhry (Java)
- Abhishek Chander (Java)
- Jeppe Hallgren (C++)

*(code received shortly after the deadline also from...)*

- Zoltán Szenczi (Visual Basic)
- Darren Foong (C)

### 2013-05-13: binary search trees

My heroes!

- Petar Veličković (C++)
- Hauke Neitzel (Java)
- Artjoms Iskovs (Scheme)
- Chris Diamand (C++)
- Darren Foong (Java)