Skip to main content

COMS31900: Advanced Algorithms, 2013/2014

Lecturers Office Hours
Markus Jalsenius MVB 3.36 Fridays 10am-12pm
Benjamin Sach MVB 3.36 Fridays 10am-12pm
Teaching Assistant Office Hours
Dan Martin Room MVB-3.22 Mondays 2-3pm

Lecture Time Location
Wednesdays 12pm Queen's Building: 1.69
Fridays 2pm Queen's Building: 1.8

Guide to examinable material

A guide to examinable material can be downloaded here.

Coursework

The 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.

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.



There are also links to external notes and book references in the "Readings" column. Full book titles (for CLRS, MU etc.) and refernces are given at the bottom of the page. Note that the algorithms text DPV is freely available (as an online draft, via the link below)

Muhammad ibn Musa-al-Khwarizmi
(c. 780-850)


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

Links and Resources

[CLRS] Cormen, Leiserson, Rivest and Stein. Introduction to Algorithms (3rd Edition). MIT Press. ISBN: 978-0262533058

[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.

Mathematics review from MIT

Compendium of NP-complete optimisation problems