Lectures Efficient Algorithms and
Data Structures II Computational Biology I External Memory Algorithms Pearls of Computer Science IV Python for Fine Programmers Proseminar Algorithms for daily life Lab Course Discrete Optimization Courses for PhD Students Oberseminar

Pearls of Computer Science IV

• Lecturers:
  Dr. Thomas Fuhrmann
  Dr. Riko Jacob
  Dr. Martin Sachenbacher
  Dr. Alexandros Stamatakis
  Dr. Christian Urban
• Module:
  IN2177
• Area:
  1 lecture of 2 hours per week
• Time and Place:
  Thu, 12:25-13:55.
  Wed, 10:15-11:45.
  Room 03.11.18
• Audience:
  Motivated 4th semester students of computer science with good results in the 1st year courses
• Prerequisites:
  1st year courses
• Recommended for:
  Participants of the Special program for gifted students of the computer science department
• Contents:
  Dr. Christian Urban "Correctness of Programming Languages"
  Programming languages are the means by which every software product is created. In the lectures we will cover latest research results about verifying that programming languages are correct. We will emphasize on formal techniques to study a variety of programming language paradigms, including functional and imperative. Time permitting, we will have a look at mapreduce algorithms, which are inspired by functional programming.
  Slides:
  23 Apr 09
  30 Apr 09
  7 May 09
  Dr. Thomas Fuhrmann "Design principles of the Internet"
  The Internet is the largest machine humankind has ever built. No one can control it, and no one fully understands it. This lecture gives a brief introduction into the design principles that shaped the Internet architecture from its beginning in the 1970s until today. In particular we consider examples for the scalable, self-organizing algorithms that shall sustain the Internet's growth also in the future.
  Dr. Riko Jacob "Memory Hierarchy Optimal Matrix Multiplication-Programs"
  The I/O model judges the quality of an algorithm for huge data sets not by the number of CPU-operations but by the number of page misses it incurs. In this setting many traditionally trivial tasks start to require real algorithms, for example to permute the elements of an array, or more generally and stated in the linear algebra way, to multiply a vector with a sparse matrix (SpMxV). SpMxV is also a fundamental task applications, for example in numerical solvers or in network analysis tasks like computing Googles page rank. By now the worst case complexity of SpMxV on a serial computer is reasonably well understood. In the project these insights are generalized to parallel computers, the structure of concrete matrices is investigated, and the found algorithms are considered from an algorithms engineering point of view.
  Alternatively, we could discuss some seemingly unrelated results, one on Shunting Freight Trains and the other on finding the predecessor in a sorted matrix (details of the problems will be explained). Here the focus would be on the uniting toolbox and why I think of these results as beautiful.
  Dr. Martin Sachenbacher "Constraint programming and its role in self-aware, autonomous systems"
  Constraint programming (CP) has been called "one of the closest approaches computer science has yet made to the holy grail of programming": in CP, the user states the conditions which restrict his freedom of decision, and a general purpose solver is used to find solutions. After a short introduction to basic constraint modeling and solution techniques, we present recent research directions, which aim at modeling user preferences and multi-agent scenarios where not all decision variables are under the user's control. We discuss how CP methods are instrumental to build technical systems (autonomous space probes, intelligent factories, smart buildings, etc.) that are able to work properly without or with very limited human intervention, even in the case of unexpected events and failures.
  Dr. Alexandros Stamatakis "Reconstructing Evolution"
  This year we are celebrating Darwin's 200th birthday. Therefore, a part of the lectures will be dedicated to the reconstruction of phylogenetic (evolutionary) trees from DNA sequences. This area of research spans a broad range of interesting problems such as statistical modeling of evolution, heuristics for NP-hard optimization problems, discrete algorithmic problems on sets of bipartitions of trees, and application of High Performance Computing Techniques. After a brief general introduction to the field, a couple of current research highlights will be discussed in more detail, e.g., the currently fastest and most accurate heuristic search algorithm for reconstruction of evolutionary histories and a parallel implementation on the IBM BlueGene/L supercomputer.