Data Structures and Algorithms

Lecturer: Professor R.M. Needham (rmn@cl.cam.ac.uk)

No. of lectures: 16  

Fundamentals.

Models of a computer, costs, growth rates.

Simple data structures.

Arrays, lists, trees. Idea of abstract data type.

Ideas for algorithm design.

Divide and Conquer and other important styles of algorithm.

The TABLE data type.

Multiple implementation models for a single ADT, including hash tables.

Free storage management.

Reference counts and garbage collection.

Sorting.

Insertion, Shell, Quick, Heap and other sorting methods.

Storage on external media.

Larsen's method, B-trees, multi-tape sorting.

Variants on the SET data type.

Operations to be supported. 2-3-4 and red-black trees.

Data compression.

Huffman. LZ.

Algorithms on graphs.

Reachability and shortest paths. Matchings in bi-partite graphs.

Geometric algorithms.

Inside-outside a closed figure? Do line segments cross? Convex hull.

Recommended books:

Aho, A.V., Hopcroft, J.E. & Ullman, J.D. (1983). Data Structures and Algorithms. Addison-Wesley.

Cormen, T.H., Leiserson, C.D. & Rivest, R.L. (1990). Introduction to Algorithms. MIT Press.

Manber, U. (1989). Algorithms: A Creative Approach. Addison-Wesley.