Algorithms

Data Structures and Computational Complexity
(Lent 2011)

• Home page
• Schedules [updated]
• What do I need to know?
• Algorithms 2010
  • Notes
  • Videos
  • Schedules
• Resources
  • Example sheets
  • Further material
  • Interesting asides
• Errata
• About Us

Welcome to the course home page for Algorithms: Data Structures and Computational Complexity! This was a new course being run by a team of students here at Cambridge, after the previous year's successful Algorithms 2010 course.

Quick links:

• Errata for the course are published on this website: please see the errata page.
• We are also keeping example sheets on the website.

Introduction

In this course - a largely independent sequel to the brand-new Algorithms 2010 course taught last year - we move on to discuss in detail some of the important theoretical and practical concepts underlying some of the basic topics in algorithms. The two key areas we will focus on will be Data Structures, and then Complexity Theory and Approximation Algorithms.

• Data structures are everywhere. In the same way that a good algorithm can make a computation faster, keeping track of information in the right way can make important operations faster. They are the difference between Google maps taking a weekend to give directions, and it giving the right route in fractions of a second. They are the difference between the categorized shelves of the University Library and a pile of 7 million books. They allow the internet to be routed over fibre; they allow searching for quotations from books. They allow Amazon to recommend new things you might want and allow supermarkets to do "just in time" restocking. They are invisible and indispensable.
• Complexity theory discusses the single most important theoretical property of a problem (beyond whether or not we can solve it at all!) - how much time and space is needed to solve it, as the scale of the problem grows. The discussion will lead up to an overview of the P = NP problem, one of the biggest open problems in computer science. Finally, we'll see that the intractability of some problems has not deterred brave people from trying to solve them anyway - and (at least partially) succeeding! In fact, it's possible to get solutions which are provably close to optimal, and the study of such approximation algorithms has been a hot topic in recent years.

For a more detailed list of the topics we intend to cover, you can view the schedules in either HTML or PDF format.

We have set out to make this course as accessible as possible to as many people as possible - in particular, first-year students were warmly welcomed to attend! As far as background goes, we have set out the main things you should check you can understand in the What do I need to know? section. Don't worry about this, there really is not anything too difficult!

When & Where?

The course was held in

The first lecture was on Thursday 20 January 2011, and there were sixteen lectures in total.

This Website

This website will hopefully soon host notes for the lectures, videos of the lectures and some real examples of code implementing the techniques discussed.

Also, if you look around the site (particularly in the Resources section), you will find plenty of material for further reading as well as challenging problems you may like to attempt.

Algorithms 2010

Last year, another course entitled Algorithms (2010) was run by Sean Lip, and he worked with Freddie Manners and Ludwig Schmidt to present a 16 lecture course introducing the basics of complexity analysis, and going on to discuss and solve a whole range of problems. Topics from dynamic programming, graph algorithms, greedy algorithms, maximum matching and network flow theory were discussed (see the schedules).

The course was filmed, and videos for all of the lectures are available on the course website. Alternatively, the full notes for the course are available from the author's website.

Finally, the course had supplementary material in the form of example sheets (see the course home page) and 10 challenge questions and programming tasks, which you might like to attempt if you are enthusiastic. (Solutions for the challenge problems are also given, if you would like to see how other students solved them last year.)

Contact Information

Lecturing team contact: tucac2011 AT gmail.com, organizer's home page.

Webmaster e-mail: cpt39 AT cam.ac.uk, home page.