Course: Algorithms and Complexity
Eindhoven University of Technology, Eindhoven
4 July8 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.3014.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 link. Participants 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/Oefficient algorithms and algorithms that use very little (writable) memory. We will learn about applications where I/Oefficiency 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/Obottlenecks 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:


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 handson 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 selfstabilization. 

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 NPhard? 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 socalled 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 gamespecific circumstances. Hearn and Demaine translate this logic into different games, ranging from zeroplayer games like Conway’s Life, via puzzles (being oneplayer games) such as Sokoban and Rush Hour (with sliding blocks), to twoplayer games like Amazons. And how about team games? Crucial is the construction of socalled gadgets. For each game, simulation of and and orgates within the specific game rules is the basis of the translation, usually referred to as reduction. The lectures are essentially selfcontained, and include assignments that deal with puzzles and reductions. See the web for the socalled plank puzzle.Reference:
Programme:

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 IPAmembers 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.