Module Identifier | CI21120 | ||
Module Title | DATA STRUCTURES AND SOFTWARE DESIGN | ||
Academic Year | 2002/2003 | ||
Co-ordinator | Dr Mark B Ratcliffe | ||
Semester | Semester 2 (Taught over 2 semesters) | ||
Other staff | Dr Lynda A Thomas | ||
Pre-Requisite | CI12420 or CS12420 | ||
Co-Requisite | None | ||
Mutually Exclusive | CS21120 | ||
Course delivery | Lecture | 44 lectures | |
Practical | Up to 16 x 2hr | ||
Other | Workshop. Up to 4 | ||
Assessment | Semester Exam | 2 Hours A1 There will be regular worksheets with penalties for non-submission. | 40% |
Semester Assessment | A2 Course Work: 2 pieces of assessed coursework | 50% | |
Semester Assessment | A3 Regular worksheets | 10% | |
Supplementary Exam | 2 Hours Written examination only | 100% | |
Further details | http://www.aber.ac.uk/compsci/ModuleInfo/CI21120 |
As well as providing a solid grounding in the major data structures and algorithms of Computer Science, the course stresses the development of problem solving skills through a number of programming worksheets.
2. Introduction to Complexity - 3 Lectures
O() notation, growth rates. Measurement of execution time of some real programs and estimation of their time complexity. Some examples of time/space trade-offs.
3. Classes of Algorithm - 2 Lectures
An overview will be given on the different classes of algorithm; for example, divide and conquer and greedy algorithms. Genetic algorithms will also be discussed.
4. Recursion - 2 Lectures
An introduction to recursive thinking. Examples of recursion.
5. Storing and Retrieving Data by Key (1) - 15 Lectures
This problem will be used to motivate the discussion of a wide variety of different implementation techniques. The features of some typical solutions will be related to the dimensions of the problem such as the volume of data to be handled, volatility and the operations required. Internal Storage: linear and binary searching. Linked representations; an introduction to hashing, binary search trees, AVL trees and heaps.
6. Storing and Retrieving Data by Key (2): External storage - 6 Lectures
Performance issues. Hashing and B-tree organisations. The Hashable class in Java.
7. Representing Text - 4 Lectures
String matching algorithms and their performance. Search engines case study.
8. Sorting - 4 Lectures
A comparison of divide and conquer, priority queue and address calculation based sorting algorithms. Performance characteristics of these algorithms will be discussed.
9. Representing Complex Relationships: Graphs - 3 Lectures
Some examples of greedy algorithms. Terminology and implementation considerations. A look at some graph-related problems such as: finding a route (shortest paths); planning a communications network (minimum spanning trees); network routing management (flow graphs); compiling a program or planning a project (topological sorting).