Department of Computer Science

## COM1009 Introduction to Algorithms and Data Structures

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. Spring 2021/22 10 Blackboard quiz (threshold) Formal examination (grading) Dr Pietro Oliveto & Dr Sagnik Mukhopadhyay 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 general-purpose 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. 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. 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 A-Level Maths The theoretical background and techniques will be presented in a series of lectures. Students will reinforce the material through self-study, and through weekly problems classes. Students will receive continuous feedback e.g. on their marked assignments, during tutorial sessions and during lectures. 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/introduction-algorithms http://www.amazon.co.uk/Introduction-Algorithms-T-Cormen/dp/0262533057