Advanced Algorithms and Data Structures
| Code | School | Level | Credits | Semesters |
| COMP4019 | Computer Science | 4 | 10 | Autumn UK |
- Code
- COMP4019
- School
- Computer Science
- Level
- 4
- Credits
- 10
- Semesters
- Autumn UK
Summary
We study data structures, efficient algorithms on them and ways to determine their complexity. We also study some modern algorithms that are widely used in contemporary software. The topics covered may include Binary Search Trees (Red-Black Trees), Dynamic Programming, Graph Algorithms (e.g. shortest path, maximum flows), Amortized Analysis, Priority Queues (Binary, Leftist and Fibonacci Heaps) and String Algorithms (string matching, longest common subsequence). Among the special topics relevant to contemporary application, we may study Public Key Cryptography (the RSA cryptosystem), the Page-rank algorithm (from Google search), Neural Networks and other data structures and algorithms in AI. The theory is practiced in weekly labs where we learn how to implement the algorithms and data structures as functional and imperative programs.
Target Students
Available to Level 3 and Level 4 students in the School of Computer Science. This module is not available to students not listed above without explicit approval from the module convenor(s). Prior knowledge of mathematics and computer programming including standard data science is required. This module is part of the Foundations of Computer Science theme in the School of Computer Science.
Classes
Activities may take place every teaching week of the Semester or only in specified weeks. It is usually specified above if an activity only takes place in some weeks of a Semester.
Assessment
- 25% Coursework 1: Continuous assessment, including written homework exercises. Possibly with some under invigilated in-class test conditions. Reassessment is 100% examination.
- 75% Exam 1 (2-hour): 2-hr written examination. Reassessment is 100% examination. Reassessment is 100% examination.
Assessed by end of autumn semester
Educational Aims
To obtain advanced knowledge and practical skills in the analysis, design and implementation of advanced algorithms and data structures.Learning Outcomes
Knowledge and Understanding
- Mathematical modelling and analysis of the efficiency of algorithms.
- Advanced implementation techniques.
Intellectual Skills
- The application of mathematical techniques to algorithms and data structures.
- The identification and evaluation of appropriate models of efficiency.
Professional Skills
- The use and selection of appropriate software libraries.
Transferable Skills
- The ability to formulate and construct effective solutions to algorithmic problems.