University of Oxford Logo University of OxfordSoftware Engineering - Home
On Facebook
Facebook
Follow us on twitter
Twitter
Linked in
Linked in
Google plus
Google plus
Digg
Digg
Pinterest
Pinterest
Stumble Upon
Stumble Upon
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.

Course dates

15th January 2018Oxford University Department of Computer Science 0 places remaining.
9th July 2018Oxford University Department of Computer Science 0 places remaining.
25th February 2019Oxford University Department of Computer Science07 places remaining.
5th August 2019Oxford University Department of Computer Science11 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.