Algorithms, Correctness and Efficiency - COMP5180

Looking for a different module?

Module delivery information

Location Term Level1 Credits (ECTS)2 Current Convenor3 2022 to 2023
Canterbury
Autumn Term 5 15 (7.5) Sanjay Bhattacherjee checkmark-circle

Overview

The curriculum covers topics in algorithms and data structures. Among data structures, it covers advanced topics on trees, heaps, graphs, et cetera. It provides details of computational complexity notations like O(). It covers the correctness and runtime analysis of recursive algorithms using recurrences. These algorithms range from mathematical computations to sorting algorithms. These algorithms are put in the context of appropriate algorithmic paradigms like divide-and-conquer and dynamic programming. Finally, computational complexity classes and problem reductions are introduced along with the proof techniques for NP-hardness and NP-completeness.

Details

Contact hours

Total contact hours: 32
Private study hours: 118
Total study hours: 150

Method of assessment

Main assessment methods
2 programming assessments (15 hours each) (25% each)
2 hour unseen written examination (50%)

Reassessment methods
Like for like.

Indicative reading

Algorithms. Sedgewick and Wayne
Algorithms. Jeff Erickson
Introduction to Algorithms. Cormen, Leiserson, Rivest, and Stein
The Art of Computer Programming. Donald E. Knuth
The Algorithm Design Manual. Steven S. Skiena
Data Structures and Algorithms in Java 2nd Edition. M.T. Goodrich and R. Tamassia
Algorithms and Data Structures 2nd Edition. Jeffrey H. Kingston x
Cracking the Coding Interview. Gayle Laakmann McDowell

See the library reading list for this module (Canterbury)

Learning outcomes

On successfully completing the module students will be able to:
1. specify, test, and verify implementations of algorithms;
2. analyse the time and space behaviour of algorithms;
3. analyse and compare general algorithmic paradigms;
4. make informed decisions while choosing data structures and algorithms for practical use;
5. demonstrate an understanding of algorithmic reduction, complexity classes and hardness.

Notes

  1. Credit level 5. Intermediate level module usually taken in Stage 2 of an undergraduate degree.
  2. ECTS credits are recognised throughout the EU and allow you to transfer credit easily from one university to another.
  3. The named convenor is the convenor for the current academic session.
Back to top

University of Kent makes every effort to ensure that module information is accurate for the relevant academic session and to provide educational services as described. However, courses, services and other matters may be subject to change. Please read our full disclaimer.