Feedback on the formal coursework

Tutorial handout, 30/11/2007

Past exam papers (Local access only)

Course description

2004-5 lecture slides

JDK 1.5 API documents (here you can look at Collection classes in java.util package)

Data Structures and Algorithms in Java (4th Edition)

John Wiley & Sons

Textbook website is http://ww0.java4.datastructures.net .

- Lectures 1-2 (introduction and algorithm analysis).
- Lecture 3 (stacks and queues).
- Lecture 4 (answers to informal coursework. Summary of big Oh. Any questions.) If I have time, I will also talk about recursion.
- Lecture 5 (linked lists, vectors)
- Lecture 6 (more linked lists, comparison of sequential and random access list implementations, iterators)
- Lecture 7 Trees.

- Lecture 8 (priority queue ADT and heap data structure)
- Lecture 9 Map ADT and hash tables.
- Lecture 10 Binary search trees, AVL trees.
- Lecture 11 (now with exercises) (2-4) trees. Also, some background for formal coursework: here and SimpleTest.java.
- Lecture 12 Red-black trees.
- Lecture 13 External searching, B-trees.
- Lecture 14 Simple sorting algorithms and their complexity.
- Lecture 15 Merge sort and quicksort. Lower bounds on comparison sorting (it cannot be done faster than O(n log n)). Complete Java code for merge sort and quicksort on arrays.
- Lecture 16 Proving correctness of algorithms.

Some of the material is not in the textbook. - Lecture 17 Graphs - implementing graphs - breadth-first and depth-first search - their complexity.
- Lecture 18 Topological sort. Minimal spanning tree.
- Lecture 19. Greedy algorithms. Why they are not always optimal. Dijkstra's algorithm (and why it is optimal).
- Revision lecture and course review.

- Informal coursework on algorithm analysis
- Please do exercises for 2-4 trees which we did not have time for in lecture 11.
- Informal coursework on proving correctness
- Answers to the informal coursework on correctness.

This file is maintained by Natasha Alechina

Last updated September 28, 2007.