Advanced Algorithms and Data Structures for Data Science¶
MSc studies in Data Science, Faculty of Mathematics and Information Science, Warsaw University of Technology
This course covers methods for data analysis and mining, statistics, machine learning, and artificial intelligence from an algorithmic perspective. We will introduce, analyse, and implement key algorithms and data structures used for finding similar groups of objects, building decision trees, learning parameters of artificial neural networks, processing time series, and many more. We will focus not only on implementing re-usable algorithms from scratch (acquiring programming skills needed to implement any algorithm when a ready-to-use implementation of a method is unavailable, its high-level R/Python prototype is too slow to run, or a customised modification thereof is required), but also calling methods from existing libraries (standing on the shoulders of giants, appreciating the effort of the open-source community). As a by-product, we will better understand the implementation of statistical software packages (R, Python with numpy and pandas, etc.).
Prerequisites: Structured Data Processing (R and Python), Data Structures and Algorithms (sorting and searching), Numerical Methods, Introduction to Machine Learning
Schedule¶
Winter semester 2024/2025:
Lectures: Wednesdays, 16:15–18:00, 103 MiNI (classical, blackboard-based lectures; students are expected to participate actively in the classes, take notes, discuss/brainstorm all ideas, and overall happily relish the food for thought carefully prepared by yours truly)
Pracs: Thursdays, 10:15–12:00, 219 MiNI (practical implementation, testing, and application of the algorithms presented in the lectures or described in the literature; discussion of the obtained results)
Lecture |
Pracs |
|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
— |
|
|
|
|
|
|
|
|
|
|
— |
|
— |
|
|
|
|
|
|
— |
General Topics Covered¶
The list (and the order of items) is provisional.
Introduction to the C programming language. Calling C from R and Python.
Working with arrays in C. Dynamic memory allocation. Sorting algorithms and hash tables refresher. File I/O. Processing (large) data streams. Pseudorandom number generation and Monte Carlo methods
Dense and sparse representations of matrices. Calling functions from shared libraries: GNU GSL, LAPACK, BLAS, etc. Applications of the QR and SVD decompositions in data analysis.
Minimum spanning trees, disjoint-sets data structures, implementing agglomerative hierarchical clustering algorithms.
Implementing linked data structures in C (linked lists, binary search trees, B-trees, etc.). Decision trees (ID3, CART, boosting, bagging, random forests).
Exact and approximate near-neighbour/spatial search (kd-, vp-trees, LSH) with applications in k-nn classification and regression and DBSCAN clustering.
One (NP-hard) objective function and many heuristic solvers: the within-cluster sum of squares and many variants of the K-means, Ward linkage, hill climbing, tabu search, evolutionary algorithms etc.
Logistic regression and other feed-forward artificial neural networks: parameter learning via gradient descent and other optimisers, back-propagation, automatic differentiation (autograd).
Fourier transforms of time series with FFT.
Assessment Methods and Regulations¶
There are two written (Ă 20 and 30 pts) and four programming assignments (Ă 10, 10, 15, and 15 pts max, respectively).
During the written assignments, electronic devices must not be used. However, a single A4-sized sheet of hand-written notes can be brought along.
The programming assignments will be solved on the laboratory (Linux; not: own) devices. Only an explicitly specified list of online resources (e.g., official documentation of some APIs) can be accessed. In particular, the use of Gen-AI-based services (ChatGPT etc.) is strictly forbidden. The failure to comply with these rules is a breach of academic integrity (cheating) and results in a fail mark.
Class attendance is compulsory. Five pts will be deducted from the final result for each unexcused absence.
The final grade will reflect the extent to which your written and programming assessment tasks meet the specified quality criteria. The total result of ≤50 pts translates to the 2.0 grade; (50,60] – 3.0; (60,70] – 3.5; (70,80] – 4.0; (80,90] – 4,5; and >90 – 5.0.
References¶
The list is non-exhaustive. More references will be provided in the lectures.
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, MIT Press and McGraw-Hill, 2022
W.H. Press, S.A. Teukolsky, W.T. Vetterling, B.P. Flannery, Numerical Recipes. The Art of Scientific Computing, 3rd ed., Cambridge University Press, 2007
S. Marsland, Machine Learning: An Algorithmic Perspective, Chapman&Hall/CRC, 2015
M. Gagolewski, Deep R Programming, 2024 (Chapter 14)
D. Goldberg, What every computer scientist should know about floating-point arithmetic, ACM Computing Surveys 21(1), 1991, 5–48
N.J. Higham, Accuracy and Stability of Numerical Algorithms, SIAM, 2002
(*) D.E. Knuth, The Art of Computer Programming, Vols. 1–4B, Addison-Wesley, 2023
T. Rothwell, J. Youngman, and others, The GNU C Reference Manual (skip the parts devoted to the “GNU extensions”)
The GNU C Language Manual (skip the parts devoted to the “GNU extensions”)
J. Gustedt, Modern C, Manning, 2019
(*) B.W. Kernighan, D.M. Ritchie, The C Programming Language, Prentice Hall, 1988
(*) Programming Languages – C. International Standard ISO/IEC 9899:2023, draft
Source code of:
Software¶
Programming languages: C, C++ (gcc/clang), R, Python (CPython, Cython), Fortran
A GNU/Linux operating system with root access