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

Efficient Algorithms and Data Structures (WS 99/00)


* Lecturer:
Prof. Dr. Sami Khuri

* Area:
4+2 lectures per week in area III (Theoretical Computer Science)
core course , topic algorithms

* Time and Place:
Tue 10:05 - 11:35, lecture hall 1100
Thu 10h c.t. - 12:00, lecture hall 1100

* Exam:
written exam on February 22, 3:00pm to 5:00pm, room S2229
time allowed: 120 minutes
Language: questions are in English, answers can be in German or in English
You can bring one sheet of paper (A4) with arbitrary contents and a normal calculator (not programmable), nothing else!

* Exercises:
2 hours per week exercises accompanying the lectures
Wed 12:30 - 14:00, lecture hall N1095
Teaching Assistant: Thomas Erlebach
Course Certificate: To get a course certificate students must get at least 40% on the homework assignments and pass the final exam.

* Audience:
graduate students of computer science
students with computer science as minor

* Prerequisites:
1st and 2nd year courses
The lecture will be taught in English.

* Recommended for:
Fundamental knowledge in topic Algorithms

* Contents:
This lecture will deal with the following topics:
  1. Introduction
  2. Advanced Datastructures
  3. Selection
  4. Minimum Spanning Trees
  5. Shortest Paths
  6. Graph Connectivity
  7. Planar Graphs

* Related and Advanced Lectures:
Efficient Algorithms and Data Structures II

* Lecture Notes:
Lecture notes are typed by Christian Osendorfer during the semester and are available here.

Lecture notes of previous semesters can be found here.

* References:
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman:
The design and analysis of computer algorithms
Addison-Wesley Publishing Company, Reading MA, 1976
Donald E. Knuth:
The art of computer programming Vol. 3 : Sorting and searching
Addison-Wesley Publishing Company, Reading MA, 1973
Kurt Mehlhorn:
Data structures and algorithms 1 : Sorting and searching
EATCS Monographs on Theoretical Computer Science, Springer-Verlag, Berlin - Heidelberg - New York - London - Paris - Tokyo - Hong Kong, 1984
Kurt Mehlhorn:
Data structures and algorithms 2 : Graph algorithms and NP-Completeness
EATCS Monographs on Theoretical Computer Science, Springer-Verlag, Berlin - Heidelberg - New York - London - Paris - Tokyo - Hong Kong, 1984
Christos H. Papadimitriou, Kenneth Steiglitz:
Combinatorial optimization : Algorithms and complexity
Prentice-Hall, Englewood Cliffs, NJ, 1982

* Office Hours:
look here


khuri@informatik.tu-muenchen.de