Design and Analysis of Algorithms:  2021-2022

Overview

This core course covers good principles of algorithm design, elementary analysis of algorithms, and fundamental data structures. The emphasis is on choosing appropriate data structures and designing correct and efficient algorithms to operate on these data structures.

Learning outcomes

This is a first course in data structures and algorithm design. Students will:

• learn good principles of algorithm design;
• learn how to analyse algorithms and estimate their worst-case and average-case behaviour (in easy cases);
• become familiar with fundamental data structures and with the manner in which these data structures can best be implemented; become accustomed to the description of algorithms in both functional and procedural styles;
• learn how to apply their theoretical knowledge in practice (via the practical component of the course).

Synopsis

• Program costs: time and space. Worst case and average case analysis. Asymptotics and "big O" notation. Polynomial and exponential growth. Asymptotic estimates of costs for simple algorithms. Use of induction and generating functions. [2]
• Algorithm design strategies: top down design, divide and conquer. Application to sorting and searching and to matrix algorithms. Solution of relevant recurrence relations. [4]
• Data structures and their representations: arrays, lists, stacks, queues, trees, heaps, priority queues, graphs. [3]
• Introduction to discrete optimisation algorithms:  dynamic programming, greedy algorithms, shortest path problems. [3]
• Graph algorithms: examples of depth-first and breadth-first search algorithms. Topological sorting, connected components. [3]

Syllabus

Basic strategies of algorithm design: top-down design, divide and conquer, average and worst-case criteria, asymptotic costs. Simple recurrence relations for asymptotic costs. Choice of appropriate data structures: arrays, lists, stacks, queues, trees, heaps, priority queues, graphs. Applications to sorting and searching, matrix algorithms, shortest-path and spanning tree problems. Introduction to discrete optimisation algorithms: dynamic programming, greedy algorithms. Graph algorithms: depth first and breadth first search.

Lectures

1. Program cost and asymptotic analysis - slides
2. Divide-and-conquer - slides
3. Data structures - heaps - slides
4. Dynamic programming - slides
5. Graph search - slides
6. Shortest path - slides
7. Greedy algorithm - slides
8. Matroids - slides
9. Stable matching - slides

Problem Sheets

There will be 4 sets of problems.

• Problem sheet 1 (answers to *-problems)
• Problem sheet 2 (answers to *-problems)
• Problem sheet 3 (answers to *-problems)
• Problem sheet 4 (answers to *-problems)

Practical materials

• Instructions
• Brack-skeleton.scala

Reading list

• T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein. Introduction to Algorithms, 3rd edition, MIT Press, 2009 (2nd edition [2001] or 1st edition, [1990] can be used as well). This is the main text book for this lecture course.
• J. Kleinberg and E. Tardos. Algorithm design. Addison-Wesley. First edition 2005, 2nd edition February 2022. 
• S. Dasgupta, C. Papadimitriou, and U. Vazirani. Algorithms. McGraw-Hill Higher Education. 2006

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.