School of Informatics - 2021/22

Course Information

Content

  • Course Summary

    Algorithms and Data Structures (ADS) is a 10 credit course at Level 10, normally taken in Year 3. It runs in Semester 2. The exam is in , and is worth 75% of the course mark. The University descriptor is here.

  • Course Outline

    The webpage of the ADS course is http://www.inf.ed.ac.uk/teaching/courses/ads/

    Introductory concepts
    Review of CS2. Models of computation; time and space complexity; upper and lower bounds, big-O and big-Omega notation; average and worst case analysis.

    Divide and conquer
    Matrix multiplication: Strassen's algorithm; the discrete Fourier transform (DFT), the fast Fourier transform (FFT). Expressing the runtime of a recursive algorithm as a recurrence relation; solving recurrence relations.

    Sorting
    Quicksort and its analysis; worst-case, best-case and average-case.

    Data structures: Disjoint sets
    The "disjoint sets'' (union-find) abstract data type: specification and implementations as lists and trees. Union-by-rank, path-compression, etc., "heuristics''. Applications to finding minimum spanning trees.

    Dynamic programming
    Introduction to the technique; examples: Matrix-chain multiplication, Longest common subsequences.

    Graph/Network algorithms
    Network flow, Max-flow/min-cut theorem, Ford-Fulkerson algorithm.

    Geometric algorithms
    Convex hull of a set of points (in 2-d).

    Relevant QAA Computing Curriculum Sections: Data Structures and Algorithms

  • Timetable

    If you are looking for your class times for this course, these can be found via your University of Edinburgh calendar (links provided below):

  • Informatics Teaching Organisation: Information for Students

    You can also email the Informatics Teaching Organisation (ITO) at ito@inf.ed.ac.uk  or the Student Support Team (SST) at inf-sst@inf.ed.ac.uk.