# Algorithms I2009–10

Principal lecturer: Dr Robert Harle
Taken by: Part IA CST, Part IA NST, Part I PPS
Syllabus
Past exam questions: Algorithms I, Algorithms
Information for supervisors (contact lecturer for access permission)

## Course Overview

This course is intended to expose IA students to the basics of algorithms. It does so by:

• analysing a range of sorting algorithms;
• introducing established algorithm strategies (divide and conquer, etc);
• introducing and analysing a series of data structures from stacks to red-black trees

## Course Notes

The course handout was written by Dr Frank Stajano and is an excellent document around which to base your studies. It is itself based on the course textbook Introduction to Algorithms by Cormen. et al. You can download the PDF here.

Although the notes are excellent, they are not my preferred format for lecture presentation. Consequently I use a set of slides that I annotate during lectures. These you can download here (including annotations):

• Lecture 1 (Intro, asymptotic analysis, assertions, insertion sort)
• Lecture 2 (Insertion, selection, bubble, binary insertion and mergesort algorithms and analysis)
• Lecture 3 (Quicksort)
• Lecture 4 (Quickselect, Heapsort, Distribution Sort)
• Lecture 5 (Algorithm design)
• Lecture 6 (Elementary data structures)
• Lecture 7 (Basics of Binary Search Trees)
• Lecture 8 (Red-Black Trees)
• Lecture 9 (AVL Trees, B-Trees) [Corrected after lecture]
• Lecture 10 (Hash Tables)
• Lecture 10 (Prioriry Queues and Binomial Heaps)

## Lecture 12

The course material was covered in the first 11 lectures, so there is no twelth lecture per-se. However, I will turn up on wednesday at 10am and students are free to come and ask questions or have me go over parts of the course if they wish.

## Examples Sheet

The lecture notes contain a series of exercises meant primarily to focus and challenge the reader as they go. They are not intended for supervisions per se, although a subset are certainly appropriate.

To help guide supervisions, I have produced an examples sheet that picks out some of the exercises from the notes and supplements them with some others I dreamed up. This sheet was updated as the course went on and the (hopefully) final version is here: download the examples sheet

In addition, you should have no difficulty in finding other exercises in the textbook or others like it.

## Sorting Competition

Many congratulations to all who entered. The results were very impressive - almost everyone's algorithm beat the native Java sort method on at least one aspect!