Skip to main content

Study information

# Data Structures and Algorithms - 2023 entry

MODULE TITLE CREDIT VALUE Data Structures and Algorithms 15 ECM1414 Prof Ronaldo Menezes (Coordinator)
DURATION: TERM 1 2 3
DURATION: WEEKS 11
 Number of Students Taking Module (anticipated) 73
DESCRIPTION - summary of the module content

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

AIMS - intentions of the module

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.

INTENDED LEARNING OUTCOMES (ILOs) (see assessment section below for how ILOs will be assessed)

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.

SYLLABUS PLAN - summary of the structure and academic content of the module

- 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.

LEARNING AND TEACHING
LEARNING ACTIVITIES AND TEACHING METHODS (given in hours of study time)
 Scheduled Learning & Teaching Activities Guided Independent Study Placement / Study Abroad 32 118 0
DETAILS OF LEARNING ACTIVITIES AND TEACHING METHODS
 Category Hours of study time Description Scheduled learning and teaching 22 Lectures Scheduled learning and teaching 10 Tutorials Guided independent study 30 Coursework Guided independent study 88 Private reading

ASSESSMENT
FORMATIVE ASSESSMENT - for feedback and development purposes; does not count towards module grade
Form of Assessment Size of Assessment (e.g. duration/length) ILOs Assessed Feedback Method
In Class Test 1 hour All In class

SUMMATIVE ASSESSMENT (% of credit)
 Coursework Written Exams Practical Exams 100 0 0
DETAILS OF SUMMATIVE ASSESSMENT
Form of Assessment % of Credit Size of Assessment (e.g. duration/length) ILOs Assessed Feedback Method
Written Exam 100 1 hour (summer) All Written feedback sheet

DETAILS OF RE-ASSESSMENT (where required by referral or deferral)
Original Form of Assessment Form of Re-assessment ILOs Re-assessed Time Scale for Re-reassessment
All Written exam (1 hour) All August Ref/Def period

RE-ASSESSMENT NOTES
Reassessment will be by written exam only. For referred candidates, the mark will be capped at 40%. For deferred candidates, the exam mark will be uncapped.
RESOURCES
INDICATIVE LEARNING RESOURCES - The following list is offered as an indication of the type & level of
information that you are expected to consult. Further guidance will be provided by the Module Convener

ELE – College to provide hyperlink to appropriate pages

Reading list for this module:

Type Author Title Edition Publisher Year ISBN
Set Cormen T, Leiserson C, Rivest R, Stein C Introduction to Algorithms 3rd Edition MIT Press 2009
Set Aho, A., Ullman, J., Hopcroft, J. Data Structures and Algorithms Addison Weslett 1983
CREDIT VALUE ECTS VALUE 15 7.5
PRE-REQUISITE MODULES ECM1415, ECM1400
NQF LEVEL (FHEQ) AVAILABLE AS DISTANCE LEARNING 1 (NQF Level 4) No Tuesday 10th July 2018 Wednesday 8th February 2023
KEY WORDS SEARCH Data structures; algorithms; computational complexity.

Please note that all modules are subject to change, please get in touch if you have any questions about this module.