Algorithms and Data Structures 2004-2005
Course description
Last year's course notes
Past exam papers (Local access only)
New textbook
Starting in 2004-2005, I have decided to switch to a new textbook:
Goodrich, Michael T. and Tamassia, Roberto
Data Structures and Algorithms in Java
John Wiley & Sons
Textbook website is http://java.datastructures.net .
Lecture slides
Lecture slides are in pdf, 6 slides to a page. Where the copyright notice
(@Goodrich and Tamassia) is present, the slides are downloaded from the website
for the Goodrich and Tamassia textbook. I may have made small changes
to the slides. All typos are probably mine, even when copyrighted to G & T.
- Lectures 1 and 2 (introduction and algorithm analysis)
- Lecture 3 (recursion)
- Lecture 4 (stacks and queues)
I have removed `using a stack to compute spans' algorithm because it is broken
(sorry, and thanks to the student who pointed this out). It is possible to
compute spans in linear time, but you don't really need a stack to do this.
Here is the code.
- Lecture 5 (linked lists and vectors)
- Lecture 6 (List ADT).
Program from the lecture: SinglyLinkedList.java
- Lecture 7 (Trees).
- Lecture 8 (Priority queues).
- Lecture 9 (Maps and hash tables).
- Lecture 10 (Binary search trees; AVL trees).
- Lecture 11 ((2,4) trees).
Extra slides: exercise from the lecture.
- Lecture 12 (red-black trees).
Same lecture with more pictures added.
- Lecture 13 (algortihms and data structures for external memory;
B-trees).
- Lecture 14 (simple sorting algorithms; three
pages, no animations)
If you would like algorithm traces, here are all the
slides, but there are 15 pages of them.
- Lecture 15 (merge sort)
- Lecture 16 (quicksort; correctness of programs)
Typo on slide 31 (loop invariant for selection sort) corrected. Also, `sorting in place' means sorting without using an extra data structure, sorry for confusing you in the lecture on merge sort.
- Graphs: terminology and implementation
- Breadth-first search, depth-first search, their complexity
- More graph algorithms: topological sort, minimal spanning tree, Dijkstra's algorithm. Greedy algorithms.
- Revision lecture
Informal coursework
This file is maintained by Natasha Alechina
Last updated February 7, 2005.