Description
Aims:
To introduce more formal aspects of algorithms and data structures, techniques for analysing the complexity of algorithms, and to discuss the limits of computation (intractable and undecidable problems).
Intended learning outcomes:
On successful completion of the module, a student will be able to:
- Understand how to use a variety of data structures.
- Understand a variety of common algorithms and why some are more efficient than others
- Carry out time complexity analysis in a variety of scenarios.
- Discuss intractable and undecidable problems.
Indicative content:
The following are indicative of the topics the module will typically cover:
Algorithms and Data Structures:
- Why study algorithms and data structures?
- Pseudocode.
- Efficiency of algorithms.
- Recursion.
- Arrays.
- Approaches to algorithm design including greedy and divide and conquer.
- Graph traversal.
Analysis of Algorithms:
- Empirical vs theoretical analysis.
- Algorithmic complexity.
- O-notation.
- Forms of time complexity analysis (worst case, average case, best worst case).
- Sums of series and simple summation formulae.
- Recursive algorithms and recurrence relations.
Limits of Computation:
- Tractable and intractable problems.
- The complexity classes P, NP, NPC.
- Undecidability.
Requisites:
To be eligible to select this module, a student must: (1) be registered on a programme and year of study for which it is a formally available; and (2) have also selected Introductory Programming (COMP0066), App Engineering (COMP0067), and Computer Architecture and Operating Systems (COMP0068).
Module deliveries for 2024/25 academic year
Last updated
This module description was last updated on 19th August 2024.
Ìý