Computer Laboratory

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.

PageLineErrataCorrigeFound onby
4414used 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-30author
4422We can then either use recursion[Add this footnote.]2013-04-30author
50-9[formula of 27346 mod 7][Every binary operation in the formula (say a @ b) must be converted not just to
a 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-09Hauke Neitzel
5111where 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-06author
54-10y is shortery is not longer2013-05-05author

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)

Valid XHTML 1.0 Strict