Algorithms and Data Structures

Introduction

Algorithms and Data Structures was taught in Semester 1 by Dr Mary Cryan.

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
The "trailer" for ADS can be found here
We assume a level of knowledge up to Inf 2B level, Inf2B notes here for reference.

News (update 12th Dec)

Please fill in a feedback form for ADS.
Lecture Log I have filled in the gaps in the log, and also added some scans of ``board proofs".
office hours: 11am-12 on Mondays and Fridays, in IF 5.16 (top floor of Forum).

Tutorials

Tutorial group allocation is here. Tutorial sheets and solutions (sols go up the following week):

Sheet for Week 3 (Tues 4th - Fri 7th, Oct). sols3.pdf.
Sheet for Week 4 (Tues 11th - Fri 14th, Oct). sols4.pdf.
Sheet for Week 5 (Tues 18th - Fri 21st, Oct). sols5.pdf.
Sheet for Week 6 (Tues 25th - Fri 28th Oct). sols6.pdf.
Sheet for Week 7 (Tues 1st - Fri 4th Nov). sols7.pdf.
Sheet for Week 8 (Tues 8th - Fri 11th Nov). sols8.pdf.
Sheet for Week 9 (Tues 15th - Fri 18th Nov). sols9.pdf.
Sheet for Week 10 (Tues 22nd - Fri 25th Nov). sols10.pdf.

Lectures

I will update the Lecture Log as we progress (final update 13th Dec).

Lecture 1 (Fri, 23 Sept) Introduction to ADS lec1.pdf (for viewing), lec1-4.pdf (for printing).
Lecture 2 (Tues, 27 Sept) Asymptotic Notation, Recurrences lec2.pdf (for viewing), lec2-4.pdf (for printing). (Corrected on 12th Dec)
Lecture 3 (Fri, 30 Sept) Strassen's Algorithm lec3.pdf (for viewing), lec3-4.pdf (for printing).
A (in pdf) discussion of the relationship between Divide-and-Conquer and the Master Theorem is here.
Lectures 4 and 5 (Tues, 4 Oct and Fri, 7th Oct): Fast Fourier Transform: lec4.5.pdf (for viewing), lec4.5-4.pdf (for printing), notes on FFT.
Lecture 6 (Tues 11th Oct): Average-case analysis of Quicksort: lec6.pdf (for viewing), lec6-4.pdf (for printing).
Lecture 7 (Fri, 14 Oct): Lower Bounds for Sorting: lec7.pdf (for viewing), lec7-4.pdf (for printing).
Board proof (very detailed) of average-case depth of a leaf here (added 9 Dec).
Lecture 8 (Tues, 18 Oct): Counting sort, Radix sort lec8.pdf (for viewing), lec8-4.pdf (for printing).
Lecture 9 (Fri, 21 Oct): Dynamic programming; Matrix-chain multiplication problem lec9.pdf (for viewing), lec9-4.pdf (for printing).
some notes on DP (from a previous session). Added 12 Dec.
Tues, 25th Oct: NO ADS LECTURE TODAY
Lecture 10 (Fri, 28 Oct): Minimum Spanning Trees I lec101112.pdf (for viewing), lec101112-4.pdf (for printing).
Lecture 11 (Tues, 1 Nov): Minimum Spanning Trees II
Lecture 12 (Fri, 4 Nov): Minimum Spanning Trees III
BOARD NOTE on correctness of Kruskal's Algorithm here (added 9 Dec).
Lecture ? (Tues, 8 Nov): Finishing MSTs
Lecture 13 (Fri, 11 Nov): Network Flow I lec1314.pdf (for viewing), lec1314-4.pdf (for printing).
Lecture 14 (Tues, 15 Nov): Network Flow II
Lecture 15 (Fri, 18 Nov): Computational Geometry lec15.16.pdf (for viewing), lec15.16-4.pdf (for printing).
Proof of Lemma 1: notes (in txt), case1.pdf picture
Lecture 16 (Tues, 22 Nov): Computational geometry 2

Coursework

Two courseworks worth 50 marks each, due on Friday, 21st Oct and Friday, 18th Nov at NOON.

Coursework 1: was due to the ITO on 21st Oct at noon.
Solutions, marking rules, and key points for Coursework 1: cwk1sols.pdf
Coursework 2: was due to the ITO on 22nd Nov at NOON (extended date). Solutions, marking scheme, some key points for cwk2 is here.

References

Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms (2nd Edition). McGraw-Hill, 2002.
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.
The book by Cormen et al. is our course text. The book by Kleinberg and Tardos is a nice alternative which unfortunately does not cover all of the topics in this course.

Home : Teaching : Courses

Mary Cryan, mcryan AT inf DOT ed DOT ac DOT uk, IF 5-16, ext. 505153