Next: Digital Electronics Up: Michaelmas Term 2007: Part Previous: Computer Design   Contents

## Data Structures and Algorithms

Lecturer: Dr F.M. Stajano

No. of lectures: 16

This course is a prerequisite for Algorithms II, 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. It is suitable for people who did not take discrete mathematics in Part IA.

Lectures

• Discrete Mathematics. Common mathematical notation. Proofs. Induction. Sets, tuples, functions. Relations and Graphs. Combinations and permutations. [Ref: Ch 1; App B, C] [3-4 lectures]

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

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

• Data structures. Abstract data types. Pointers, stacks, queues, lists, trees. Hash tables. Binary search trees. Red-black trees. B-trees. Priority queues and heaps. [Ref: Ch 10, 11, 12, 13, 18, 19, 20, 21] [5-7 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 and searching

• 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