Data Structures and Algorithms - 2019 entry

According to an old formula, Algorithms + Data Structures = Programs. This remains as true today as when it was originally formulated by Niklaus Wirth in 1976, and encapsulates the truism that all computation consists of the manipulation of data by means of systematic procedures. But data comes in many different forms (e.g., numerical, alphabetical, graphical) and only by knowing how it is structured can we specify the procedures – algorithms – for manipulating it to produce desired outcomes.  Thus the study of data structures and algorithms constitutes an integrated topic, which forms the subject matter of this module. You will be introduced to some of the key concepts in the area, with plenty of examples to illustrate them, and will be given a chance to demonstrate your understanding by undertaking exercises. This module builds on the programming knowledge you have already acquired from ECM1408 (Programming for Science) and will make use of mathematical tools introduced in ECM1415 (Discrete Mathematics for Computer Science) to enable data structures and algorithms to be described precisely.

Prerequisite module: ECM1400, ECM1415 or equivalent

The aim of this module is to introduce you to the fundamental role played by data structures and algorithms in computer science. You will already have acquired some practical understanding of data structures and how they work from the programming module; now it is time to put this understanding on a more formal and theoretically-grounded footing by introducing a systematic framework for the description and manipulation of data structures. This will pave the way for a systematic study of algorithms, the abstract procedures that may be implemented in concrete form within computer programs. In particular, you will be introduced to the study of computational complexity, which provides measures of the efficiency of algorithms (in terms of memory utilisation and running time) and can also characterise the complexity of problems in terms of the optimum efficiency of algorithms for solving them.

On successful completion of this module, you should be able to:

 

Module Specific Skills and Knowledge:
1 demonstrate a familiarity with a range of fundamental data structures used in computing;
2 use the formalism of abstract data types to construct precise specifications of data structures and derive their properties;
3 describe the properties of algorithms, explaining clearly their relationship to programs and to heuristics;
4 give rigorous specifications of algorithms and construct solutions to algorithmic tasks using pseudocode;
5 show an awareness of the issues of termination and correctness, demonstrating these for some simple examples;
6 make use of recursion and iteration in constructing algorithms;
7 explain the meaning of computational complexity, distinguishing space and time complexity, and evaluating the complexity of a range of different algorithms;
8 display an awareness of the phenomenon of NP-completeness, giving examples of problems known to be NP-complete and explaining the significance of NP-completeness for practical computation.
Discipline Specific Skills and Knowledge:
9 demonstrate enhanced practical skills in programming and problem analysis as a result of the deeper theoretical understanding gained from this module.
10 describe computational phenomena using a range of key theoretical concepts.
Personal and Key Transferable / Employment Skills and Knowledge:
11 present and explain abstract ideas using a systematic approach.

- recapitulation of fundamental data structures used in computing: lists, stacks, queues, trees, graphs, digraphs;

- abstract data types: distinguished elements, operations and relations; models; morphisms;

- what an algorithm is;

- algorithms vs heuristics;

- specification and pseudocode;

- termination and correctness;

- iteration and recursion;

- space and time complexity (including recapitulation of logarithmic, polynomial and exponential functions, order notation);

- use of searching and sorting as running examples to illustrate the foregoing;

- NP-completeness and the travelling salesman problem.

Referred and deferred assessment will normally be by examination. For referrals, only the examination will count, a mark of 40% being awarded if the examination is passed. For deferrals, candidates will be awarded the higher of the deferred examination mark or the deferred examination mark combined with the original coursework mark.

ELE – College to provide hyperlink to appropriate pages

Reading list for this module: