ALG | Algorithmics |
This course overviews the fundamental concepts and results underlying the science of computing. It will provide both an introduction to algorithm design, discussing concrete algorithms and data structures, and an investigation into the limits of mechanization (intractability and noncomputability). The course addresses the needs both of professional programmers and students with little or no programming background. The style of presentation will make intensive use of visual techniques, complementing the traditional programmatic approach to algorithmics.
Frequency
This course normally runs twice a year.
Course dates
17th February 2025 | Oxford University Department of Computer Science - Held in the Department | 0 places remaining. |
6th October 2025 | Oxford University Department of Computer Science - Held in the Department | 08 places remaining. |
23rd February 2026 | Oxford University Department of Computer Science - Held in the Department | 18 places remaining. |
Objectives
At the end of the course, students will we able to solve algorithmic problems using a range of methods. They will know concrete algorithms and a variety of different data structures. They will also be aware of problems that computers cannot solve.
Contents
Contents
1. Introduction and Historical Review
2. Algorithms and Data
- Elementary Data Structures: lists and arrays
3. Programming Languages and Paradigms
4. Algorithmic Methods
- Design of Algorithms by Induction
- Divide and Conquer
- Greedy Algorithms
- Dynamic Programming and Memoization
5. Correctness of Algorithms
6. Efficiency of Algorithms
- Sorting: comparison-based sorting, sorting networks, key-based sorting
- Searching: comparison-based searching, key-based searching
- Order Statistics and Priority Queues
- Graph Algorithms
- Computational Geometry
7. Inefficiency and Intractability
8. Noncomputability and Undecidability
9. Algorithmic Universality and its Robustness
Requirements
There are no prerequisites, though some familiarity with programming (in any language) will be helpful.