Computer Science, Prifysgol Cymru Aberystwyth University of Wales
CSM0310 - Software Development, Data Structures and Algorithms II
Brief Description
This module introduces students to the more advanced
techniques for the detailed specification and design of programs.
Building on the techniques presented in
CSM0220
, this module
provides a thorough grounding in the design of data structures and
algorithms.
This course is assessed at the end of the Easter
vacation.
Aims, Objectives, Syllabus, Booklist
Further Details
- Number of lectures
- 24 (6 * 4)
- Number of seminars/tutorials
- 6
- Number of practicals
- 0
- Coordinator
- Dr. Edel Sherratt
- Other staff involved
- Not yet known
- Pre-requisites
-
CSM0220
- Co-requisites
- None
- Incompatibilities
- This module is not available to undergraduate students
- Assessment
- Assessed coursework 50%
Written exam 50%
- Timing
- This module is offered in the early part of Semester
2
Aims
This module builds on the foundation provided by
CSM0220
and provides 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
On completion of this module, students should:
-
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.
Syllabus
-
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++.
Booklist
It is considered essential to purchase 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.
(Earlier editions are also available in the library).
-
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.7
Syllabus
Nigel Hardy Departmental Advisor
nwh@aber.ac.uk
Dept of Computer Science, UW Aberystwyth (disclaimer)