Module Identifier | CI21120 | |||||||||||||||||

Module Title | DATA STRUCTURES AND SOFTWARE DESIGN | |||||||||||||||||

Academic Year | 2004/2005 | |||||||||||||||||

Co-ordinator | Dr Lynda A Thomas | |||||||||||||||||

Semester | Semester 2 (Taught over 2 semesters) | |||||||||||||||||

Other staff | Dr Joanne H Walker, Dr Lynda A Thomas | |||||||||||||||||

Pre-Requisite | CI12420 or CS12420 | |||||||||||||||||

Co-Requisite | None | |||||||||||||||||

Mutually Exclusive | CS21120 | |||||||||||||||||

Course delivery | Lecture | 44 lectures | ||||||||||||||||

Practical | Up to 16 x 2hr | |||||||||||||||||

Other | Workshop. Up to 4 | |||||||||||||||||

Assessment |
| |||||||||||||||||

Further details | http://www.aber.ac.uk/compsci/ModuleInfo/CI21120 |

- demonstrate their understanding of the principles of abstraction and encapsulation as they apply to the design of abstract data types and programs (A1, A2);
- analyse and evaluate the time and space behaviour of algorithms and understand how this is expressed and determined (A1, A2, A3);
- recognise the importance of this analysis in the design of software (A1, A2);
- recognise the importance of the classes P and NP in the analysis of algorithms (A1);
- describe some of the main approaches to algorithm design such as greedy algorithms, divide and conquer and dynamic programming (A1);
- demonstrate judgement in evaluating and choosing appropriate data structures and algorithms for a range of programming problems (A1, A2);
- design and implement significant programs in Java (A2, A3).

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. Review of Java support for their implementation: packages, exceptions and interfaces.

2. Introduction to Complexity - 3 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.

3. 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.

4. Recursion - 2 Lectures

An introduction to recursive thinking. Examples of recursion.

5. Storing and Retrieving Data by Key (1) - 15 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. Linked representations; an introduction to hashing, binary search trees, AVL trees and heaps.

6. Storing and Retrieving Data by Key (2): External storage - 6 Lectures

Performance issues. Hashing and B-tree organisations. The Hashable class in Java.

7. Further Techniques for Designing Software - 4 Lectures

How course topics relate to programming problems, including design patterns.

8. Sorting - 4 Lectures

A comparison of divide and conquer, priority queue and address calculation based sorting algorithms. Performance characteristics of these algorithms will be discussed.

9. Representing Complex Relationships: Graphs - 3 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).

Nell Dale et al (2002)

Alfred Aho, John Hopcroft, and Jeffrey Ullman (1983)

Alfred Aho and Jeffrey Ullman (1992)

Thomas A Standish (1994)

Rebecca Wirfs-Brock, Brian Wilkerson, and Lauren Wiener (1990)

T. Budd (2001)

Michael Main (1999)

T.A. Standish (1998)

This module is at CQFW Level 5