Computer Science, Prifysgol Cymru Aberystwyth University of Wales

CS21020 (1995-96 session)
Program Design, Data Structures and Algorithms

Brief Description

Aims, Objectives, Syllabus, Booklist

Further Details

Number of lectures

48

Number of seminars/tutorials

8

Number of practicals

0

Coordinator

Dr. Fred Long

Other staff involved

Not yet known

Pre-requisites

Pass or exemption in Computer Science at Level 1

Co-requisites

None

Incompatibilities

None

Assessment

Assessed coursework - 50%
Written exam - 50%

Timing

This module extends over both Semester 1 and Semester 2

As well as providing a solid grounding in the major data structures and algorithms of Computer Science, the course stresses the development of problem solving skills through a number of programming assignments.

Objectives

• understand the principles of abstraction and encapsulation as they apply to the design of abstract data types and programs;
• understand the importance of the running time behaviour of algorithms and how this is expressed and determined;
• have a familiarity with some of the main approaches to algorithm design such as greedy algorithms, divide and conquer and dynamic programming;
• be able to evaluate and choose appropriate data structures and algorithms for a range of programming problems;
• be able to design and implement significant programs in Ada;
• have an appreciation of the importance of program correctness and some of the techniques used to ensure it.

Introduction to complexity - 4 Lectures

O() notation, growth rates. Measurement of execution time of some real programs and estimation of their time complexity. Some examples of time/space trade-offs.

Re-introduction to abstract data types - 4 Lectures

Issues of correctness as they relate to the definition of ADTs. The key ideas of abstraction and encapsulation. Notations for describing ADTs. Ada support for their implementation: packages, exceptions and generics.

Introduction to pointers and dynamic storage allocation and the advantages and disadvantages compared with static allocation - 4 Lectures

Failure modes associated with heap allocation. An examination of a familiar ADT implemented using dynamic storage. Abstract specification versus concrete implementation.

Storing and retrieving data by key (1) - 8 Lectures

This problem will be used to motivate the discussion of a wide variety different implementation techniques. The features of some typical solutions will be related to the dimensions of the problem such as the volume of data to be handled, volatility and the operations required. Internal Storage: linear and binary searching. A brief introduction to proving programs correct with particular reference to the use of loop invariants. Linked representations; an introduction to hashing and binary search trees.

Storing and retrieving data by key (2): External storage - 6 Lectures

Performance issues. Using Ada Direct\_IO to implement persistent random access storage. Hashing and B-tree organisations.

Representing text - 4 Lectures

A simple text editor will be used as the basis of a substantial design case-study showing how the design decisions concerning the different ways of representing text affect performance and ease of implementation. String matching algorithms and their performance (for the searching operations provided by the editor).

Sorting - 4 Lectures

Divide and conquer algorithms. An introduction to proving the performance of an algorithm.

Representing complex relationships: graphs and the algorithms used to process them - 8 Lectures

Some examples of greedy algorithms. Terminology and implementation considerations. A look at some graph-related problems such as: finding a route (shortest paths); planning a communications network (minimum spanning trees); network routing management (flow graphs); compiling a program or planning a project (topological sorting).

Limitations of ADTs - 4 Lectures

What happens when a reusable component does almost what you want. An introduction to object-oriented programming and design and the object-oriented features of Ada 95.

Designing ADTs, classes and objects in other languages - 4 Lectures

A brief examination of C++.

Students are likely to need ready access to the following

Mark Allen Weiss. Data Structures and Algorithm Analysis in Ada. Benjamin/Cummings, Redwood City, California, 1993.

D. F. Stubbs and N. W. Webre. Data Structures with Abstract Data Types and Ada. PWS-Kent, 1993.

Notes

Students will probably wish to choose one of the above.

The following should be consulted for different approaches or for further information

Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, Massachusetts, 1990.

Alfred Aho, John Hopcroft, and Jeffrey Ullman. Data Structures and Algorithms. Addison-Wesley, Reading, Massachusetts, 1983.

Robert Sedgewick. Algorithms. Addison-Wesley, Reading, Massachusetts, 1988.

Grady Booch and Doug Bryan. Software Engineering with Ada. Benjamin/Cummings, Redwood City, California, 3rd. edition, 1994.

Rebecca Wirfs-Brock, Brian Wilkerson, and Lauren Wiener. Designing Object-Oriented Software. Prentice Hall, 1990.

Timothy A. Budd. Classic Data Structures in C++. Addison-Wesley, 1994.

Robert L Kruse. Data Structures and Program Design. Prentice-Hall, Englewood Cliffs, New Jersey, second edition, 1987. (The first edition is also available from the library).

Thomas A Standish. Data Structures, Algorithms and Software Principles. Addison-Wesley, Reading, Massachusetts, 1994.

Alfred Aho and Jeffrey Ullman. Foundations of Computer Science. Computer Science Press, New York, 1992.

Notes

The book by Wirfs-Brock et. al. provides a useful introduction to the concepts of object-oriented programming and design which are covered later in the course. Budd shows how many of the data structures covered in the course can be implemented using C++.

Version 4.1

John Hunt Departmental Advisor