## Guide to examinable materialA guide to examinable material can be downloaded here.## CourseworkThe coursework is available here.Deadline is December 15.
## Some thoughts about the course
We are also experimenting with You can also email us with questions or pop by to the office hours. We will also be using the CS department unit discussion forum. This can provide a useful way for you to help each other and to get questions answered by the lecturers. Feel free to post questions and so on; we'll try to answer them as soon as possible. There are also excellent external question and answer websites which are directly relevant to university students. I particularly recommend CS stackexchange and Math stackexchange. ## Notes
The course structure is correct for 2013/2014. This year we will be providing full slides with both on-screen and printer friendly versions. The print slides should provide a good set of notes. To avoid confusion, the notes from previous years have been removed. |
Muhammad ibn Musa-al-Khwarizmi |

Lecture | Topic | Slides (2013/2014) | Readings |

1(02/10) |
Mathematical preliminaries | [print|screen] | MIT Course Notes 10–13 (up to the end of Section 2). See also CLRS, Appendix C.1–C.3 |

2(04/10) |
Hash functions | [print|screen] | MIT Notes covering lectures 2,3 and 4. CLRS 11.3.3, MU p. 90–93, 314–328 |

3(09/10) |
Static perfect hashing | [print|screen] | CLRS 11.5 |

4(11/10) |
Cuckoo hashing | [print|screen] | Cuckoo hashing for undergraduates. |

5(16/10) |
Bloom filters | [print|screen] | MU p. 109–111, 329, MIT notes, and Bloom filter survey. |

6(18/10) |
Van Emde Boas trees | [print|screen] | CLRS, Chapter 20 Notes 1, notes 2. |

7(23/10) |
Orthogonal range searching | [print|screen] | BCKO, Ch. 5, External Notes (based on BCKO, Ch. 5) |

8(25/10) |
Suffix trees | [print|screen] | External notes I and External notes II. See also Gusfield, Part II More on suffix trees, see External notes III. |

9(30/10) |
Suffix arrays | [print|screen] | Gusfield p. 149–156. Section 3 of this paper. This comparison of three methods. |

10 (01/11) |
Range Minimum Queries (RMQ) | [print|screen] | Simplified LCA paper |

11 (06/11) |
Lowest common ancestor (LCA) | [print|screen] | |

12 (08/11) |
Approximate pattern matching (part one) | [print|screen] | No external notes. |

13 (13/11) |
Approximate pattern matching (part two) | [print|screen] | No external notes. |

14 (15/11) |
Linear Programming | [print|screen] | DPV 7.1, 7.4 |

15 (20/11) |
Maximum flow and minimum cut | [print|screen] | CLRS, Chapter 26 (p.708–727) DPV 7.2, 7.3 |

16 (22/11) |
P, NP and constant factor approximations | [print|screen] | No external notes. |

17 (27/11) |
Further constant factor approximations | [print|screen] | No external notes. |

18 (29/11) |
(Fully) Polynomial time approximation schemes | [print|screen] | No external notes. |

19 (04/12) |
Asymptotic Polynomial time approximation schemes | [print|screen] | Slides - the Director's Cut. |

20 (06/12) |
Approximation using Linear Programming | [print|screen] | No external notes. |

21 (11/12) |
Deterministic Communication Complexity | [print|screen] | External notes |

22 (13/12) |
Randomised Communication Complexity | [print|screen] | External notes |

23 (18/12) |
Revision Lecture | TBA | TBA |

24 (20/12) |
Christmas guest lecture | TBA | TBA |

[DPV] S. Dasgupta, C.H. Papadimitriou and U.V. Vazirani.
*Algorithms*.
ISBN: 978-0073523408.
McGraw-Hill, 2006.

[Gusfield] D. Gusfield.
*Algorithms on Strings Trees and Sequences*. CUP 1997.

[MU] M. Mitzenmacher and E. Upfal.
*Probability and Computing*. CUP 2005.

[BCKO] M. de Berg, O. Cheong, M. van Kreveld, M. Overmars.
* Computational Geometry*. Springer 2010.