Students should be able to design, program and evaluate relatively complex computer-based systems which model process-oriented problems in many subject and application areas.
Students should be able to:
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 re-use). Specific attention should be paid to algorithms and strategies for simulating advanced linear and non-linear data structures for the implementation of abstract data types.
This unit extends and builds on unit GS1: Foundations of Programming and Software Development. Students will solve several, increasingly-complex problems from real application areas.
Students develop models for relatively complex process-oriented 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.
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.
Students construct sophisticated linear and tree-like 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.
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.
Students determine order of magnitude indicators to compare algorithms, and practice some basic formal methods of program verification.
Where time is available, design strategies using other development paradigms, such as object-oriented methodology or logic programming, may be explored if resources make this possible.
Design for reliability, reuse
Analysis strategies, such as data flow analysis using pre- and post- conditions
Formal program verification, assertions, invariants
Data abstraction and information hiding
Effective user interfaces
Graphs and graph algorithms
Encapsulation of abstract data types
Dynamic data types and structures
Binary search trees
Advanced searching algorithms
Efficient non-quadratic sorting algorithms
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
Non-linear table data structures
Applications in graphics, robotics, or artificial intelligence
Modelling using logic or functional programming
Parallel processing of algorithms
Minimum necessary resources:
A high-level, 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.
Programming environments for logic, functional, object-oriented programming or parallel processing.
Foundations of Programming and Software Development (GS1)
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 sub-units and curriculum development.