COMS21103: Data structures and algorithms

The lecturers for this unit are:

Instructors	Office	Hours
Bogdan Warinschi	MVB-3.13	Friday 2:30 to 4:00
Markus Jalsenius	MVB-3.15	TBA
Dan Page	MVB-3.42a	Tuesday 14:00 to 16:00
Teaching assistants	Office	Hours
Jamie Hanlon	MVB-2.01	TBA
David Bernhard	MVB-3.22/3.42	Thursday 11:00 to 12:00

The timetables and room allocations for this unit are here:

Lectures: Thursday 15:00 Mott Lecture Theatre, Physics, Friday 10:00 B37 Lecture Theatre, Biological Science, Friday 12:10 in Mott Lecture Theatre
Problem Class: Tuesday 12:10 in QB 1.15

Textbook

The main textbook for this unit is:

T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein (referred to as CLRS in lecture notes).
Introduction to Algorithms.
MIT Press, 2001.

Lecture Notes

Week	Date	Material	Date	Material	Date	Material
1	Oct 13th	Introduction Summary	Oct 14th	Basic Math Prelims Summary	Oct 14th	Asymptotic Analysis (I) Summary
2	Oct 20th	Asymptotic analysis (II) Summary	Oct 21th	Recurrences (I) Summary	Oct 21th	Recurrences (II) Summary
3	Oct 27rd	Algorithm Correctness Summary	Oct 28th	Binary (MAX) Heaps CLRS - Chapter 6 -	Oct 28th	Priority Queues CLRS - Chapter 6 -
4	Nov 3th	Quiz	Nov 4th	Graph exploration algorithms Summary	Nov 4th	Graph exploration algorithms Summary
5	Nov 10th	Stable matching [slide\|print]	Nov 11th	MST + Shortest paths [slide\|print]	Nov 11th	Sorting revisited [slide\|print]
6	Nov 17th	Search structures [slide\|print]	Nov 18th	String matching [slide\|print]	Nov 18th	FFT and multiplication [slide\|print]
7	Nov 24th	FFT and multiplication [slide\|print]	Nov 25th	Order statistics [slide\|print]	Nov 25th	Bellman Ford [slide\|print]
8	Dec 1st	Dynamic programming [Chapter 6 of DPV]	Dec 2nd	Dynamic programming [Chapter 6 of DPV]	Dec 2nd	All pairs shortest path [slide\|print]
9	Dec 8th	Examples and case studies (PageRank) [ slides \| notes ]	Dec 9th	Implementation techniques (motivation) [ slides \| notes ] ("bare metal" programming) [ slides \| notes ]	Dec 9th	Implementation techniques (caches, buffers and friends) [ slides \| notes ]
10	Dec 15th	Implementation techniques (refactoring algorithmic constructs) [ slides \| notes ]	Dec 16th	Implementation techniques (refactoring algorithmic constructs) [ slides \| notes ] (specialisation and friends) [ slides \| notes ]	Dec 16th	Implementation techniques (specialisation and friends) [ slides \| notes ]
11	Jan 19th	Implementation techniques ("micro" data structures) [ slides \| notes ]	Jan 20th	Implementation techniques ("micro" data structures) [ slides \| notes ]	Jan 20th	Implementation techniques ("micro" data structures) [ slides \| notes ]
12	Jan 26th	Implementation techniques (latency hiding) [ slides \| notes ]	Jan 27th	Examples and case studies (chess) [ slides \| notes ]	Jan 27th	Examples and case studies (MapReduce) [ slides \| notes ]

Problems Sheets and Study guide

Part 1

Problems that cover the whole first part of the course as well as some sample proofs can be found in the Study Guide The following are specific problems that you should work on from one week to another.

Part 2

Problem sheets for the second part of the course are available here. Please attempt these sheets before the following Tuesday when they will be discussed.

Problem Sheet 1: Complex Numbers (Answers)
Problem Sheet 2: Stable matching and Dijkstra's algorithm (Answers)
Problem Sheet 3: Sorting and Searching (Answers)
Problem Sheet 4: Skipping, Multiplying and Independence (answers will be available later)
Problem Sheet 5: "never odd or even" (answers will be available later)

Coursework Assignments

Coursework 1. The deadline is Friday 13 January 2012. Code snippets (Fig.1 and Fig.2): Complex.java and Cwk1Problem1.java.
Coursework 2. The deadline is Friday 27 January 2012.

Support

It is important to effectively utilise the various forms of support available for this unit; see the page about communication in the department for a general introduction.

Labs and Help Desk: There are no timetabled lab sessions for this unit; this is a departmental policy in relation to study within the second and later years. The lack of lab sessions means it is even more important to utilise the other forms of support available, for example the help desk (Mondays and Tuesdays 12:00--14:00, Thursdays 13:00--15:00) in MVB room 2.11 should be the first point of contact for programming queries.

Forum: The forum can provide a useful way for you to help each other and to get questions answered by other students, the teaching assistant or the lecturers, all of whom will take part in online discussions:

COMS21103 Forum

You are encouraged to post questions to the forum and also offer any advice you have on the material in the unit. However, please be careful not to give answers to the coursework questions. Before you use the forum to ask a question you should make sure you have first tried to help yourself by reading lecture slides and course texts for example.

Office Hours: The lecturers set office hours where they guarantee to be in their offices to help you. You are welcome to drop in during those times to discuss any aspect of the unit. At other times, please use the forum or contact the TA for assistance. However, do first carefully check the recommended text book (CLRS) and the online book (DPV) and also the lecture notes where you will find most answers to common questions.

Email: Email is very useful for the lecturers to contact all of you, but it isn't so useful for you to contact the lecturers. They often get completely swamped with emails, so use of the forum is preferred for any questions. Following this policy for all but vital (or personal) problems will hopefully ensure common questions and answers are quickly made available to everyone.

Feedback: Like some other units, some of the coursework assignments in this unit are automatically marked. This means the feedback will be fast but of a fairly low quality. Some assignments (in particular those with a written component) will not be automatically marked. This means the feedback will be slower but of a higher quality. In particular we aim to provide a model answer as well as individual feedback. If you need additional feedback, please seek this via the routes above.

Links and Resources

There are a number of good online resources that will act as a refresher for various topics in the unit:

Introductory material on mathematics for computer science from MIT (course 6.042).
Introductory material on complex numbers from Brigham Young University.
Advice on writing and reasoning about proofs.
Online tutorials for Haskell, C and Java (the "Haskell for C programmers" tutorial is particularly good).
Advice on how to be a programmer.

There are also plenty of online resources that could help you find out more about topics covered in the unit:

We have a locally mirrored copy of a brilliant quick reference guide for theoretical computer science:

S.S. Seiden.
Theoretical Computer Science Cheat Sheet.
ACM SIGACT News 27(4), 52-61, 1996.

Copies of some useful new (preprint) and old (out of print) books can be found online:

S. Dasgupta, C.H. Papadimitriou and U.V. Vazirani (referred to as DPV in lecture notes).
Algorithms.
McGraw-Hill, 2006.