Data Structures and Algorithms

Lecturer: Dr M. Richards (mr@cl.cam.ac.uk)

No. of lectures: 16

This course is a prerequisite for Further Java (Part IB and Diploma) and Complexity Theory (Part IB and Diploma).

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, Tree, Merge and Radix. Selection of k^th element in O(n).

Storage on external media.

Larsen's method, B-trees.

Variants on the SET data type.

Balanced, 2-3-4, red-black, splay and ternary trees.

String searching.

Brute force, Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp algorithms.

Data compression.

Run length encoding, Prediction, Move-to-Front, Huffman, Arithmetic encoding, Lempel-Ziv, and Wheeler's Block Compression.

Algorithms on graphs.

Reachability and shortest paths. Warshall, Floyd, Dijkstra, Prim and Kruskal algorithms. Depth first and breadth first traversal, Strongly connected components. Matchings in bi-partite graphs.

Geometric algorithms.

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

Recommended books:

Sedgewick, R. (1990). Algorithms in C. 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.

Salomon, D. (1998). Data Compression: The Complete Reference. Springer.