ADVANCED ALGORITHMS - 2023/4
Module code: COM2031
Module Overview
The module introduces algorithmic techniques for various sets of problems and teaches how to analyse algorithms in terms of their complexity. The techniques build upon the data structures and algorithms module provided in level 4 (COM1029) so that students can further develop their use of methods for solving complex problems. Examples will be used throughout to demonstrate the relevance of each approach.
Module provider
Computer Science and Electronic Eng
Module Leader
BAUER Roman (CS & EE)
Number of Credits: 15
ECTS Credits: 7.5
Framework: FHEQ Level 5
Module cap (Maximum number of students): N/A
Overall student workload
Independent Learning Hours: 73
Lecture Hours: 22
Laboratory Hours: 22
Guided Learning: 11
Captured Content: 22
Module Availability
Semester 1
Prerequisites / Co-requisites
None
Module content
- Divide-and-Conquer
- Concepts of Divide-and-Conquer
- Selected problems and their solutions using Divide-and-Conquer
- Dynamic Programming
- Concepts of dynamic programming
- Selected problems and their solutions using dynamic programming
- Linear Programming
- Concepts of linear programming
- Simplex algorithm
- Selected problems and their solutions using linear programming
- Network Flow Problems
- Paths in graphs
- Max-flow/min-cut problem
- Min-cost flow problem (transportation problem)
- Algorithms for NP problems
- Reducibility and NP-completeness
- Selected NP problems and strategies for finding their solutions
- A selection of the following advanced topics:
- Number-Theoretic Algorithms, Modular arithmetic (extended GCD, mod exponentiation, mod inversion, Cyclic Groups
- Cryptographic Algorithms, Integer factorization, Discrete Logarithms, Encryption algorithms.
- Approximation Algorithms
- Randomised Algorithms
Assessment pattern
Assessment type | Unit of assessment | Weighting |
---|---|---|
Coursework | INDIVIDUAL COURSEWORK | 20 |
Examination | Invigilated Exam (2hrs) | 80 |
Alternative Assessment
N/A
Assessment Strategy
The assessment strategy is designed to provide students with the opportunity to demonstrate that they have achieved the module learning outcomes.
Thus, the summative assessment for this module consists of:
· An individual coursework on sets of problems that students are required to solve. This addresses LO1, LO2, LO3, LO4 and LO5.
· A 4h unseen open-book online examination on the whole course content. This addresses LO2, LO3, L05 and LO6.
The individual courseworks will be due around week 6. The exam takes place at the end of the semester during the exam period.
Formative assessment and feedback
Lecture slides are used extensively in the lectures with each lecture consisting of a number of slides explaining the theory and showing the examples. Solutions to lab exercises are explained during the lab session and provided to the students as part of preparation for the exam.
Module aims
- The aim of this module is to equip students with a tool box of efficient algorithmic techniques which they can apply to real-world problems. This will cover foundations, theoretical advantages and constraints of a broad range of algorithms. Mathematical algorithms and operational techniques will be presented using examples of problems allowing students to practice their application. Appropriate mathematical concepts will be introduced to support the theoretical design and evaluation of algorithms.
Learning outcomes
Attributes Developed | ||
1 | Understand the distinctive features of a broad range of algorithmic techniques that can be used to solve real-world problems | KC |
2 | Formulate problems as abstract models which can be solved by generic algorithms and mathematical methods | KC |
3 | Critically evaluate the design and efficiency of algorithms for specific types of problem | KCT |
4 | Execute and implement algorithms in a programming language. | |
5 | Apply a range of appropriate algorithms to example problems | KPT |
6 | Critically interpret the performance of an algorithm and identify improvements that can be applied to make them more efficient | KPT |
Attributes Developed
C - Cognitive/analytical
K - Subject knowledge
T - Transferable skills
P - Professional/Practical skills
Methods of Teaching / Learning
The learning and teaching strategy is designed to:
- Help students understand the distinctive features of a broad range of algorithmic techniques
- Deomonstrate the application of algorithmic techniques for solving concrete problems
- Explain students how to analyse the complexity of an algorithm, incl. its performance and how to compare different algorithms
- Equip students with necessary mathematical background to understanding certain algorithms
- Enable students to apply taught techniques to solve concrete problems
The learning and teaching methods include:
- Lectures (11 weeks at 2h) using detailed lecture slides to gauge the students’ understanding
- Labs/Tutorials (11 weeks at 2h) using exercises and their solutions and demonstrations.
Students will be expected to spend a minimum of 7 hours a week on self-study to prepare and revise lecture, lab and tutorial material.
Indicated Lecture Hours (which may also include seminars, tutorials, workshops and other contact time) are approximate and may include in-class tests where one or more of these are an assessment on the module. In-class tests are scheduled/organised separately to taught content and will be published on to student personal timetables, where they apply to taken modules, as soon as they are finalised by central administration. This will usually be after the initial publication of the teaching timetable for the relevant semester.
Reading list
https://readinglists.surrey.ac.uk
Upon accessing the reading list, please search for the module using the module code: COM2031
Other information
Digital Capabilities
This module builds on COM1029 (Data Structures and Algorithms) to introduce further classes of common algorithms and how to analyse them. These algorithms form the basis of many common computing problems their solutions provide students with different ways of thinking about and building solutions for these problems.
Employability
This module provides foundational software design and development skills that are crucial to understanding how to apply complex algorithms and reasoning about selection between different algorithms. Students are equipped with practical problem-solving skills, theoretical skills, and development skills. All of these are highly valuable to employers.
Global and Cultural Skills
Computer Science is a global language and the algorithms and analysis techniques taught in this module are used internationally. This module allows students to develop skills that will allow them to develop applications with global reach and collaborate with their peers around the world.
Resourcefulness and Resilience
The classes of algorithms taught in this module such as divide and conquer algorithms can be widely applied to a range of new and unseen problems. These new techniques provide student with different ways to reason about and form solutions to problems.
Programmes this module appears in
Programme | Semester | Classification | Qualifying conditions |
---|---|---|---|
Computer Science BSc (Hons) | 1 | Compulsory | A weighted aggregate mark of 40% is required to pass the module |
Computer Science MEng | 1 | Compulsory | A weighted aggregate mark of 40% is required to pass the module |
Please note that the information detailed within this record is accurate at the time of publishing and may be subject to change. This record contains information for the most up to date version of the programme / module for the 2023/4 academic year.