IPA organises Basic Courses on each of its major research fields, Algorithmics and Complexity, Formal Methods and Software Technology. Each of these Basic Courses intends to give an overview of (part of) the research of IPA in this specific field.
The Basic Course, which is hosted by IPA at the Technische Universiteit Eindhoven focusses on four subjects areas in algorithmics where succesfull research is being conducted by groups in IPA. From each of these areas, operations research, graph and network algorithms, natural computation, and alternative computational models, a topic is taken to which an entire course day is dedicated. The final course day will addres an interesting application area for algorithmic techniques, in this case bio informatics. Course days consist of lectures mixed with active training (exercises,assignments, etc.), more information on the course program will become available through this page.
The overall schedule of the course is as follows, course days will last from approximately 10.00 to 17.00 hours.
A more precise time table will be made available as soon as possible. Unlike the Herfstdagen and Lentedagen, overnight accomodation is not "built in" for this course. The schedule is set up in such a way that it is feasible for many students to travel back and forth to Eindhoven during the week. In cases where this is not feasible, we will provide basic overnight accomodation. You can specify your accomodation needs on the registration form.
The venue for the course is the main building ("hoofdgebouw") of the Technische Universiteit Eindhoven, marked "HG" on the campus map. The TU/e campus is only a few minutes walk from Eindhoven Central Station. After arriving at the station, take the stairs down from the platform and turn to your right. Exit the station on the north side (buss station) to the main road. Enter the diagonal walk way to your right. At the end you will come to a crossing with a main road, guarded by traffic lights. The entrance to the campus is across the main road. Follow this footpath along the circular building till the end. You are now on a square with the main building in front of you and a green glass building to your right. Enter the main building through the main (south side) entrance, and take the elevator to the 6th floor, the first room to your left when you leave the elevator is room HG 6.01 (a.k.a. "winzaal").
Course material will be handed out during the course. Where possible, this material will be made available for downloading via this page.
The courses are directed towards IPA PhD. students, giving them an overview of IPA's research. For them participation is free (including overnight accommodation if necessary). Other IPA-members can attend if there is capacity left, and the holds for members of associated research schools. For these categories we will charge costs for the course material, lunches, etc (and we will not provide overnight accomodation). Costs for these participants will be specified here as soon as possible.
Registration closed on Friday June 15, 2007.
Scheduling theory has been developed to solve problems occurring in for instance production facilities. The basic scheduling problem can be described as finding for each of the tasks, which are also called jobs, an execution interval on one of the machines that are able to execute it, such that all side-constraints are met; obviously, this should be done in such a way that the resulting solution, which is called a schedule, is best possible, that is, it minimizes the given objective function.
In this course day, I will give an overview of three different areas in scheduling:
10.00 - 11.00: Introduction + single machine scheduling
11.00 - 11.15: Break
11.15 - 12.00: Exercises
12.00 - 12.15: Discussion of exercises
12.15 - 13.30: Lunch
13.30 - 14.15: Job shop scheduling
14.15 - 14.30: Break
14.30 - 15.15: Exercises + discussion
15.15 - 15.30: Break
15.30 - 16.30: Parallel machines: column generation
10.00 - 11.00 Lecture 1: Introduction to parameterized complexity FPT - algorithms I: branching and kernelization
11.15 - 12.00 Exercises 1
12.00 - 12.15 Discussion of exercises
12.15 - 13.30 Lunch
13.30 - 14.30 Lecture 2: Hardness proofs and FPT techniques
14.30 - 14.45 Break
14.45 - 15.30 Exercises 2
15.30 - 15.45 Discussion of exercises
15.45 - 16.15 Lecture 3: Advanced FPT techniques
Randomization is a powerful tool to obtain efficient algorithms that are often simpler than their deterministic counterparts. In this module we will study the use of randomized algorithms in computational geometry. We will give a general framework to design and analyze randomized (geometric) algorithms, and we will give several of applications of this technique.
10.00 - 11.00: Lecture 1: Short introduction to computational geometry in general.
11.00 - 11.15: Break
11.15 - 12.00: Exercises 1
12.00 - 12.15: Discussion of exercises
12.15 - 13.30: Lunch
13.30 - 14.30: Lecture 2: A framework for randomized incremental construction.
14.30 - 14.45: Break
14.45 - 15.45: Exercises 2
15.45 - 16.00: Discussion of exercises
16.00 - 16.30: Wrap-up session: Mini-overview.
Literature:
M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications (2nd edition). Springer-Verlag, 2000. Several chapters from this book will be distributed as hand-outs during the course.
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) excercises 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.
10.00 - 11.00: Introduction and the simple Genetic Algorithm
11.00 - 11.15: Break
11.15 - 12.00: Exercises 1
12.00 - 12.15: Discussion of exercises 1
12.15 - 13.30: Lunch
13.30 - 14.15: Different types of evolutionary algorithm and their applications
14.15 - 15.00: Exercises 2
15.00 - 15.15: Discussion of excercises 2
15.15 - 15.45: Evolutionary simulations
15.45 - 16.00: Break
16.00 - 16.30: Overview of the main research topics in the field
Molecular biology offers many algorithmic challenges. Most problems arise from DNA research. For instance, given many small fragments of DNA obtained by destroying a large string, the target is to reconstruct this original sequence (fragment assembly). The problem directly translates into the NP-hard Shortest Common Superstring problem. However, practical issues as occurrance of errors in biological data introduce further difficulties.
Sequence comparison, probably the most basic technique in the research area, tries to answer the question how alike two given strings of DNA are. Again, there are many (practical) variants worth mentioning, for instance dealing with insertions and deletions.
During the course we will discuss several topics from computational molecular biology; in particular we treat sequence comparison and fragment assembly. The focus is on the algoritmic aspects; a very brief introduction to the necessary topics from biology is provided.
10.00-11.00: Introduction: Basics of biology; Sequence alignment
11.00-11.15: Break
11.15-12.15: Exercises I
12.15-13.30: Lunch
13.30-14.30: Fragment assembly
14.30-14.45: Break
14.45-15.45: Exercises II
15.45-16.00: Wrap-up