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
If you don't understand something - We think it's best to ask at the time, in the lecture or at the end if you prefer. We're very happy to explain things again. This is an advanced course (it even says so in the title) so if something isn't clear to you, you probably aren't the only one.
We are also experimenting with exciting new cutting edge teaching methods™ - we are attending each other's lectures. We've found in the past that this is surprisingly popular. Basically it just means you'll have to hear, say Ben, saying "I didn't understand that" in Markus' lectures, and vice versa.
You can also email us with questions or pop by to the office hours. Top tip: Come to the office hours! We think it's a good way to get one-on-one assistance if you are having trouble understanding something.
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.
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
|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.