Computer LaboratoryComputer Science Syllabus - Data Structures and Algorithms

Data Structures and Algorithms
Next: Digital Electronics Up: Michaelmas Term 2005: Part Previous: Concurrent Systems and Applications   Contents

Data Structures and Algorithms

Lecturer: Dr F.M. Stajano

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 an introduction to computer algorithms and data structures, with an emphasis on foundational material.

Lectures

• Fundamentals. Algorithm analysis and design. Models of a computer; costs. Asymptotic notation. Recurrences. Ideas for algorithm design: divide and conquer, dynamic programming, greedy algorithms and other useful paradigms. [Ref: Ch 1, 2, 3, 4, 15, 16] [1-2 lectures]

• Sorting. Insertion sort. Merge sort. Heapsort. Quicksort. Other sorting methods. Finding the minimum and maximum. [Ref: Ch 2, 6, 7, 8, 9] [3-4 lectures]

• Data structures. Abstract data types. Pointers, stacks, queues, lists, trees. Hash tables. Binary search trees. Red-black trees. B-trees. [Ref: Ch 10, 11, 12, 13, 18] [5-6 lectures]

• Algorithms on graphs. Breadth-first and depth-first search. Topological sort. Minimum spanning tree. Kruskal and Prim algorithms. Shortest paths. Maximum flow. Ford-Fulkerson algorithm. Matchings in bipartite graphs. [Ref: Ch 22, 23, 24, 25, 26] [3-5 lectures]

• Geometric algorithms. Intersection of segments. Convex hull: Graham's scan, Jarvis's march. [Ref: Ch 33] [1-2 lectures]

Objectives

At the end of the course students should

• have a good understanding of how several fundamental algorithms work, particularly those concerned with sorting, searching and graph manipulation

• have a good understanding of the fundamental data structures used in computer science

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

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

* Cormen, T.H., Leiserson, C.D., Rivest, R.L. & Stein, C. (2001). Introduction to Algorithms. MIT Press (2nd ed.). ISBN 0-262-53196-8
Sedgewick, R. (2004). Algorithms in Java. (2 volumes; note that C and C++ editions are also available and are equally good for this course). Addison-Wesley. ISBN 0-201-36120-5 and 0-201-36121-3.
Kleinberg, J. & Tardos, É. (2006). Algorithm design. Addison-Wesley. ISBN 0-321-29535-8.
Knuth, D.E. (1997). The art of computer programming (three volumes so far; a boxed set is also available). Addison-Wesley (3rd ed.). ISBN 0-201-89683-4, 0-201-89684-2 and 0-201-89685-0.

Students are expected to buy and make extensive use of one of the above references: those not doing so will be severely disadvantaged. The easiest and recommended choice is Cormen et al. which covers all the topics in the syllabus: the pointers in the syllabus are to chapters in that book. The other textbooks are all excellent alternatives and are sometimes clearer or more detailed than Cormen, but they are not guaranteed to cover every item in the syllabus. Their relative merits are discussed in the course handout.

Next: Digital Electronics Up: Michaelmas Term 2005: Part Previous: Concurrent Systems and Applications   Contents
Christine Northeast
Sun Sep 11 15:46:50 BST 2005

 © 2005 University of Cambridge Computer Laboratory Please send any comments to pagemaster@cl.cam.ac.uk Page last updated on 11-Sep-2005 at 15:57 by Christine Northeast