Module Identifier CSM0320  
Academic Year 2000/2001  
Co-ordinator Dr Myra Wilson  
Semester Semester 2 (Taught over 2 semesters)  
Pre-Requisite CSM0120  
Course delivery Lecture   55 Hours  
  Practical   22 Hours 22 x 2 hours  
Assessment Exam   2 Hours   50%  
  Course work   Two pieces of assessed coursework.   50%  
  Resit assessment   Supplementary examination will take the same form, under the terms of the Department's policy    

General description
In the 40 or so years that people have been developing software, a range of common tasks, such as sorting and searching, have been identified and a body of knowledge has been accumulated about how these tasks are best carried out. This knowledge usually consists of various ways of structuring the data, a range of different algorithms, and performance analysis that enables a designer to chose the algorithm and data structure most appropriate to the circumstances of the system, and to predict how the system will perform.

This module introduces students to this body of knowledge and sets it into the context of modern software design and structuring techniques.

The aims of this module are to:

Learning outcomes
On successful completion of the module, students should:

1. Course overview - 4 Lectures
An introduction into time/space complexity. Issues of correctness as they relate to the definition of ADTs. The key ideas of abstraction and encapsulation. Notations for describing ADTs.

2. Further design and implementation of computer programs - 12 Lectures
Programming language facilities will be investigated to support more advanced data structures and the development of larger, more reusable software. An introduction to linear data structures: stacks, queues and lists of objects, implemented using arrays and utilising interfaces. An introduction to recursion.

3. Dynamic storage allocation - 8 Lectures
An investigation into unbounded data structures and a comparison with their bounded equivalents.

4. Object-oriented design - 1 Lecture
An introduction to object-oriented analysis and design. A brief consideration of use case analysis.

5. The unified modelling language (UML) - 2 Lectures
The UML is an attempt by Booch, Rumbaugh and Jacobson to produce a common language for describing OO designs. These lectures will provide a brief introduction to UML.

6. The object modelling technique (OMT) - 6 Lectures
The OMT approach to object-oriented design will be considered and the analysis phase will be discussed. Consideration will also be given to modifications of the basic OMT approach, which improve the design and implementation phases of OMT.

7. Introduction to complexity - 2 Lectures
OO notation, growth rates. Measurement of execution time of real program examples and the estimation of their time complexity. Examples of time/space trade-offs.

8. Classes of algorithm - 2 Lectures
An overview will be given on the different classes of algorithm; for example, divide and conquer and greedy algorithms. Genetic algorithms will also be discussed.

9. Storing and retrieving data by key (Internal storage) - 6 Lectures
This problem will be used to motivate the discussion of a wide variety of 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. Brief introductions to proving programs correct with particular reference to the use of loop invariants. Linked representations; an introduction to hashing and binary search trees.

10. Storing and retrieving data by key (External storage) - 4 Lectures
Performance issues. Hashing and B-tree organisations. The Hashable class in Java.

11. Representing text - 4 Lectures
String matching algorithms and their performance.

12. Sorting - 4 Lectures
Divide and conquer algorithms. An introduction to proving the performance of an algorithm.

Reading Lists
** Recommended Text
Rob Pooley and Perdita Stevens. (1999) Using UML: Software engineering with objects and components. Addison-Wesley ISBN: 0201360675
T A Standish. (1998) Data Structures in Java. Addison-Wesley
Mark Allen Weiss. (1998) Data Structures and Algorithm Analysis in Java. Peachpit Press, Berkeley ISBN: 0201357542