Advanced Data Structures and Algorithms: 2012-2013
Lecturer | |
Degrees | Schedule S1(3rd years) — Computer Science |
Term | Hilary Term 2013 (16 lectures) |
Overview
This course builds on the first-year Design and Analysis of Algorithms course. It introduces students to a number of highly efficient algorithms and data structures for fundamental computational problems across a variety of areas. Students are also introduced to techniques such as amortised complexity analysis. As in the first-year course, the style of the presentation is rigorous but not formal.Learning outcomes
On successful completion of the course students will:
- Be able to understand and apply amortised analysis on data structures, including binary search trees, mergable heaps, and disjoint sets.
- Understand the implementation and complexity analysis of fundamental algorithms such as RSA, primality testing, max flow, discrete Fourier transform.
- Have an idea of applications of algorithms in a variety of areas, including linear programming and duality, string matching, game-theory
Synopsis
- Amortised analysis
- Disjoint sets / union-find
- Binary search trees
- Mergeable heaps
- Number theoretic algorithms + RSA
- Fast Fourier transform
- Linear programming
- Max flow in networks
- String matching
- Approximation algorithms
- Stable matching
Syllabus
- Amortised analysis
- Disjoint sets / union-find
- Binary search trees
- Mergeable heaps
- Number theoretic algorithms + RSA
- Fast Fourier transform
- Linear programming
- Max flow in networks
- String matching
- Approximation algorithms
- Stable matching
Reading list
The main text used in the course is:
- Thomas Cormen, Charles Leiserson, Ronald Rivest and Clifford Stein, Introduction to Algorithms, MIT Press, 2009 (third edition).
Other usefull textbooks that cover some of the material are
- S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Algorithms, Mcgraw-Hill, 2006.
- J. Kleinberg and E. Tardos, Algorithm Design, Addison-Wesley, 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.