Graph Algorithms (MuA)
News
Content
Graph algorithms belong to the most important tools in computer science with plenty of applications in different areas (e.g., route navigation, telecommunications, production planning, as well as different combinatorial optimization problems). After introducing some basic definitions and concepts, we will consider shortest paths, matchings and routing problems, as well as algorithms in networks. In all these cases, we will mainly concentrate on the design of efficient algorithmic solutions.
Exam
Oral examinations after the course.
Schedule
-
Lecture:
Day Time Room Thursday 14:15-15:45 A4 Monday 18:00-19:30 D1
-
Tutorials:
Day Time Room Thursday 13:15-14:00 E2.145
Teaching material
| Lecture | Slides (als PDF) | Literature |
|---|---|---|
| 13.10.2011 | Introduction, APSP | [Cormen]: 620-632 |
| 20.10.2011 | Shortest paths | [Motwani]: 278-283 |
| 24.10.2011 | Shortest paths | [Motwani]: 283-286 |
| 27.10.2011 | Shortest paths | [Motwani]: 286-288 |
| 31.10.2011 | Approximating shortest paths | no reference given |
| 03.10.2011 | Approximating shortest paths | no reference given |
| 10.11.2011 | Matchings in bipartite graphs | [West]: 107-112 |
| 17.11.2011 | Matchings in bipartite graphs | [West]: 112-113, [Chartrand]: 166-173 |
| 24.11.2011 | Matchings in graphs | [Chartrand]: 166-173 |
| 28.11.2011 | Matchings in graphs | [West]: 136-139 |
| 01.12.2011 | Interconnection networks | [Leighton]: 392-399 |
| 08.12.2011 | Algorithms in hypercubic networks | [Leighton]: 439-451 |
| 12.12.2011 | Algorithms in networks | no reference given |
Exercises
Exercise sheet 1Exercise sheet 2
Exercise sheet 3
Exercise sheet 4
Exercise sheet 5
Exercise sheet 6
Exercise sheet 7
Exercise sheet 8
Exercise sheet 9
Exercise sheet 10
Bonus points
There is a possibility to improve your grade in the final exam, if
- you achieve at least 50% of the points assigned to the exercises, which are corrected during the term. Then, you may obtain an upgrade of 1/3 .
- you achieve at least 80% of the points assigned to the exercises, which are corrected during the term. Then, you may obtain an upgrade of 2/3 .
- the best grade you can achieve is 1,0 (sehr gut).
- Important: you can not improve a grade of 5,0 (nicht bestanden) by bonus points.
Literature
- West: "Introduction to Graph Theory",
Pretince Hall, 2nd ed., ISBN: 0-13-014400-2 - Chartrand, Oellermann: "Applied and Algorithmic Graph Theory",
McGraw-Hill, ISBN: 0-07-557101-3 - Cormen, Leiserson, Rivest, Stein: "Introduction to Algorithms",
MIT Press / McGraw-Hill, 2nd ed., ISBN: 0-262-53196-8 - Cormen, Leiserson, Rivest: "Algorithmen - Eine Einführung",
Oldenburg, ISBN: 3-486-27515-1 - Motwani, Raghavan: "Randomized Algorithms",
Cambridge University Press, ISBN: 0-52-147465-5 - Leighton: "Parallel Algorithms and Architectures: Arrays, Trees,
Hypercubes",
Morgan Kaufmann Publishers, ISBN: 1-55-860117-1