Algorithms and Data Structures (STAT0041)

This module aims to provide a more theoretical basis for understanding algorithms while being strongly motivated by practical applications, introducing classical algorithms and exposing students 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 (including the MASS programmes). For these students, the academic prerequisites for this module are met through compulsory study earlier in their programme.

Intended Learning Outcomes

• be able to compare algorithms in terms of computational cost;
• possess a working knowledge of several algorithms for common tasks such as sorting and search that illustrate core concepts of algorithmic design;
• possess 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;
• have a conceptual understanding of numerical stability properties of algorithms from examples of particular numerical problems;
• be able to code from first principles several of the methods discussed.

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.

Indicative 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.