- Homepage
- Key Information
- Students
- Taught programmes (UG / PGT)
- Student Services and Procedures
- Student Support
- Events and Colloquia
- International Students
- Students as Change Agents (SACA)
- Student Staff Liaison Committees (SSLC)
- The Exeter Award
- Peer Support
- Skills Development
- Equality and Diversity
- Athena SWAN
- Outreach
- Living Systems Institute Webpage
- Alumni
- Info points and hubs

- Staff
- PGR
- Health and Safety
- Computer Support
- National Student Survey (NSS)
- Intranet Help
- College Website

## ECM1414 - Data Structures and Algorithms (2019)

MODULE TITLE | Data Structures and Algorithms | CREDIT VALUE | 15 |
---|---|---|---|

MODULE CODE | ECM1414 | MODULE CONVENER | Prof Ronaldo Menezes (Coordinator) |

DURATION: TERM | 1 | 2 | 3 |
---|---|---|---|

DURATION: WEEKS | 11 |

Number of Students Taking Module (anticipated) | 73 |
---|

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.

Scheduled Learning & Teaching Activities | 32.00 | Guided Independent Study | 118.00 | Placement / Study Abroad | 0.00 |
---|

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 |

Form of Assessment | Size of Assessment (e.g. duration/length) | ILOs Assessed | Feedback Method |
---|---|---|---|

In Class Test | 1 hour | All | In class |

Coursework | 20 | Written Exams | 80 | Practical Exams | 0 |
---|

Form of Assessment | % of Credit | Size of Assessment (e.g. duration/length) | ILOs Assessed | Feedback Method |
---|---|---|---|---|

Coursework | 20 | 6 pages | 1,2,7,8,10,11 | Written feedback sheet |

Examination | 80 | 2 hours - Summer Exam Period | All | On request |

Original Form of Assessment | Form of Re-assessment | ILOs Re-assessed | Time Scale for Re-reassessment |
---|---|---|---|

All | Written exam | All | August Ref/Def period |

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.

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

Set | Cormen T, Leiserson C, Rivest R, Stein C | Introduction to Algorithms | 3rd Edition | MIT Press | 2009 | [Library] | |

Set | Aho, A., Ullman, J., Hopcroft, J. | Data Structures and Algorithms | Addison Weslett | 1983 | [Library] |

CREDIT VALUE | 15 | ECTS VALUE | 7.5 |
---|---|---|---|

PRE-REQUISITE MODULES | ECM1415, ECM1400 |
---|---|

CO-REQUISITE MODULES |

NQF LEVEL (FHEQ) | 1 (NQF Level 4) | AVAILABLE AS DISTANCE LEARNING | No |
---|---|---|---|

ORIGIN DATE | Tuesday 10 July 2018 | LAST REVISION DATE | Tuesday 10 July 2018 |

KEY WORDS SEARCH | Data structures; algorithms; computational complexity. |
---|