Appendices Appendix D ICT specialisation Unit GS2 - Advanced elements of programming
Previous TOC Next

UNIT GS2 – ADVANCED ELEMENTS OF PROGRAMMING

Objective

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.

Sub-objectives

Students should be able to:

  1. methodically analyse and model relatively complex process-oriented problems in a variety of application areas;
  2. apply moderately advanced formal analysis, design and data abstraction techniques to design effective algorithms, abstract data types and relatively sophisticated data structures;
  3. code and realise programs and sub-programs (modules) using a general purpose programming environment;
  4. evaluate and explore alternative designs to programs.

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

Content

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.

Problem Analysis

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.

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

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 object-oriented 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 non-quadratic 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
Non-linear table data structures

Optional

Applications in graphics, robotics, or artificial intelligence
Modelling using logic or functional programming
Object-oriented programming
Parallel processing of algorithms

Resources

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.

Optional resources

Programming environments for logic, functional, object-oriented 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 sub-units and curriculum development.