Course: Algorithms and Complexity
Eindhoven University of Technology, Eindhoven
27 January-31 January, 2014
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, viz. quantum computing and communication complexity, evolutionary algorithms, game theory and complexity and many-core programming, 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 MMP 1 in building Multimediapaviljoen 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 hours. Short coffee breaks are planned at around 11.00 and around 14.45 and an organised lunch break at, roughly, 12.30-13.30. The slides for selected courses can be downloaded here.
| 27 January | Ronald de Wolf (CWI) |
| Quantum Computing This one-day course provides a first introduction to quantum computing. It assumes some basic familiarity with computer science, but no prior knowledge of quantum mechanics. The first part will introduce quantum mechanics and quantum bits, and will show how to do computation based on these. The second part will describe some of the main quantum algorithms, in particular Shor’s algorithm for factoring large integers into their prime factors (which breaks much commonly used cryptography) and Grover’s algorithm for search. The third part will focus on quantum communication between distributed parties, including quantum communication complexity and quantum cryptography.This course will be self-contained, but in case you want to read up before or afterwards: it will cover parts of Chapters 1, 2, 5, 6, 11, 13 of the lecture notes that can be downloaded here. |
|
| 28 January | 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. |
|
| 29 January | 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:
Programme:
|
|
| 30 January | 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. |
|
| 31 January | 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. |
Course Material
Course material will be handed out during the course. Where possible, this material will be made available for downloading via this page. Participants will receive a free copy of Wan Fokkink’s recent book on Distributed Algorithms (limited availability).
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 necessary, 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.
Registration
Registration closed on 20 January. 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. Registration closes on 20 January, 2014.
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. In the event this is not feasible, we will provide basic overnight accommodation. You can specify your accommodation needs on the registration form.