THE UNIVERSITY of EDINBURGH

DEGREE REGULATIONS & PROGRAMMES OF STUDY 2023/2024

Timetable information in the Course Catalogue may be subject to change.

University Homepage
DRPS Homepage
DRPS Search
DRPS Contact
DRPS : Course Catalogue : School of Informatics : Informatics

Undergraduate Course: Algorithmic Foundations of Data Science (INFR11156)

Course Outline
SchoolSchool of Informatics CollegeCollege of Science and Engineering
Credit level (Normal year taken)SCQF Level 11 (Year 4 Undergraduate) AvailabilityAvailable to all students
SCQF Credits10 ECTS Credits5
SummaryThe course aims to introduce algorithmic techniques that form the foundations of processing and analysing massive datasets of various forms. In particular, the course discusses how to pre-process massive datasets, efficiently store massive datasets, design fast algorithms for massive datasets, and analyse the performance of designed algorithms. Through various examples and the coursework, the students will see applications of the topics discussed in class in other areas of computer science, e.g., machine learning, and network science.
Course description The course is to discuss algorithmic techniques that form the foundations of processing and analysing massive datasets of various forms. Specific techniques covered in the course include effective representation of datasets, extracting useful information from a dataset based on algebraic tools, designing faster algorithms based on sampling and sketching techniques. Students in class will learn these techniques through intuitions, theoretical reasoning, and practical examples.

The syllabus includes:
High-dimensional spaces
Best-fit subspaces and singular value decomposition
Spectral algorithms for massive datasets
Data streaming algorithms
Clustering
Graph sparsification
Entry Requirements (not applicable to Visiting Students)
Pre-requisites It is RECOMMENDED that students have passed Algorithms and Data Structures (INFR10052)
Co-requisites
Prohibited Combinations Other requirements This course has the following mathematics prerequisites:
1 Calculus: limits, sums, integration, differentiation, recurrence relations
2 Graph theory: graphs, digraphs, trees
3 Probability: random variables, expectation, variance, Markov's inequality, Chebychev's inequality
4 Linear algebra: vectors, matrices, eigenvectors and eigenvalues, rank
5 Students should be familiar with the definition and use of big-O notation, and must be comfortable both reading and constructing mathematical proofs using various methods such as proof by induction and proof by contradiction.
Information for Visiting Students
Pre-requisitesAs above.
High Demand Course? Yes
Course Delivery Information
Not being delivered
Learning Outcomes
On completion of this course, the student will be able to:
  1. demonstrate familiarity with fundamentals for processing massive datasets.
  2. describe and compare the various algorithmic design techniques covered in the syllabus to process massive datasets
  3. apply the learned techniques to design efficient algorithms for massive datasets
  4. apply basic knowledge in linear algebra and probability theory to prove the efficiency of the designed algorithm
  5. use an appropriate software to solve certain algorithmic problems for a given dataset
Reading List
The main textbook for the course is:
Avrim Blum, John Hopcroft, and Ravindran Kannan: Foundations of Data Science.
https://www.cs.cornell.edu/jeh/book.pdf
Additional Information
Graduate Attributes and Skills As the outcome of the course, a student should be able to apply the learned mathematical knowledge to analyse and process massive datasets, and use these tools to solve algorithmic problems occurring in practice.
KeywordsMachine Learning,Computer Science,Artificial Intelligence,Theoretical Computer Science
Contacts
Course organiserDr He Sun
Tel: (0131 6)51 5622
Email: H.Sun@ed.ac.uk
Course secretaryMrs Helen Tweedale
Tel: (0131 6)50 2692
Email: Helen.Tweedale@ed.ac.uk
Navigation
Help & Information
Home
Introduction
Glossary
Search DPTs and Courses
Regulations
Regulations
Degree Programmes
Introduction
Browse DPTs
Courses
Introduction
Humanities and Social Science
Science and Engineering
Medicine and Veterinary Medicine
Other Information
Combined Course Timetable
Prospectuses
Important Information