Module Identifier CO21120  
Module Title DATA STRUCTURES, ALGORITHMS AND SOFTWARE DESIGN  
Academic Year 2007/2008  
Co-ordinator Mr Christopher W Loftus  
Semester Available all semesters  
Other staff Mr David J Smith  
Pre-Requisite Available only to students taking the Diploma/MSc in Computer Science scheme in Singapore.  
Course delivery Other   Contact Hours. 55 hours of contact time; lectures, practicals, workshops. 145 hours of private study, practical work and assessment.  
Assessment
Assessment TypeAssessment Length/DetailsProportion
Semester Exam2 Hours (A1)  75%
Semester Assessment (A2) Assignment  25%
Supplementary Exam Supplementary examination will take the same form, under the terms of the Department's policy.   
Further details http://www.aber.ac.uk/compsci/ModuleInfo/CO21120  

Learning outcomes

On successful completion of this module, students should be able to:


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

Aims

The aims of this module are to:

Content

1. Introduction - 15 Lectures
Course Overview. An introduction into time/space complexity. Mathematical underpinnings. Issues of correctness as they relate to the definition of ADTs. The key ideas of abstraction and encapsulation. Notations for describing ADTs. 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 - 4 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. P and NP.

4. Recursion - 3 Lectures
An introduction to recursive thinking. Examples of recursion.

5. Storing and Retrieving Data by Key (1) - 12 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 and heaps.

6. Storing and Retrieving Data by Key (2): External storage - 4 Lectures
Performance issues. Hashing and B-tree organisations. The Hashable class in Java.

7. Representing Text - 4 Lectures
String matching algorithms and their performance. Search engines case study.

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 - 6 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).

Reading Lists

Books
Alfred Aho and Jeffrey Ullman (1995) Foundations of Computer Science W H Freeman & Co. 0716782847
Alfred Aho, John Hopcroft, and Jeffrey Ullman (1983) Data Structures and Algorithms Addison Wesley 0201000237
Michael Main (Oct 1998) Data Structures and Other Objects Using Java Addison-Wesley 0201357445
Rebecca Wirfs-Brock, Brian Wilkerson, and Lauren Wiener (1990) Designing Object-Oriented Software Prentice Hall 0136298257
T. Budd (2001) Classic Data Structures in Java Addison-Wesley Pub Co 0201700026
T.A. Standish (1998) Data Structures in Java Addison Wesley 020130564X
Thomas A Standish (1994) Data Structures, Algorithms and Software Principles Addison-Wesley, Reading, Massachusetts 0201591189

Notes

This module is at CQFW Level 5