 | |
Teacher: Herman Haverkort (office: HG 7.35)
Course dates: spring 2011 (probably); in 2009/2010 the course will not be taught
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 that do not fit in main memory, the number of disk accesses
is much more important for the running time than the number of computational steps.
Even when the data fit in main memory at once, a significant part of the running time
of an algorithm that works on large amounts of data is determined by the way in which
the algorithm exploits the cache: data that is cached can be accessed much faster
than data that resides in main memory. Therefore it is important to design algorithms
for large data sets in such a way, that the data needed next is always likely to be
data recently brought into cache.In this course we study so-called I/O-efficient
algorithms: algorithms and data structures that are designed in order to keep the number
of disk accesses or cache misses as small as possible. We discuss models for the design
and analysis of such algorithms, basic algorithms, data structures and paradigms, and
applications where I/O-efficiency makes the difference between algorithms that work and
algorithms that do not work in practice.
The course will make the students familiar with the basic concepts and techniques
for the design of I/O-efficient algorithms and data structures. The students will
learn to recognize I/O-bottlenecks in algorithms, learn basic techniques to alleviate
such bottlenecks, and will get an idea of the orders of magnitude of the parameters
involved. The students will practice finding, reading, interpreting and explaining
advanced literature on the topic. Furthermore the course offers opportunities
for students to practice their presentation skills.
The course is taught in a mixed form. Some lectures are given by the teacher;
most lectures are given by the students, who collaborate in pairs
to prepare their lectures. Each pair gets assigned a particular topic and has
to give a lecture of 2 x 45 minutes. Links to basic literature for the lectures are
provided by the teacher. The students are expected to look up additional literature
when necessary.The instructors will advise the students on the preparation
of their talks. The students will meet with the instructor assigned to them at least two weeks
before the lecture for advice on its contents, and at least one week before the lecture to
discuss (the draft version of) the presentation. Each student is expected to spend about
40 hours on preparing the lecture. For some general advice on how to study the material
and on how to prepare your talk, see How to give a seminar talk. In the second half of the course, the students study possible solutions for a
real-life problem where I/O-efficiency is crucial. The students collaborate
to write short papers about these solutions.
Near the end of the course, the students review each other's papers and
present their solutions to each other.
There will be some small additional assignments throughout the course.
Registration for this course will open a few months before the start of the course.
Students coming from the TU/e computer science bachelor programme must have
completed Ontwerp van algoritmen 3 (2IA30) or Algorithms (2IL15) successfully.If you got your prior education elsewhere, we will need to check if you have the
proper prior knowledge to be able to complete the I/O-Efficient Algorithms course
successfully. We will expect that you have experience with the following topics:
incremental algorithms, divide and conquer, greedy algorithms, proofs with induction and
invariants, O-notation and recurrences, sorting, search trees, depth-first and
breadth-first search, minimum spanning trees, and shortest path algorithms.
Experience with randomized algorithms is recommended.
If you have insufficient prior experience with algorithms, you will first need
to take Algorithms (2IL15), Advanced Algorithms (2IL45), or Geometric algorithms (2IL55);
to be able to take these courses you might need Data Structures (2IL05) first.
(All of these courses are taught in English.) | |
