Module Identifier |
CSM1220 |
Module Title |
DATA STRUCTURES, ALGORITHMS AND SOFTWARE DESIGN |
Academic Year |
2001/2002 |
Co-ordinator |
Mr Christopher Loftus |
Semester |
Available all semesters |
Pre-Requisite |
CSM1020 |
Course delivery |
Contact Hours | 55 Hours plus around 100 hours of self study and practical work |
Assessment |
Course work | | 20% |
|
Exam | 3 Hours | 80% |
Further details |
http://www.aber.ac.uk/compsci/ModuleInfo/CSM1220 |
Syllabus
Course Overview -
Time/space complexity. Issues of correctness as they relate to the definition of ADTs. Abstraction and encapsulation. Notations for describing ADTs. Review of Java support for their implementation: packages, exceptions and interfaces.
Further Design and Implementation of Computer Programs -
Programming language facilities to support more advanced data structures and the development of larger, more reusable software. Linear data structures: stacks, queues and lists of objects, implemented using arrays and utilising interfaces.
Dynamic Storage Allocation -
Unbounded data structures and a comparison with their bounded equivalents. Implementation of dynamic storage allocation in run-time systems; 'heap creep'.
Object-Oriented Techniques -
Object-oriented analysis and design. The Unified Modelling Language (UML). The Unified Process, a recipe for developing UML diagrams during object oriented analysis and design.
Introduction to Complexity -
OO notation, growth rates. Measurement of execution time of program examples and the estimation of their time complexity. Examples of time/space trade-offs.
Storing and Retrieving Data by Key From Internal Storage -
Binary search trees, 2-3 trees. How the characteristics of the problem (data volumes, volatility and relative frequency of the different operations) affect the choice of data structure.
Storing and Retrieving Data by Key from External Storage -
Performance issues. Hashing and B-tree organisations. The Hashable class in Java.
Sorting -
Quicksort, Mergesort and Selection Sort and their time complexities.
Graphs -
Weighted, directed graphs. Shortest path algorithms, breadth first and depth first searching. Minimum spanning trees and topological sorting.
Learning outcomes
On successful completion of the module, students should:
-
have an understanding of the concepts of problem abstraction and program design;
-
be capable of realising their designs in software that is robust, reusable and maintainable;
-
understand the principles of abstractions and encapsulation, as they apply to object-oriented design;
-
understand the importance of the ideas of space and time complexity and be able to use them to predict the behaviour of simple systems;
-
understand and be able to use a variety of 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.
Aims
The aims of this module are to:
-
introduce students to the standard data structures and algorithms that form the common currency of software design;
-
develop students' understanding of the object-oriented model of software;
-
introduce students to the analysis and prediction of performance.
General description
In the 40 or so years that people have been developing software, a range of common tasks, such as sorting and searching, have been identified and a body of knowledge has been accumulated about how these tasks are best carried out. This knowledge usually consists of various ways of structuring the data, a range of different algorithms, and performance analysis that enables a designer to chose the algorithm and data structure most appropriate to the circumstances of the system, and to predict how the system will perform.
This module introduces students to this body of knowledge and sets it into the context of modern software design and structuring techniques.
Reading Lists
Books
** Consult For Futher Information
Robert L Kruse.. (1994 O/P)
Data Structures and Program Design. 3rd. Prentice-Hall, Englewood Cliffs, New Jersey 0132081822
Alfred Aho, John Hopcroft, and Jeffrey Ullman.. (1983)
Data Structures and Algorithms. Addison-Wesley, Reading, Massachusetts 0201000237
Alfred Aho and Jeffrey Ullman.. (1992)
Foundations of Computer Science. Computer Science Press, New York 0716782332
Hans-Erik Eroksson and Magnus Penker. (1997)
UML Toolkit. Wiley, New York 0471191612
Michael Main.. (1999)
Data Structures and Other Objects Using Java. Addison-Wesley 0201357445
Rob Pooley and Pardita Stevens. Addison-Wesley, 1999.. (1999)
Using UML: Software enginering with objects and components. Addison-Wesley 0201360675
Grady Booch. (1994)
Object-Oriented Analysis and Design. Addison-Wesley 080535402
Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest.. (2001)
Introduction to Algorithms. 2nd ed. MIT Press, Cambridge, Massachusetts 0262531968
John E Hunt. (1998)
Java and Object Orientation: An Introduction. Springer Verlag 03540762019
Rebecca Wirfs-Brock, Brian Wilkerson, and Lauren Wiener.. (1990)
Designing Object-Oriented Software. Prentice Hall 0136298257
T A Standish. (1998)
Data Structures in Java. Addison-Wesley 020130564X
T A Standish. (1994)
Data Structures, Algorithms and Software Principles. Addison-Wesley 0201528800
Robert Sedgewick. (1988)
Algorithms. Addison-Wesley 0201066734
J. Rumbaugh, M. Blaha, W. Permerlani, F Eddi, and W Lorensen. Prentice-Hall, 1991.. (1991)
Object-Oriented Modeling and Design. Prentice-Hall 0136298419