ADVANCED ALGORITHMS - 2017/8

Module code: COM2031

Module provider

Computer Science

Module Leader

GRUNING A Dr (Computer Sci)

Number of Credits

15

ECT Credits

7.5

Framework

FHEQ Level 5

JACs code

I100

Module cap (Maximum number of students)

N/A

Module Availability

Semester 1

Overall student workload

Independent Study Hours: 106

Lecture Hours: 24

Laboratory Hours: 22

Assessment pattern

Assessment type Unit of assessment Weighting
Coursework INDIVIDUAL COURSEWORK 40
Examination 2HR UNSEEN EXAM 60

Alternative Assessment

N/A

Prerequisites / Co-requisites

None

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 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
Understand the distinctive features of a broad range of algorithmic techniques that can be used to solve real-world problems KC
Formulate problems as abstract models which can be solved by generic algorithms and mathematical methods KC
Critically evaluate the design and efficiency of algorithms for specific types of problem KCT
Execute and implement algorithms in a programming language.
Apply a range of appropriate algorithms to example problems KPT
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

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



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.

 

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 2h unseen 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.

 

Reading list

Reading list for ADVANCED ALGORITHMS : http://aspire.surrey.ac.uk/modules/com2031

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
Software Development for Business BSc (Hons) 1 Compulsory A weighted aggregate mark of 40% is required to pass the module
Liberal Arts and Sciences BA (Hons)/BSc (Hons) 1 Optional 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 2017/8 academic year.