Computer Laboratory Home Page Search A-Z Directory Help
University of Cambridge Home Computer Laboratory
Computer Science Tripos Syllabus - Data Structures and Algorithms
Computer Laboratory > Computer Science Tripos Syllabus - Data Structures and Algorithms

Data Structures and Algorithms next up previous contents
Next: Digital Electronics Up: Michaelmas Term 2004: Part Previous: Continuous Mathematics   Contents


Data Structures and Algorithms

Lecturers: Dr M. Richards and Mr E.C. Upton

No. of lectures: 16

This course is a prerequisite for Computer Graphics and Image Processing, Complexity Theory, Artificial Intelligence I.


Aims


The aim of this course is to provide a comprehensive introduction to computer algorithms taken from many different areas of application. The course will concentrate on algorithms that are of fundamental importance and the efficiency of most of them will be analysed.


Lectures

  • 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, dynamic programming 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. Union-Find algorithms.

  • 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.

Objectives


At the end of the course students should

  • have a good understanding of how several fundamental algorithms work, particularly those concerned with sorting and table look up

  • be able to analyse the efficiency in terms of space and time of most algorithms

  • be familiar with several techniques used in data compression and algorithms on graphs

  • be able to design new algorithms or modify existing ones for new applications and reason about the efficiency of the result

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). Introduction to algorithms: a creative approach. Addison-Wesley.
Salomon, D. (1998). Data compression: the complete reference. Springer.



next up previous contents
Next: Digital Electronics Up: Michaelmas Term 2004: Part Previous: Continuous Mathematics   Contents
Christine Northeast
Wed Sep 8 11:57:14 BST 2004