Code

COMPGC05

Year

MSc

Prerequisites

This course should be taken in conjunction with the core courses for this programme (ie GC01, GC02, GC03 and GC04)

Term

2

Taught By

Denise Gorse (50%)
Jens Krinke (50%)

Aims

To introduce more formal aspects of algorithms and data structures than in the first term. Properties of data types such as queues and search trees. Techniques for analysing the complexity and decidability of algorithms. Formal models of computation.

Learning Outcomes

Knowledge of a selection of standard data structures and abstract data types. The ability to choose appropriate data structures for programming problems. Understanding of a variety of common algorithms and why some are more efficient than others. Ability to discuss uncomputable and intractable algorithms.

Course Introduction

Introduction to data structures and abstract data types.
Abstract data types and Java classes.
Language facilities. Model of storage in imperative languages. Cells, l-values and r-values. Exceptions.
Data aggregation: arrays, structures and object references.

Linear abstract data types

Stacks and queues. Implementations with arrays and linked lists. Applications.
Sequences. Implementations with arrays and linked lists. Circular and double linked lists.
Inheritance relationships between linear linked lists

Tables

Linear look-up table.
Linear search.
Binary search.

Trees

Definitions of trees.
Binary search tree.
Insertion, deletion, tree traversal and searching.

Hash tables

Chaining.
Open addressing.
Choice of hash function.

Graphs

Adjacency lists.
Adjacency matrices.
Depth and breadth first traversal.

Sorting

Insertion Sort
Mergesort
Quicksort

Analysis of Algorithms

Empirical vs theoretical analysis
Algorithmic complexity
O notation
Best, worst, and average cases
Sums of series
Simple summation formulae

Analysis of earlier examples

Includes linear and binary search

Limits of Computation

Tractable and intractable problems; the complexity classes P, NP, NPC
Undecidability; the Halting Problem

Lecture presentations, coursework and associated class problems .

The course has the following assessment components:

• Written Examination (2.5 hours, 90%)
• Coursework Section (2 pieces, 10%)

To pass this course, students must:

• Obtain an overall pass mark of 50% for all sections combined

The examination rubric is:
Answer any 3 questions, at least ONE from EACH of Sections A and B, all questions carry equal marks

Algorithmics - the science of computing. D.

Harel, Addison-Wesley, 1989.