LEA
Department of Computer Science at the Technische Universität München
Chair for Efficient Algorithms
Postal address: 80290 München; Premises: Arcisstr.21, 80333 München
deutsch

Core practical: Design of Algorithms (WS 2001/2002)


Lecturer: Prof. Dr. Ernst W. Mayr
Time: Monday 14:00 (c.t.) - 16:00
Room: S0143
Office hours:: Tuesday 16:00 - 17:00, Thursday 14:00 - 15:00
Area: Computer Science III (Theory of Computer Science)
Prerequisites: Vordiplom; course Efficient Algorithms I (attended either in previous semester or in same semester as practical) obligatory, course Efficient Algorithms II recommended
Coordinator: Hanjo Täubig, Martin Raab
Registration: centralized registration at the Sun-Halle (19.-23.7.2001)
Certificate: solving all programming exercises (students work in groups of three) and passing a final oral exam

Background

Efficient algorithms are algorithms whose running times and/or space requirements are optimal or the best among all known solutions for a certain problem. Often a straightforward approach to a problem leads to exponential running times or at least to running times that are substantially worse than the optimum running time. A big field in which a number of efficient algorithms have been found over the years are graph algorithms. These will be covered in more detail in the following.

Many problems that are encountered in practice can be solved efficiently if they are modeled as graph problems. For several decades researchers in mathematics and computer science have devised algorithms for the efficient solution of typical graph problems. It has been shown that many problems can be solved by very fast algorithms even though a straightforward implementation requires exponential running-times.

Picture Matching
Maximum matching in a bipartite graph

So-called matching algorithms, for example, can be used to solve a variety of assignment problems. One such problem could be to assign lecturers to courses in a way that ensures that the maximum possible number of courses can be taught. If every lecturer teaches at most one course and every course is taught at most once, the problem is equivalent to the matching problem in a bipartite graph as depicted in the figure above. The top row of nodes represents lecturers, the bottom row represents courses. An edge between a lecturer node and a course node means that the lecturer is competent to teach the respective course. Now, a valid assignment of courses to lecturers corresponds to a matching in the graph. In the example above, at most six out of eight courses can be taught. The bold edges correspond to such an assignment. The algorithm by Hopcroft and Karp computes maximum matchings in bipartite graphs in time O(sqrt(n)*m), where n is the number of nodes and m is the number of edges of the graph.

Graph algorithms are interesting not only because of their usefulness for the solution of practical problems, but also because of the algorithmic techniques and the used data structures. Therefore, students who intend to take part in this practical course should be prepared to deal with complicated algorithms.

Contents

During this practical course students have to implement different algorithms, mainly graph algorithms, efficiently. In addition, these algorithms should be visualized on the screen . Here are some examples for graph problems to be solved:
* depth-first-search, breadth-fist-search
* connected components
* minimum spanning trees
* shortest paths
* matchings
* network flow
* vertex-coloring planar graphs
* approximating the traveling salesman problem

In addition to these graph problems, several other problems originating from different application contexts and not directly related to graphs will be covered as well. Examples are:
* string matching
* computing the edit distance of strings

Many of these algorithms are presented in the courses "Efficient Algorithms and Data Structures I/II". The content of these lectures is useful for the practical but it is also possible to aquire the knowledge in parallel to the practical. A special two-hours-per-week discussion group is part of the practical and gives explanations regarding the implementation of the algorithms.

The goal of the practical course is to help students gain a better understanding of how sophisticated algorithms, graph algorithms in particular, work and to convince them of the benefit obtained by using high-level data structures.

Organization

The students are given problem sets consisting of programming exercises which have to be solved within one or two weeks. Programs are expected to be written in C++ using LEDA (Library of Efficient Data Types and Algorithms).

LEDA is a class library supplying frequently used data structures such as stacks, queues, priority queues, lists and graphs. Using LEDA reduces substantially the programming effort necessary to implement sophisticated algorithms in C++ efficiently. In addition, the class GraphWin offered by LEDA is a flexible tool for visualization of graph algorithms.

The programming exercises can either be solved in our computer room (S2237), on the workstations in the HP-Halle (beware: compilation of LEDA programs takes quite long here!), or on any PC running Linux (the latter case requires to install LEDA first). Groups of three students solve the programming exercises together. We strongly advise the groups not to divide the work load and work on the exercises separately; instead, they should actually cooperate in solving the problems and implementing the algorithms. In the oral exam at the end of the semester, every student is expected to be knowledgable about the actual implementation of all solutions handed in by his/her group.

Students and coordinators meet once per week for a two-hour discussion group in which the coordinators present new exercises and explain the required algorithms and theoretical background. Students send their solutions by e-mail to algoprak@informatik.tu-muenchen.de or algoprak@in.tum.de. Comments on their solutions and grading information are sent to the students by e-mail by their respective supervisors as well. Problems encountered by the students can be discussed and questions can be answered either during the discussion group or with their supervisors.

Programs handed in by the students will be graded according to the following criteria:

  1. the computed solutions must be correct
  2. the implementation must be efficient, i.e., the given worst-case complexity must not be exceeded
  3. the visualization of the algorithm should be at least acceptable
  4. the source code must be comprehensible and well-structured

In order to get a course certificate, the following criteria must be satisfied:

Literature:

The following books contain descriptions of algorithms which are the topic of programming exercises in the practical:
* Cormen, Leiserson, Rivest. Introduction to Algorithms MIT Press, 1990
* Turau. Algorithmische Graphentheorie. Addison Wesley, 1996
* Gibbons. Algorithmic Graph Theory. Cambridge University Press, 1985
* Mehlhorn. Data Structures and algorithms 2: Graph algorithms and NP-Completeness, Springer-Verlag, 1984
* Papadimitriou, Steiglitz. Combinatorial Optimization: Algorithms and complexity. Prentice-Hall, 1982
* Sedgewick. Algorithms. Addison-Wesley, 1988
* Tarjan. Data Structures and Network Algorithms. SIAM, 1983
* Reingold, Nievergelt, Deo. Combinatorial Algorithms. Prentice-Hall, 1977
* Ahuja, Magnanti, Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.

Hanjo Täubig, 2001-10-22