Introductory description

Algorithms are the fundamental building blocks of computer science – but how can we prove that an algorithm does what we want it to? How can we improve the efficiency of existing algorithms? This module will provide students with a comprehensive understanding of the fundamental principles and techniques in algorithm design and optimisation. Students will explore a wide range of topics, including sorting, searching and pathfinding algorithms, while evaluating their correctness and efficiency.

Module aims

Outline syllabus

This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.

Basic Algorithms:

• Sorting algorithms: Bubble sort, insertion sort, selection sort, quicksort, merge sort and heapsort
• Searching algorithms: Linear search, binary search, hash table lookup

Complexity Analysis:

• Big-O, big-Omega and big-Theta notation
• Time complexity analysis
• Space complexity analysis

Strategies for Algorithm Design:

• Recursive programming
• Divide and conquer
• Dynamic programming and memoisation
• Heuristics
• Any other useful paradigms

Data Structures:

• Primitive data structures: Arrays, stacks and queues
• Compound data structures: Hash tables, linked lists, binary search trees, heaps and priority queues
• Advanced data structures: Red-black trees, 2-3-4 trees, binomial trees and binomial heaps

Graph Theory:

• Graph representations
• Minimum spanning trees, Kruskal's and Prim's algorithms
• Dijkstra's and A* algorithms
• The max-flow min-cut theorem

Learning outcomes

By the end of the module, students should be able to:

• Describe the importance of various algorithms and data structures in cyber security [CITP 2.1.1, 2.1.2]
• Evaluate the correctness and efficiency of algorithms in different programming contexts [CITP 2.1.10, 2.1.11, 2.2.2]
• Appraise the behaviour of existing algorithms [CITP 2.1.11, 2.2.2]
• Implementing algorithms or modify existing ones to solve unseen problems [CITP 2.1.12, 2.2.1, 2.2.4]

Indicative reading list

Reading lists can be found in Talis

Specific reading list for the module

Subject specific skills

This module improves students' programming skills, giving them an understanding of the underlying algorithms and data structures. Students will also be able to reason about the efficiency of existing algorithms, recognising bugs in existing code as well as opportunities to improve the efficiency of algorithms.

Transferable skills

Logical reasoning, problem solving and effective communication of ideas (both written and verbal)