Spring semester

COM1002 Programming Languages 1, COM1004 Programming Languages 2.

To explore algorithms as abstractions - independent of any computing facility.
To examine what is involved in creating algorithms and quantifying their efficiency.
To examine the importance of algorithm efficiency and see how the appropriate choice of data structures can facilitate this.
To discover and examine various abstract data types.
To examine the action of a small number of specific algorithms in the areas of hashing, sorting and data compression.
To explore various strategies for algorithm design.
To classify algorithms.
To question what the future holds in terms of algorithm development and classification.

At the end of the module you should:

• Be familiar with the big Oh measure of algorithm efficiency.
• Be able to describe and handle the taught abstract data types (ADT).
• Be able to describe and handle taught ADT applications, e.g. applications of a heap.
• Know what is meant by recursive and non-recursive algorithms.
• Be able to describe a number of searching strategies and trace any of the taught hashing schemes.
• Be able to describe any of the taught sorting methods.
• Be able to distinguish between different algorithm design strategies.
• Be able to discuss the classification of algorithms and problems.

Background: An algorithm is a sequence of steps for performing some process. A computer program is not an algorithm but a representation of an algorithm. There is need to be able to create effective algorithms, quantify their efficiency and classify them independently of any computing system or language.

This module starts by considering the abstract nature of algorithms. It continues by defining a scheme for quantifying algorithm efficiency, devoid of any computing system or language. A discussion of the importance of algorithm efficiency then provides the motivation to discover, over the ensuing weeks, efficient data structures and study various abstract data types such as lists, stacks, queues, trees and graphs. As the module continues, several approaches for algorithm design are studied such as recursion, divide and conquer, and brute force strategies. Towards the end of the module the classification of algorithms and the problems they solve is explored. The module finally concludes by asking how future technological developments could change the way we perceive algorithms.

You should be clear that the module does NOT set out to review the action of a comprehensive range of specific algorithms. Nevertheless, a limited number of specific algorithms within the areas of searching, sorting and data compression will be examined.

Lectures and seminars.  The course is conceptual. Much of the material is independent of any computer language. Much of your coursework will be pen and paper (or word processor) based. But at the practical level you will also be handling Java programs which implement various data structures such as linked lists and algorithmic strategies such as recursion.

All of the material you need for the module will be provided. However, if you also wish to purchase a book you may find the following useful.

Main course text    Title:             Data Structures and Algorithm Analysis in Java.

                              Author:          Mark Allen Weiss

                              Publisher      Benjamin/Cummings Publishing Inc

                              ISBN             0-201-35754-2

                              Price             approx £22

This book covers about 80% of the course material. Code (where given) is in Java.

The ‘Pascal’ version of this book entitled Data Structures and Algorithm Analysis (ISBN0-8053-9057-X) and the C version entitled Data Structures and Algorithm Analysis in C (ISBN 0-202-49840-5) are also suitable.

Other Books          Title              Algorithmics:  The Spirit Of Computing  2^nd or 3^rd Edn

                              Author:          David Harel

                              Publisher      Addison-Wesley Publishing Co

20 August 2008