Algorithms and Data Structures 2003 - 2004

Formal coursework

Feedback for formal coursework

Note: lecture on the 11th of December is in LT2.
There will be a revision/feedback for the coursework lecture on Friday the 9th of January at 11 in LT3.

Lecture slides

Lecture 1 (Aims, objectives, textbooks...)
Lecture 2 (Algorithm analysis)
Lectures 3 and 4 (big Oh continued). Includes informal coursework.
Lecture 5 (Simple sorting algorithms) Includes informal coursework. Handout (code of the algorithms).
Lecture 6 (Merge sort). Question from the previous lecture (prove that bubble sort running time is not in O(N)) answered. Merge sort code
Lecture 7 (Quick sort). Quicksort code
Lecture 8 Abstract data types. List ADT. Linked list class from the last year Java course.
Lecture 9 More lists, stacks and queues.
Lecture 10 Graphs: terminology and implementation. The slides of Brian Logan's lecture
Lecture 11 Depth first search, breadth first search, using DFS for cycle detection, complexity of DFS and BFS.
Lectures 12 and 13 Topological sort; using topological sort for cycle detection. Dijkstra's algorithm. Greedy algorithms in general. Minimal spanning tree. Prim's algorithm.
Lecture 14 Hash tables.
Lecture 15 Trees (perfectly balanced and complete trees. Number of levels and number of nodes).
Lecture 16 Binary Search Trees. Java implementation. Corrected version - there was a typo in the search algorithm description, and I generally improved the pseudocode.
Lecture 17 Balanced binary trees.
Lecture 18 Correctness of algorithms.
Lecture 19 B-Trees. Note: lecture in LT2.
Lecture 20 Heaps.
Revision and feedback for the coursework: lecture on Friday the 9th of January at 11 in LT3.
Exam revision lecture from last year
Exam revision lecture from 2000-2001.

Tutorial allocation

Please only attend tutorials if you are really struggling with the material. Please try to attend during the time allocated to you to spread the load evenly.

Monday 12:00-13:00 in C4 (CTF, or Exchange building). Students with usernames starting a - g.
Tuesday 15:00-16:00 in C42 ( in the School of Education ), students with usernames starting h - n.
Thursday 13:00-14:00 in B53 (Computer Science). Students with usernames starting m - r.
Friday 13:00-14:00 in A01 (Computer Science). Students with usernames s - z.

Informal coursework

Informal coursework is given so that you can check whether you understand the material and to help you revise. Answers will be posted here on Friday before next week tutorials. Informal coursework is not being marked. Tutorials are not compulsory - in fact, please only go to tutorials if you are really struggling with the topic because space is a problem.

This file is maintained by Natasha Alechina
Last updated December 4, 2003.