Algorithms I 2009–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!
|