Algorithms and Data Structures
Introduction
In 2021/22 Algorithms and Data Structures will be taught during Semester 2
by Dr. Richard Mayr.
Timetable: The ADS course starts in week 1 of semester 2.
Lectures Mondays (17:1018:00, AT Lecture Theatre 4) and
Thursdays (9:009:50, Bayes Center G.03).
See Timetable in DRPS.
ADS teaches material important for research in Computer Science,
and for the Database and Web Search industries.
 The DRPS entry for ADS (including syllabus, prerequisites, etc) is
here.
Note that ADS is now a level 10 course, therefore 4th year
undergraduates who did not previously take ADS may take it this year.
It is still primarily a 3rd year course.
 We assume the students know and are confident with
Algorithms/Data Structures to Inf 2B level, and are strong in Maths.
Students should have good grades in DMMR and Probability or an
alternative year 2 Maths programme, and should be comfortable with
doing proofs.
(Inf2B notes
here for reference)
 ADS is assessed with coursework (25%) and a final exam (75%).
There will be 1 formative coursework during semester (feedback
will be returned to students, but the work will not count for
assessment), and a 1 summative coursework (contributing 25% of the
course mark) later in the semester (see below).
Tutorials
Tutorials start in week 3.
Times and dates of tutorials can be found under the
timetable in DRPS.
For assignments of students to tutorial groups see
the LEARN page of ADS 2021/22.
Tutorial sheets and solutions can be downloaded here. (Solutions go up about a week later).
Lectures
 Lecture 1:
lec1.pdf (for viewing),
lec1nup.pdf (for printing).
 Lectures 2 and 3:
lec2.3.pdf (for viewing),
lecture2.3nup.pdf (for printing).
 Lecture 4
lec4.pdf (for viewing),
lecture4nup.pdf (for printing).
 Lectures 5 and 6:
lec5.6.pdf (for viewing),
lecture5.6nup.pdf (for printing).
Supplement on FFT (by Mary Cryan)
 Lecture 7
lecture7.pdf (for viewing),
lecture7nup.pdf (for printing).
 Lecture 8
lecture8.pdf (for viewing),
lecture8nup.pdf (for printing).
 Lecture 9
lecture9.pdf (for viewing),
lecture9nup.pdf (for printing).
 Lectures 1011
lecture10.11.pdf (for viewing),
lecture10.11nup.pdf (for printing).
 Lectures 1213
lecture12.13.pdf (for viewing),
lecture12.13nup.pdf (for printing).
 Lectures 1415
lecture14.15.pdf (for viewing),
lecture14.15nup.pdf (for printing).
 Lecture 16
lecture16.pdf (for viewing),
lecture16nup.pdf (for printing).
 Lectures 1718
lecture17.18.pdf (for viewing),
lecture17.18nup.pdf (for printing).
(This is the last lecture.)
Coursework and Feedback
Two courseworks (out of 100 marks each), one formative, one summative
(25 percent of course grade).

Coursework 1: (formative)
Available on the LEARN page of ADS 21/22 under Section: Assessment.
 Out: 28. Jan. 2022.
 DUE Friday, 18. Feb. 2022 (4pm).
 FEEDBACK: 7. March 2022.

Coursework 2: (summative, counts for 25 percent of course mark).
Available on the LEARN page of ADS 2021/22 under menu item Assessment.
 Out: 4. March 2022.
 DUE Friday, 25. March 2022 (4pm).
 FEEDBACK: 11. April 2022.
References
 (*) Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms
(3nd Edition). McGrawHill, 2002. Our course text
 Kleinberg and Tardos: Algorithm Design. AddisonWesley, 2005.
 Gibbons: Algorithmic Graph Theory. Cambridge University
Press, 1985.
 Sedgewick: Algorithms in C (Part 15), Addison Wesley, 2001.
Home : Teaching : Courses
Richard Mayr.
IF 4.11a.