Next: Paper 2: Probability Up: Easter Term 2010: Part Previous: Easter Term 2010: Part   Contents

## Paper 1: Algorithms I

Lecturer: Dr R.K. Harle

No. of lectures: 12

Prerequisite course: Discrete Mathematics I

This course is a prerequisite for Algorithms II and Prolog.

Aims

The aim of this course is to provide an introduction to computer algorithms and data structures, with an emphasis on foundational material.

Lectures

• Sorting. Review of insertion sort, merge sort and quicksort. Understanding their memory usage with arrays. Heapsort. Other sorting methods. Finding the minimum and maximum. [Ref: Ch 1, 2, 3, 4, 15, 16] [4 lectures]

• Algorithm design. Ideas for algorithm design: dynamic programming, divide and conquer, greedy algorithms and other useful paradigms. [Ref: Ch 2, 15] [2 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] [6 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.