Module Identifier CS21120  
Module Title PROGRAM DESIGN, DATA STRUCTURES AND ALGORITHMS  
Academic Year 2004/2005  
Co-ordinator Mr Richard C Shipman  
Semester Semester 2 (Taught over 2 semesters)  
Other staff Dr Lynda A Thomas, Mr Richard C Shipman, Dr Reyer Zwiggelaar, Dr Simon M Garrett  
Pre-Requisite CS12420 or CS10720  
Course delivery Lecture   44 lectures  
  Practical   Up to 20 x 1 hr (start in week 5)  
  Other   Workshop. Up to 4 x 1hr  
Assessment
Assessment TypeAssessment Length/DetailsProportion
Semester Exam2 Hours A1 Written examination40%
Semester Assessment A3 Regular worksheets  10%
Semester Assessment A2 Course Work: Two pieces. There will also be regular worksheets with penalties for non-submission.50%
Supplementary Exam Will take the same form, under the terms of the Department's policy.   
Further details http://www.aber.ac.uk/compsci/ModuleInfo/CS21120  

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.

Aims

This module provides an introduction to data structures and their use in solving programming problems. The module 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 module 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.

The module is also concerned with the reuse of software design patterns and frameworks, thereby reducing the need to build programs from first principles.

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

Content

1. Module Overview - 1 Lecture

An overview of the method of teaching and assessment, and a road-map of the topics to be covered and their relationships. Some basic concepts are introduced.

2. Program design issues - 4 Lectures

Explanation of design issues such as object-orientation and identification of components through case-study examples.

3. Design patterns and frameworks - 5 Lectures

An introduction to object-oriented design patterns and frameworks. Support for reuse. General concepts, representation and examples. How patterns may be implemented in Java.

4. Introduction to Complexity - 2 Lectures

O() notation, growth rates. Measurement of execution time of some example programs and estimation of their time complexity. P and NP.

5. Classes of Algorithm - 2 Lectures

An overview will be given on the different classes of algorithm; for example, divide and conquer and greedy algorithms.

6. Recursion - 2 Lectures

An introduction to recursive thinking. Examples of recursion.

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

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

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

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

10. Representing Complex Relationships: Graphs - 7 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
Steven John Metsker (2002) The Design Patterns Java Workbook (Addison-Wesley Workbook) Addison-Wesley ISBN: 0201743973
Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides (1995) Design Patterns, Elements of Reusable Object-Oriented Software Addison-Wesley ISBN: 0201633612
Martin Fowler (2003) UML Distilled: A Brief Guide to the Standard Object Modeling Language (Addison-Wesley Object Technology S.), Addison Wesley. ISBN: 0321193687
Alfred Aho, John Hopcroft, and Jeffrey Ullman (1983) Data Structures and Algorithms Addison-Wesley, Reading, Massachusetts ISBN: 0201000237
Alfred Aho and Jeffrey Ullman (1995) Foundations of Computer Science W H Freeman & Co. ISBN: 0716782847
T. Budd (2001) Classic Data Structures in Java Addison-Wesley Pub Co ISBN: 0201700026
Thomas A Standish (1994) Data Structures, Algorithms and Software Principles Addison-Wesley, Reading, Massachusetts ISBN: 0201591189
Rebecca Wirfs-Brock, Brian Wilkerson, and Lauren Wiener (1990) Designing Object-Oriented Software Prentice Hall ISBN: 0136298257
Michael Main (1999) Data Structures and Other Objects, Using Java Addison Wesley ISBN 0201357445
T.A. Standish (1998) Data Structures in Java Addison Wesley ISBN: 020130564X

Notes

This module is at CQFW Level 5