CM22008: Algorithms and complexity
[Page last updated: 03 June 2024]
| Academic Year: | 2024/25 |
| Owning Department/School: | Department of Computer Science |
| Credits: | 10 [equivalent to 20 CATS credits] |
| Notional Study Hours: | 200 |
| Level: | Intermediate (FHEQ level 5) |
| Period: |
- Academic Year
|
| Assessment Summary: | CWSI 25%, EXCB 75% |
| Assessment Detail: |
- Set exercises individual (CWSI 25%)
- Closed-book written examination (EXCB 75%)
|
| Supplementary Assessment: |
- Like-for-like reassessment (where allowed by programme regulations)
|
| Requisites: |
Before taking this module you must take CM12005
|
| Learning Outcomes: |
At the end of this unit, you will be able to:
- describe the fundamental models of computation and the corresponding classes of formal grammars and languages;
- design algorithms for specific computational problems as automata of appropriate types;
- prove mathematically that some computational problems are undecidable within a particular class of computational models;
- determine the complexity of a variety of algorithms;
- describe a variety of data structures and algorithms and choose appropriate ones for solving a given computational problem;
- for a variety of algorithms, demonstrate their correctness in certain respects.
|
| Synopsis: | You will explore fundamental models of computation such as finite automata and Turing machines, design algorithms within a given model, and formally prove that a problem cannot be addressed within a given model. You will learn about a variety of data structures and choose an appropriate one for a given problem. You will determine the computational complexity of algorithms and demonstrate their correctness.
|
| Content: | Regular languages; deterministic and non-deterministic finite automata; existence of non-regular languages via the Pumping Lemma.
Context-free languages; pushdown automata; context-free grammars; parsing in context-free languages; existence of non-context-free languages via the Pumping Lemma.
Turing machines; Church-Turing Thesis; Universal Turing machine and undecidability of the halting problem.
Non-deterministic Turing machines; complexity classes P and NP; P vs NP problem.
Data structures such as lists, stacks, queues, trees, hash tables, heaps, graphs, and self-balancing trees.
Methods of designing efficient algorithms such as divide-and-conquer, recursion, dynamic programming, and greedy algorithms.
Complexity; best, worst and average cases; time, space and other measures; big Ο , big Θ and big Ω notation.
Analysis of algorithms such as sorting algorithms, graph algorithms, and algorithms for linear algebra.
Basic correctness techniques including loop invariants.
Algorithms and data structures in practice; crossover points between algorithms; polyalgorithms; computationally hard problems in everyday life.
|
| Course availability: |
CM22008 is Compulsory on the following courses:
Department of Computer Science
- USCM-AFB30 : BSc(Hons) Computer Science (Year 2)
- USCM-AFB31 : BSc(Hons) Computer Science and Artificial Intelligence (Year 2)
- USCM-AKB31 : BSc(Hons) Computer Science and Artificial Intelligence with professional placement (Year 2)
- USCM-AKB31 : BSc(Hons) Computer Science and Artificial Intelligence with study abroad (Year 2)
- USCM-AFB32 : BSc(Hons) Computer Science and Mathematics (Year 2)
- USCM-AKB32 : BSc(Hons) Computer Science and Mathematics with professional placement (Year 2)
- USCM-AKB32 : BSc(Hons) Computer Science and Mathematics with study abroad (Year 2)
- USCM-AKB30 : BSc(Hons) Computer Science with professional placement (Year 2)
- USCM-AKB30 : BSc(Hons) Computer Science with study abroad (Year 2)
- USCM-AFM30 : MComp(Hons) Computer Science (Year 2)
- USCM-AFM31 : MComp(Hons) Computer Science and Artificial Intelligence (Year 2)
- USCM-AKM31 : MComp(Hons) Computer Science and Artificial Intelligence with professional placement (Year 2)
- USCM-AKM31 : MComp(Hons) Computer Science and Artificial Intelligence with study abroad (Year 2)
- USCM-AFM32 : MComp(Hons) Computer Science and Mathematics (Year 2)
- USCM-AKM32 : MComp(Hons) Computer Science and Mathematics with professional placement (Year 2)
- USCM-AKM32 : MComp(Hons) Computer Science and Mathematics with study abroad (Year 2)
- USCM-AKM30 : MComp(Hons) Computer Science with professional placement (Year 2)
- USCM-AKM30 : MComp(Hons) Computer Science with study abroad (Year 2)
|
Notes: - This unit catalogue is applicable for the 2024/25 academic year only. Students continuing their studies into 2025/26 and beyond should not assume that this unit will be available in future years in the format displayed here for 2024/25.
- Courses and units are subject to change in accordance with normal University procedures.
- Availability of units will be subject to constraints such as staff availability, minimum and maximum group sizes, and timetabling factors as well as a student's ability to meet any pre-requisite rules.
- Find out more about these and other important University terms and conditions here.
|
