Advanced Data Structures and Algorithms

Overview

This course continues where the core course on Data Structures and Algorithms left off. The course introduces students to a number of highly efficient algorithms and data structures for fundamental computational problems such as primality testing, optimisation, hashing and string matching. Students are also introduced to randomised algorithms and to techniques of amortised complexity analysis. As in the core course, the style of the presentation is rigorous but high-level and informal.

Learning Outcomes

By the end of this course students should

• have knowledge and understanding of the several classical algorithms and data structures
• understand the role of randomisation and number-theoretic techniques in the design of algorithms
• be able to carry out amortised complexity analysis