Computer Science, Prifysgol Cymru Aberystwyth University of Wales

CSM0430 (1995-96 session)
Software Development, Data Structures and Algorithms

Brief Description

Aims, Objectives, Syllabus, Booklist

Further Details

Number of lectures

60

Number of seminars/tutorials

12 (latter part of semester)

Number of practicals

6 (first part of semester)

Coordinator

Dr. Edel Sherratt

Other staff involved

Not yet known

Pre-requisites

CSM0120

Co-requisites

None

Incompatibilities

This module is not available to undergraduate students

Assessment

Assessed oursework 50%
Written exam 50%
This course is assessed at the end of Semester 2.

Timing

This module is offered in both Semester 1 and Semester 2

• introducing more advanced facilities that are available to the software engineer to improve the robustness, reusability and maintainability of software;
• applying these skills in practice using the Ada programming language;
• introducing the main Abstract Data Types common in software development.

It goes on to provide 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. Ada is used as the main language of expression with the intent of providing a means of allowing the student to express more naturally their design objectives in code.

As well as providing a solid grounding in some of the important data structures and algorithms used in Computer Science, the course stresses the development of problem solving skills through a number of programming assignments.

Objectives

• have an understanding of the concepts of problem abstraction and program design;
• be capable of realising their design in the Ada programming language producing software that is robust, reusable and maintainable;
• have an understanding of the Unix operating system at a level to support their programming requirements;
• understand the principles of abstractions and encapsulation as they apply to the design of abstract data types and programs;
• be able to design and implement significant programs in Ada;
• understand the importance of the running time behaviour of algorithms and how this is expressed and determined;
• understand some of important approaches to algorithm design such as greedy algorithms, divide and conquer and dynamic programming;
• be able to evaluate and choose appropriate data structures and algorithms for a range of programming problems;
• have an appreciation of the importance of program correctness and some of the techniques used to ensure it.

Further Design and Implementation of Computer Programs - 16 Lectures

This module looks at more advanced programming facilities available to the software developer (numbers of lectures in brackets). Composite types - arrays and records. (3) Developing robust programs - illustrated by exceptions. (4) Building abstract data types - case studies. (4) Handling persistent data - advanced input/output and files. (4)

UNIX: An environment to support component reuse? - 2 Lectures

This modules looks at some of the basic UNIX components e.g. sort , uniq and the pipe.

Introduction to telematics: - 2 Lectures

Telematic applications - mailers, teleworking, the internet.

Introduction to telecommunications: - 3 Lectures

Network protocols, communication technologies, and standards.

Introduction to the analysis of algorithms - 3 Lectures

O() notation, growth rates. This material will be used as the basis of more detailed discussions of algorithms later in this course.

Dynamic Storage Allocation - 4 Lectures

Introduction dynamic allocation (using the heap). Comparisons of bounded and unbounded forms of data structures. Discussion of the failure modes associated with pointers and dynamic allocation.

Storing and Retrieving Data by Key - 6 Lectures

This problem motivates the discussion of some important data structures and algorithms, the features of various solutions being related to the dimensions of the problem such as the volume of the data to be handled, volatility, and the operations required. Binary searching, trees, a brief look at hashing.

Another Further Look at Abstract Data Types - 3 Lectures

Building more general ADTs. Parameterisation by type using the Ada generic facility.

Storing and retrieving data in external storage - 5 Lectures

Some techniques used for storing large volumes of data on external media. Performance characteristics of disks versus memory. Using Ada Direct IO to implement persistent random-access storage. Hashing and B-tree organisations.

Representing text - 4 Lectures

A simple text editor will be used as the basis of a design case-study showing how the deign decisions concerning the different ways of representing text affect the performance and ease of implementation. String matching algorithms and their performance are examined in the context of the searching operations to be provided by the editor.

Sorting - 4 Lectures

A look at some important sorting algorithms. Divide and conquer algorithms.

Representing complex relationships: Graphs and graph algorithms - 5 Lectures

Terminology. Ways of representing graphs. A look at some graph- related problems and the algorithms used to solve them. Greedy algorithms.

The limitations of ADTs - 3 Lectures

What happens when an ADT does almost what is required. An introduction to the concepts of object-oriented programming and design and the object-oriented features of Ada 9x.

Designing software in other languages - 3 Lectures

The importance of applying good design practices when using other languages. A brief examination of C++.

Practicals - 6 Practicals

This module has a heavy practical content which is used to give students experience of the techniques that are described in class.

Students are likely to need ready access to the following

Mark Allen Weiss. Data Structures and Algorithm Analysis in Ada. Benjamin/Cummings, Redwood City, California, 1993.

The following should be consulted for different approaches or for further information

Alfred Aho, John Hopcroft, and Jeffrey Ullman. Data Structures and Algorithms. Addison-Wesley, Reading, Massachusetts, 1983.

Alfred Aho and Jeffrey Ullman. Foundations of Computer Science. Computer Science Press, New York, 1992.

Grady Booch and Doug Bryan. Software Engineering with Ada. Benjamin/Cummings, Redwood City, California, 3rd. edition, 1994.

Timothy A. Budd. Classic Data Structures in C++. Addison-Wesley, 1994.

Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, Massachusetts, 1990.

Robert L Kruse. Data Structures and Program Design. Prentice-Hall, Englewood Cliffs, New Jersey, second edition, 1987. (The first edition is also available from the library).

Thomas A Standish. Data Structures, Algorithms and Software Principles. Addison-Wesley, Reading, Massachusetts, 1994.

Version 1.9

John Hunt Departmental Advisor