Module Identifier CI21120  
Module Title DATA STRUCTURES AND SOFTWARE DESIGN  
Academic Year 2002/2003  
Co-ordinator Dr Mark B Ratcliffe  
Semester Semester 2 (Taught over 2 semesters)  
Other staff 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 Semester Exam   2 Hours A1 There will be regular worksheets with penalties for non-submission.   40%  
  Semester Assessment   A2 Course Work: 2 pieces of assessed coursework   50%  
  Semester Assessment   A3 Regular worksheets   10%  
  Supplementary Exam   2 Hours Written examination only   100%  
Further details http://www.aber.ac.uk/compsci/ModuleInfo/CI21120  

Learning outcomes

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

Brief description

This module builds on the foundations of the first year modules on program design and provides a thorough grounding in the design of data structures and algorithms and gives further insight into object-oriented design. This module is designed for students who are enrolled either on the Internet Computing degree or the Minor in Computer Science. It places emphasis on worked examples and covers less theoretical material than CS21120

Aims

This module provides an introduction to data structures and their use in solving programming problems. The course emphasises the use of abstract data types and the contribution that abstraction and encapsulation can make to the comprehensibility, reusability and robustness of programs. The course also examines the efficiency of well-known algorithms in order to provide a basis for students to make informed choices about data structures and algorithms. Java is used as the language of implementation with the intent of providing a means of allowing the student to naturally express these design objectives in code.

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

Content

1. Course Overview - 5 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. 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. 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 - 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).

Reading Lists

Books
T. Budd. (2001) Data Structures in Java.
Michael Main. (1999) Data Structures and Other Objects, Using Java. Addison Wesley
T.A. Standish. (1998) Data Structures in Java. Addison Wesley
Alfred Aho, John Hopcroft, and Jeffrey Ullman. (1983) Data Structures and Algorithms. Addison Wesley
Alfred Aho and Jeffrey Ullman. (1992) Foundations of Computer Science. Computer Science Press
Thomas A Standish. (1994) Data Structures, Algorithms and Software Principles. Addison Wesley
Rebecca Wirfs-Brock, Brian Wilkerson, and Lauren Wiener. (1990) Designing Object-Oriented Software. Prentice Hall