We will explore advanced techniques for the design and the analysis of algorithms for data analysis and big data. We will focus on selected examples from classical as well as modern algorithmics. Our discussion will include both polynomial time and exponential time exact algorithms, as well as approximation algorithms for combinatorial optimization problems (often on graphs) and their analysis.

Topics will include algorithms and their analysis for graph similarity (e.g., (sub)graph isomorphism, Weisfeiler-Leman), efficient centrality computation for networks, streaming algorithms, I/O efficient algorithms, and data structures such as, e.g., Fibonacci heaps, Union-Find, and their analysis.

Prerequisites:

Note that knowledge of foundations of algorithms and data structures is essential as prerequisite. In particular, we expect you to have a solid foundation in the analysis of algorithms and data structures, including concepts such as Big-O notation and basic algorithmic analysis, as typically taught in an Introduction to Algorithms course. ou should also have programming experience—while we do not require proficiency in a specific programming language, the ability to implement algorithms and data structures is essential. Familiarity with basic computational complexity concepts is important. You should understand what it means for a problem to be NP-hard or solvable in polynomial time, and be comfortable working with such classifications. We assume you are acquainted with fundamental data structures and algorithms, including binary heaps, priority queues, and others. You should be able to analyze them (in terms of correctness and worst-case running time) and apply them efficiently. As many of the techniques involve graphs, you should know standard graph algorithms and operations, such as Breadth-First Search (BFS), Depth-First Search (DFS), and shortest path algorithms like Dijkstra’s algorithm. All of this knowledge is typically covered in an introductory algorithms course. Additionally, a basic understanding of mathematics is necessary, including proof techniques such as induction, as well as familiarity with vectors and matrices.

The lectures are accompanied by tutorials conducted by Philip Mayer and Lukas Schürmann. There are two alternative appointments. You only need to attend one of the appointments.

The assignment of the attendees is done via TVS. Registration time: 9 Oct (after the lecture) - 13 Oct (11:59 p.m.). You will need a password for the registration which will be announced in the lecture and on eCampus when the registration period starts.

You need to actively participate in the exercises as a prerequisite for getting admission for the exams (the offical admission requirements can be found in the Module Handbook and on eCampus). The exams have been oral in WiSe 2024/25. We plan to have written exams in WiSe 2025/26.