This module introduces the abstract behaviour of the fundamental list based data structures, their associated algorithms and alternative implementations. A description, analysis and comparison of the classic algorithms for the common problem of sorting is also included as are the techniques involved in devising, writing and computing the efficiency of algorithms.
Introduction: Data types; need for data structures; derivation and specification of algorithms.
Abstract Data Types: Definition; how to specify abstract data types (ADTs);
Algorithm Analysis: Calculating the running time of a program; best, worst and average cases; asymptotic analysis; O notation; comparing analysis results.
List based Data Structures: Arrays; lists; stacks, queues; priority queues;
Sorting: Internal sorting; sample sorts with various complexities: bubble, selection, insertion, quick, and radix sort; comparison of sorting algorithms;
This module is delivered over four hours a week. There is a two hour lecture where students are taught the module content and two lab hours which gives the students the oppertunity to apply the knowledge learned in the lecture though the use of execerise sheets.
| Module Content & Assessment | |
|---|---|
| Assessment Breakdown | % |
| Formal Examination | 60 |
| Other Assessment(s) | 40 |