


Objective
Students should be able to design, program and evaluate relatively complex computerbased systems which model processoriented problems in many subject and application areas.
Subobjectives
Students should be able to:
Context
Students should develop skills for solving more complex and sophisticated problems in many application areas. Emphasis needs to be placed on modelling through data abstraction (an important technique for improving reliability and reuse). Specific attention should be paid to algorithms and strategies for simulating advanced linear and nonlinear data structures for the implementation of abstract data types.
Content
This unit extends and builds on unit GS1: Foundations of Programming and Software Development. Students will solve several, increasinglycomplex problems from real application areas.
Problem Analysis
Students develop models for relatively complex processoriented systems using design strategies, such as modelling through abstract data types. They analyse systems to determine basic data objects, and associated functions which are used on these objects in the system.
Design
Students develop abstract data types for the identified objects, which may be reused in other designs which involve the same objects. Students design a solution for the problem expressed in terms of modules which manipulate the abstract data objects only through the identified functions. Students design a suitable and effective user interface.
Programming
Students construct sophisticated linear and treelike data structures to represent the abstract data types and also construct the functions needed to access these abstract data types in a general purpose programming language which supports information hiding and encapsulation, either directly or through simulation of data abstractions. Students code their design in the programming language.
Realisation
The coded programs are realised and run in the programming environment. Students first realise, test and verify the realisation of the abstract data types, and only then the entire program.
Evaluation
Students determine order of magnitude indicators to compare algorithms, and practice some basic formal methods of program verification.
Alternative approaches
Where time is available, design strategies using other development paradigms, such as objectoriented methodology or logic programming, may be explored if resources make this possible.
Topics
Software engineering
Design for reliability, reuse
Analysis
Analysis strategies, such as data flow analysis using pre and post conditions
Formal program verification, assertions, invariants
Design
Data abstraction and information hiding
Effective user interfaces
Algorithms
Graphs and graph algorithms
Encapsulation of abstract data types
Dynamic data types and structures
Binary trees
Binary search trees
Advanced searching algorithms
Efficient nonquadratic sorting algorithms
Hashing methods
Evaluation
Algorithm analysis for order of magnitude approximation
Limitations of algorithms and unsolvable problems
Limits of numerical representations and simple numerical methods
Programming Language Elements
Singly and doubly linked list representations
Stacks
Queues
Nonlinear table data structures
Optional
Applications in graphics, robotics, or artificial intelligence
Modelling using logic or functional programming
Objectoriented programming
Parallel processing of algorithms
Resources
Minimum necessary resources:
A highlevel, structured programming language environment, which supports modular program design and data abstraction.
Intermediate level, modern text book on data structures and algorithm analysis which uses a data abstraction approach.
Optional resources
Programming environments for logic, functional, objectoriented programming or parallel processing.
Links
Foundations of Programming and Software Development (GS1)
Methodology
Emphasis is on concepts, theories, and practices of the discipline rather than on exhaustive coverage of language syntax. It is advisable to use, if possible, the same structured programming language for both units. The unit has an established traditional content which is described in many advanced texts on data structures. Teachers and curriculum designers should consider using the structure of these texts as the basis for subunits and curriculum development.