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 red-black 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 |
Red-Black Trees
Leftist Heaps
|
Red-Black 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: JC-AMEN-B12
|
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 e-mail.
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 e-mail: put
G64ADS in the subject line, so I know immediately that it is about this module.