Algorithms and Data Structures

Introduction

In 2023/24 Algorithms and Data Structures will be taught during Semester 1 by Dr. Richard Mayr.

Timetable: The ADS course starts in week 1 of semester 1. (First lecture on Monday 18. Sep.) Lectures Mondays 16:10-17:00, South College Street, SCS_Newhaven Lecture Theatre and Thursdays 16:10-17:00, 50 George Square, 50GS_G.06. 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, pre-requisites, 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 2 level, and are strong in Maths. Students should have good grades in DMP 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. Tutorial group 02 (Wednesdays) does not take place, so attend groups 01 or 03. For assignments of students to tutorial groups see the LEARN page of ADS 2023/24.

Tutorial sheets and solutions can be downloaded here. (Solutions go up about a week later).

Exercises to be discussed in Week 3. Solutions for week 3.
Exercises to be discussed in Week 4. Solutions for week 4.
Exercises to be discussed in Week 5. Solutions for week 5.
Exercises to be discussed in Week 6. Solutions for week 6.
Exercises to be discussed in Week 7. Solutions for week 7.
Exercises to be discussed in Week 8. Solutions for week 8.
Exercises to be discussed in Week 9. Solutions for week 9.
Exercises to be discussed in Week 10. Solutions for week 10.

Lectures

Lecture recordings are available on the LEARN page of ADS.

Lecture 1: lec1.pdf (for viewing), lec1-nup.pdf (for printing).
Lectures 2 and 3: lec2.3.pdf (for viewing), lecture2.3-nup.pdf (for printing).
Lecture 4 lec4.pdf (for viewing), lecture4-nup.pdf (for printing).
Lectures 5 and 6: lec5.6.pdf (for viewing), lecture5.6-nup.pdf (for printing). Supplement on FFT (by Mary Cryan)
Lecture 7 lecture7.pdf (for viewing), lecture7-nup.pdf (for printing).
Lecture 8 lecture8.pdf (for viewing), lecture8-nup.pdf (for printing).
Lecture 9 lecture9.pdf (for viewing), lecture9-nup.pdf (for printing).
Lectures 10-11 lecture10.11.pdf (for viewing), lecture10.11-nup.pdf (for printing).
Lectures 12-13 lecture12.13.pdf (for viewing), lecture12.13-nup.pdf (for printing).
Lectures 14-15 lecture14.15.pdf (for viewing), lecture14.15-nup.pdf (for printing).
Lecture 16 lecture16.pdf (for viewing), lecture16-nup.pdf (for printing).
Lectures 17-18 lecture17.18.pdf (for viewing), lecture17.18-nup.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 23/24 under Section: Assessment.
- Out: 29. Sep. 2023.
- DUE 19. Oct. 2023 (12 noon).
- FEEDBACK: 2. Nov. 2023.
Coursework 2: (summative, counts for 25 percent of course mark). Available on the LEARN page of ADS 2023/24 under menu item Assessment.
- Out: 27. Oct. 2023.
- DUE 16. Nov. 2023 (12 noon).
- FEEDBACK: 30. Nov. 2023.

References

(*) Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms (3nd Edition). McGraw-Hill, 2002. Our course text
Kleinberg and Tardos: Algorithm Design. Addison-Wesley, 2005.
Gibbons: Algorithmic Graph Theory. Cambridge University Press, 1985.
Sedgewick: Algorithms in C (Part 1-5), Addison Wesley, 2001.

Home : Teaching : Courses

Richard Mayr. IF 4.11a.