Course: Algorithms and Complexity

Eindhoven University of Technology, Eindhoven
4 July-8 July, 2016

IPA organises Advanced Courses on each of its major research fields: Algorithmics and Complexity, Formal Methods and Software Engineering and Technology. Each of these Advanced Courses intends to give an overview of (part of) the research of IPA in this specific field.

The Advanced Course, which is hosted by IPA at the Eindhoven University of Technology, focusses on subject areas in algorithmics and complexity where successful research is being conducted by groups in IPA. From several of these areas, e.g. evolutionary algorithms, game theory and distributed algorithms, topics are taken to which an entire course day is dedicated. Course days consist of lectures mixed with active training (exercises, assignments, etc.).

Dates, Location and Programme

The lectures will take place in room MF 06 in building Metaforum of the TU/e. The overall schedule of the course is as follows: course days will start at 10.00 and last until approximately 16.30/17.00 hours. Short coffee breaks are planned at around 11.00 and around 14.45 and an organised (warm) lunch break at, roughly, 12.30-14.00.

Lectures will be given by Herman Haverkort (TU/e), Hans Bodlaender (UU and TU/e), Peter Bosman (CWI), Hendrik Jan Hoogeboom (UL), Walter Kosters (UL) and Wan Fokkink (VUA and TU/e). See below for a tentative programme.

Course Material

Where possible, slides and additional material have been made available for downloading via this linkParticipants received a free copy of Wan Fokkink’s recent book on Distributed Algorithms (limited availability).

Registration

Registration closed on 20 June. To make the course count as one of the required elements in the “Opleidings- en Begeleidingsplan” of an IPA Ph.D student, at least 80 percent of the course days must be attended. If you require overnight accommodation in Eindhoven for one or more nights during the course, please specify this in the “Remarks” box of the form.

Accommodation

Unlike Spring Days and Fall Days, overnight accommodation is not included by default for this course. The schedule is set up in such a way that it is feasible for many students to commute, but in case an overnight accommodation is desired we will provide one (regardless of commute distance). You can specify your accommodation needs on the registration form.

Schedule

4 July Herman Haverkort (TU/e)
I/O efficiency
Traditionally, the running time of an algorithm is analysed in terms of the number of computational steps it performs (comparisons, additions, etc.). However, when working with huge amounts of data, this does not suffice. To be practical, algorithms for massive data must be structured such that they make good use of caches to minimize expensive access (“I/O”) to main memory and disks.In this course we study I/O-efficient algorithms and algorithms that use very little (writable) memory. We will learn about applications where I/O-efficiency makes the difference between algorithms that work and algorithms that do not work in practice. We will learn about models for the design and analysis of such algorithms, we will learn about basic techniques, results and challenges, and we will study a traditional algorithm, discover its I/O-bottlenecks and see to what extent (and how) we can alleviate those bottlenecks.
5 July Hans Bodlaender (UU)
Parameterized Complexity
This lecture is organized as follows:

  • Part 1: Introduction to parameterized algorithms and complexity
    The notion of fixed parameter tractable algorithms is introduced, and different techniques to obtain fpt algorithms and method to show that there are, under complexity theoretic assumptions, no fpt algorithms for a problem are discussed.
  • Part 2: Kernelization
    The notion of kernelization, with its relations to preprocessing and fpt algorithms is introduced. A few examples of kernelization algorithms are discussed, and techniques to show lower bounds for the size of kernels
  • Part 3: Advanced fpt techniques
    In this last hour, we look at some more advanced techniques to obtain fpt algorithms; in particular, we discuss the method of color coding, and algorithms for graphs of small treewidth or a related width notion

6 July Peter Bosman (CWI)
Evolutionary Algorithms
Evolutionary algorithms are search algorithms that are based on the mechanism of natural selection (“survival of the fittest”). A collection, called the population, of solutions is maintained. From this population the best solutions are selected and used to construct new solutions, called offspring, with. This construction of new solutions is (classically) performed using operators that have been developed according to analogy with genetic operators such as crossover and mutation.Evolutionary algorithms are used for solving combinatoric and numeric optimization problems as well as to aid in the construction of adaptive systems. On this day a general framework for evolutionary algorithms will be presented and classical and stereotypic algorithms will be primarily discussed. Also a few applications will be presented and main topics and areas of research will be indicated. The (computer) exercises are meant to get some hands-on experience and to get a better idea of how evolutionary algorithms work. To this end we will use the EA Visualizer software.
7 July Wan Fokkink (VUA and TU/e)
Distributed Algorithms
A wide range of distributed algorithms are explained by informal descriptions, illuminating examples and exercises. Topics include snapshots, termination detection, crash consensus, mutual exclusion, and self-stabilization.
8 July Hendrik Jan Hoogeboom (UL) and Walter Kosters (UL)
Game Complexity
Games come in many flavours. They can be easy, they can be hard: though the rules of Go are simple, the game is very complex. But how hard is such a game from the viewpoint of computational complexity theory? Can we generalize to arbitrary board sizes? Is it NP-hard? Is it in PSPACE? And what are corresponding decision problems anyhow?
Bob Hearn and Erik Demaine have written a book that tries to provide a uniform view on game complexity. They start from special types of graphs, building so-called Contraint Logic, for which several variants are closely tied to specific complexity classes. A typical decision problem, or winning condition, might be the question whether a given edge in the graph can be finally reversed by a series of edge reversals, where an edge reversal is allowed in game-specific circumstances. Hearn and Demaine translate this logic into different games, ranging from zero-player games like Conway’s Life, via puzzles (being one-player games) such as Sokoban and Rush Hour (with sliding blocks), to two-player games like Amazons. And how about team games? Crucial is the construction of so-called gadgets. For each game, simulation of and- and or-gates within the specific game rules is the basis of the translation, usually referred to as reduction. The lectures are essentially self-contained, and include assignments that deal with puzzles and reductions. See the web for the so-called plank puzzle.Reference:

  • R.A. Hearn and E.D. Demaine, Games, Puzzles & Computation, AK Peters, 2009.

Programme:

  1. Intro: Games and complexity classes, constraint logic
  2. Gadgets, planarity, exercises
  3. Tip-Over is NP-complete
  4. Rush Hour is PSPACE complete, plank puzzle
  5. Wrap-up: other classes of games

Costs

The courses are intended for IPA PhD students, giving them an overview of IPA’s research. For IPA PhD students, participation is free of charge (including overnight accommodation if desired, see below), but registration is required. Other IPA-members can attend if there is capacity left, and the same holds for members of associated research schools. For these categories we will charge costs for the course material, lunches, etc, and IPA will not provide overnight accommodation. Contact us for information regarding pricing. For all categories, in case of no show extra charges may apply.