The following is the list of the school courses and lecturers. There may be additional talks on topics such as Computer Science Research, Education, and Industrial Applications of Algorithms. This page will be updated as the information becomes available.
Main courses:
- Giuseppe F. Italiano (University of Rome "Tor Vergata", Italy)
Algorithms on Large Data Sets - David S. Johnson (AT&T Labs, USA)
Case Studies: The Traveling Salesman and Bin Packing Problems
- Clifford Stein (Columbia University, USA)
Combinatorial Optimization Algorithms - Robert E. Tarjan (Princeton University and HP, USA)
Data Structures - Renato F. Werneck (Microsoft Research, USA)
Shortest Paths and Experimental Evaluation of Algorithms
Prerequisites: Students should be familiar with the following material from the book Introduction to Algorithms (Second Edition) by Cormen, Leiserson, Rivest, and Stein (except “*” subsections): 1—12, 15—17, 22—24. In addition, basic programming skills (in C++) are required.
- Algorithms on Large Data Sets
Giuseppe F. Italiano (University of Rome "Tor Vergata", Italy)We present algorithms and data structures for solving efficiently problems on very large data sets (of the order of terabytes or even petabytes). We start with a discussion of why standard algorithms and data structures are not suitable for solving problems on such massive data sets. This will motivate the need to develop algorithms that fully exploit the memory hierarchies of today's computers. We discuss paradigms, algorithms, and data structures for a two-level hierarchy; these algorithms are efficient for solving problems on massive data sets. We will also discuss the concept of cache-obliviousness and the most important paradigms for designing cache-oblivious algorithms. In summary, cache-oblivious algorithms are standard internal-memory algorithms that layout their data structures and access them in a fashion that helps standard paging algorithms to perform few page transfers (between virtual memory and main memory, or between main memory and L2 cache, etc ...). This leads to a clean model to design algorithms that automatically adapt to all levels of a multi-level hierarchy.
Materials:
- Slides: Lectures 1 and 2 (ppt, pdf)
- Slides: Lectures 3 and 4 (ppt, pdf)
- Bibliography
- Case Studies: The Traveling Salesman and Bin Packing Problems
David S. Johnson (AT&T Labs, USA)The Traveling Salesman Problem (TSP) and Bin Packing have both served as key testbeds for the introduction of new algorithmic approaches and modes of analysis, particularly in the area of approximation algorithms. For both problems there are important worst- and average-case results, as well as extensive experimental analysis, which will be covered in this course. The following are some of the topics I will address.
- TSP
- Classic theoretical results and their relevance to practice
- Fast implementation of tour-construction heuristics
- Novel tour representations for local search
- Test instances and their properties
- Empirical trade-offs between running time and tour quality
- The state of the art in optimization algorithms
- Bin Packing
- Simple heuristics and asymptotic approximation schemes
- Online algorithms in theory and practice
- Implementation issues
- Average case: Theorems -> Experiments and back again
- The Sum-of-Squares Algorithm
Materials:
- TSP
- Combinatorial Optimization Algorithms
Clifford Stein (Columbia University, USA)We will present algorithms, both exact and approximate, for several fundamental problems in combinatorial optimization. We will first cover algorithms for maximum flow problems -- both augmenting path and push/relabel algorithms. We will then present an algorithm for minimum cost flow. Then, we will cover some basic techniques in approximation algorithms, using the problem of scheduling jobs so as to minimize the average completion time as an example problem.
Through studying these problems, we will emphasize many popular techniques in algorithm design, including scaling, duality, invariants, lower bounds and potential functions.
Materials:
- Data Structures
Robert E. Tarjan (Princeton University and HP, USA)Classical data structures and their recent variants:
- Binary Search Trees:
- Balanced trees, including rank-balanced trees, red-black trees, left-leaning trees.
- Maintaining balance without rebalancing on deletion.
- Self-adjusting trees.
- Heaps (priority queues):
- Implicit heaps.
- Binomial heaps.
- Rank-pairing heaps.
- Soft heaps (if time permits).
- Slides: Lectures 1 and 2 (ppt, pdf)
- Slides: Lectures 3 and 4 (ppt, pdf)
- Siddhartha Sen and Robert E. Tarjan. Deletion Without Rebalancing in Balanced Binary Trees.
- Bernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan. Rank-Balanced Trees.
- G. M. Adel'son-Vel'skii and E. M. Landis. An Algorithm for the Organization of Information.
Materials:
- Binary Search Trees:
- Shortest Paths and Experimental Evaluation of Algorithms
Renato F. Werneck (Microsoft Research, USA)We present an overview of recent algorithms for computing point-to-point shortest paths, with an emphasis on road networks. In its simplest form, the problem can be solved in essentially linear time by the well-known algorithm of Dijkstra. Unfortunately, this is too slow for continental-sized maps. Two-stage algorithms can do much better: after spending a reasonable amount of time preprocessing the network, they can answer online queries several orders of magnitude faster than Dijkstra's algorithm. We cover not only on the main algorithmic ideas of various methods, but also the engineering challenges. Seemingly minor implementation details can be the difference between practical and impractical solutions in the real world.
List of topics
- Dijkstra's algorithm
- Basic data structures
- Bellman-Ford-Moore and its variants
- A* search and landmarks
- Reach-based routing
- Contraction Hierarchies
- Transit node routing
- Arc Flags
- Extensions: the dynamic and time-dependent cases
- Highway dimension
Materials:
English
Русский
