Aims -  This module aims to provide a more theoretical basis for understanding algorithms while being strongly motivated by practical applications. It introduces classical algorithms while exposing the student to the logic of algorithmic design, data structures and computational complexity. It is primarily intended for second and third year students registered on the undergraduate degree programmes offered by the Department of Statistical Science, or jointly with other departments. The academic prerequisite for such students is STAT0040.

Objectives - On successful completion of the module, a student should have: an ability to compare algorithms in terms of computational cost; a working knowledge of several algorithms for common tasks such as sorting and search that illustrate core concepts of algorithmic design; a working knowledge of several data structures such as lists and hash tables and where they are appropriate in their own algorithms for solving data science tasks; a conceptual understanding of numerical stability properties of algorithms from examples of particular numerical problems; an ability to code from first principles several of the methods discussed in Python.

Applications - In many real-world scenarios, a data scientist cannot rely on purely off-the-shelf solutions for solving complex analytical questions that require a computational approach. Being able to independently create variations of algorithmic pipelines for a particular task at hand requires deeper knowledge than mere competence in the use of pre-defined software packages. This module will give students a powerful way of using and developing different strategies for representing and manipulating information, as typically required by more advanced data analytical solutions in a wide variety of application areas.

Content - Notions of computational complexity. Divide-and-conquer principles. Sorting and notions of randomised algorithms. Basic data structures: lists, stacks, trees, graphs, hash tables. Search algorithms, dynamic programming and combinatorial problems. Numerical algorithms and their stability, notions of numerical analysis.

Key texts - Available from ReadingLists@UCL.