Summary 
Algorithms and algorithmic problem solving are at the heart of computer science. This module introduces students to the design and analysis of efficient algorithms and data structures. Students learn how to quantify the efficiency of an algorithm and what algorithmic solutions are efficient. Techniques for designing efficient algorithms are taught, including efficient data structures for storing and retrieving data. This is done using illustrative and fundamental problems: searching, sorting, graph algorithms, and combinatorial problems such as finding shortest paths in networks. 
Session 
Spring 2021/22 
Credits 
10 
Assessment 
 Blackboard quiz (threshold)
 Formal examination (grading)

Lecturer(s) 
Dr Pietro Oliveto & Dr Sagnik Mukhopadhyay 
Resources 

Aims 
The module aims to:
 Introduce students to algorithmic thinking and equip them with techniques for solving computational problems algorithmically
 Demonstrate the need for efficient algorithms, i.e. algorithms whose computation time scales well with the input size
 Enable students to analyse the efficiency of an algorithm, hence distinguishing efficient from inefficient solutions
 Explain basic data structures, their efficiency in performing elementary operations for storing and retrieving data, and how they can be used in the design of efficient algorithms
 Teach generalpurpose algorithmic design principles, including greedy algorithms, divide and conquer, and dynamic programming
 Cover algorithmic solutions to classical and illustrative computational problems such as sorting and finding shortest paths in networks, with a focus on their design and computational complexity.

Objectives 
At the end of the course students will be able to
 Appreciate what constitutes an efficient and an inefficient solution to a computational problem;
 Analyse the efficiency of an algorithm;
 Evaluate and choose data structures that support efficient algorithmic solutions;
 Identify and apply design principles such as greediness, divide and conquer and dynamic programming in the design of efficient algorithms;
 Describe efficient algorithms for fundamental computational problems, along with their computational complexity.

Content 
Planned topics (subject to change) include:
 Algorithms as a technology
 Efficiency of Algorithms
 Design and Analysis of Algorithms for Sorting
 Insertion sort
 Heap sort
 Mergesort
 Quicksort
 Linear time sorting
 Data Structures
 Stacks and Queues
 Linked lists
 Binary search trees
 Balanced trees
 Graphs
 Design and Analysis of Graph Algorithms
 Searching in graphs
 Finding shortest paths in graphs
 Combinatorial graph problems
 Algorithmic Design Paradigms
 Greedy algorithms
 Divide and conquer
 Dynamic programming

Essential skills 
ALevel Maths 
Teaching Method 
The theoretical background and techniques will be presented in a series of lectures. Students will reinforce the material through selfstudy, and through weekly problems classes. 
Feedback 
Students will receive continuous feedback e.g. on their marked assignments, during tutorial sessions and during lectures. 
Recommended Reading 
T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein (2009) Introduction to Algorithms, third edition (MIT Press) http://mitpress.mit.edu/books/introductionalgorithms
http://www.amazon.co.uk/IntroductionAlgorithmsTCormen/dp/0262533057 