Advanced Data Structures is about using mathematical objects like trees and graphs to represent computational problems.
It teaches you some sophisticated algorithms and methods of analysis.
We will concentrate on functional programming, specifically using the language Haskell.
The module is equally divided into the abstract study of the data structures, their realisation into programs and their correctness and complexity analysis.
We will learn design techniques to develop our own algorithms.
We will look at both classical topics, like redblack trees and binomial queues and some new structures developed exclusively for functional languages.
Module Resources
The material of the module derives mostly from the following three books.
 Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms (IA)
 Chris Okasaki, Purely Functional Data Structures (PFDS)
 Richard Bird, Pearls of Functional Algorithm Design (PFAD)
The first book gives the mathematical background, the method of complexity analysis, and the description of data structures and algorithms in an imperative language.
The second book, which is the main reference, is about functional programming.
It teaches you how to implement the data structures and algorithms in languages like ML and Haskell.
The third book is about functional algorithm design, illustrated by using several short programming problems, puzzles and games.
Haskell
The language used in the module is Haskell.
We only use a subset of it: algebraic data types, recursive function definitions and type classes.
So even if you haven't learnt it before, it should take you just a few days to become familiar with these features.
The best introductions to Haskell are the following two books.
 Graham Hutton, Programming in Haskell
 Miran Lipovača, Learn You a Haskell for Great Good! (Website)
The Haskell Glasgow Compiler is available for all major operating systems and is installed on all computer in the terminal room.
There's a
mailing list for beginners. I encourage you to subscribe to it and post any questions about the language there.
Outline of lectures
In this section you will find, after each lecture, a list of topics that were taught.
The lecture notes are in the form of commented Haskell files showing the implementation of the material of each lecture.
Lecture  Topics  Haskell Files 
1. 4 Oct 2011 
Introduction to the Module
Insertion Sort and Binary Search Trees
Complexity of Algorithms

Sorting
IA Ch.3; PFDS Ch.2

Tutorial 6 Oct 2011 
Mergesort, Quicksort, Balanced Search Trees
Exercises on complexity


2. 11 Oct 2011 
RedBlack Trees
Leftist Heaps

RedBlack Trees
PFDS Ch.3, Sec.3.3

3. 18 Oct 2011 
Leftist Heaps (continued) Binomial Heaps

Leftist Heaps
Binomial Heaps
PFDS Ch.3

4. 25 Oct 2011 
Binomial Heaps (continued)
Finding a minimum tree


Tutorial 27 Oct 2011 
Exercise: efficient way of
constructing minimum tree

Minimum Tree
PFAD Ch.7 
5. 1 Nov 2011 
Correctness of forest insertion
Folding operators


Tutorial 3 Nov 2011 
Tutorial in Lab
Heap instance for Binomial Heaps

See revised version of
Binomial Heaps file 
6. 8 Nov 2011 
Infinite data types: Streams

Streams 
7. 15 Nov 2011 
Recursive equations on streams
The unfold operator


Tutorial 17 Nov 2011 
Exercises with unfolding


8. 22 Nov 2011 
Bisimulations, Coinduction Principle

Bisimulation 
9. 29 Nov 2011 
Coinductive Data Types
Amortized Analysis

Amortized Analysis 
Tutorial 1 Dec 2011 
Questions about Presentations


10. 6 Dec 2011
room: JCAMENB12

Amortized Analysis
Second hour: Presentations


Tutorial 8 Dec 2011 
Presentations


11. 13 Dec 2011

Presentations


Tutorial 15 Dec 2011 
Presentations


Assessment
The final mark you get on this module is equally divided between coursework and final exam.
The coursework consists in a small project.
You will be assigned a topic, a specific data structure or algorithm from the literature.
You have to do some research on it and produce a Haskell implementation and and a 10 pages report.
During the last week of the semester you'll have to give a short presentation on it.
The deadline for submission of coursework is 13 January 2012.
You must submit the report in hard copy to the School Office and the program to me by email.
All the projects are from Richard Bird's book "Pearls of Functional Algorithm Design" (PFAD).
ID numbers  Presentation day and time  Topic  Reference 
[4172551]
[4170010]
[4091976]
[4164576]

8 Dec, 12:00
13 Dec, 17:00
13 Dec, 16:00
15 Dec, 12:00

Sudoku solver 
PFAD, Chapter 19 
[4084413]
[4152051]
[4086535]
[4171372]
[4160694]

6 Dec, 17:00
8 Dec, 12:10
13 Dec, 17:10
13 Dec, 16:10
15 Dec, 12:10

The smallest free number 
PFAD, Chapter 1 
[4079812]
[4154263]
[4083813]
[4086690]
[4170932]

6 Dec, 17:10
8 Dec, 12:20
13 Dec, 17:20
13 Dec, 16:20
15 Dec, 12:20

Finding Celebrities 
PFAD, Chapter 9 
[2110425]
[4174683]
[4171366]
[4172966]
[4172461]

6 Dec, 17:20
8 Dec, 12:30
13 Dec, 17:30
13 Dec, 16:30
15 Dec, 12:30

The Countdown problem 
PFAD, Chapter 20 
[4164737]
[4148373]
[4080605]
[4082701]

8 Dec, 12:40
13 Dec, 17:40
13 Dec, 16:40
15 Dec, 12:40

Making a century 
PFAD, Chapter 6 
Here is a description of the various goals of the project:
 Presentation: It should last around 7 minutes, leaving 3 minutes for questions. You must explain the problem you were assigned, in a clear way understandable to everybody, and say what techniques are used to solve it.
 Program: A Haskell implementation of the solution of the problem. The book PFAD already gives the solution, so you just need to make sure that you understand it and write it in a Haskell file. At the end of your file include an example on which you run the program, showing that it works correctly.
 Report: Write about 10 pages (in plain LaTex article style; you can use any other document preparation software) describing the problem to a lay reader; explaining the Haskell solution; proving that it is correct; and giving some complexity analysis.
You should write the report in your own words (don't copy from PFAD, check the rules about plagiarism).
Your report should include more details and explanations than PFAD: think that it should be easily understandable by your classmates.
Contacting the teacher
Please don't hesitate to ask me any question you may have about the module.
Office hours are on Monday from 4pm to 5pm and Thursday from 10am to 11am in my office (A07 in the Computer Science building).
I will be answering all your queries during those times.
You can also contact me by email: put
G64ADS in the subject line, so I know immediately that it is about this module.