max planck institut
informatik
informatik
| Lecturers: |
Prof. Dr. Benjamin Doerr,
Dr. Danny Hermelin, and
Dr. Reto Spöhel |
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Time: |
Tuesday, 10-12 and Thursday, 10-12 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Room: |
Building E1.4 (MPI main building), room 0.24 (main lecture hall) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Content: |
This is a first course in graph theory. Topics include basic
notions like graphs, subgraphs, trees, cycles, connectivity, colorability,
planar graphs etc. We continue with some particularly interesting areas like
Ramsey theory, random graphs or expander graphs. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Audience: |
The course counts both as mathematics and computer science lecture (4 hours of lectures per week, 9 credit points).
It requires no particular prerequisites except the basics in mathematics. We offer exercise groups (2 hours per week), which will be set
up in the first lecture. The lecture will be given in English. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Exercise groups: |
Monday, 14:30-16:00 and 16:00-17:30 in rooms 0.21 and 0.23 (next to the lecture hall). Start: April 18. You can register, and login to your personal account here. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Lecture details: |
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Exams/Credit: | There will be a written final exam on July 26, 2011 (see below for details). Eventually, there will also be a repetition exam.
The repetition exam will be oral or written, depending on the number of
candidates. Anyone who got admitted to the final exam will be allowed to participate
in the repetition exam, irrespective of whether they passed or failed
the final. If you take both exams, your final grade will be the better one of the two grades you achieve.
You get a "Schein" if you
reach a grade of "four" or better. To be admitted to either exam, you have to get at least 50% of all points achievable during the semester. In addition, you not only need to have 50% of all available points at the end of the semester, but also after the third and sixth exercise session. You earn points in two different ways: 1) We will hand out exercise sheets in the lecture. We expect you to hand in written solutions to these homework problems. Your solutions will be graded, and you get points accordingly. 2) In each exercise session, there will be a short (ca. 15 min) quiz to test your understanding of the material discussed in the previous lectures. Again your answers will be graded, and you get points accordingly. This system is intended to encourage serious efforts from the very beginning, and is also meant to prevent students who miss too much during the first part of the semester from wasting unnecessary efforts later on. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Final Exam: |
The final exam takes place on Tuesday, July 26, 2011 (this is in the first week of the semester break).
It will be in room "AudiMO" in building E2 2. You have to be there at 9:00, and you will have exactly three (3) hours to
solve the problems.
Since it usually takes some time to set up an exam, don't expect to
finish at 12:00 sharp, but allow some extra time.
You may use one (1) double-sided hand-written page (size DIN A4) of
arbitrary notes and a dictionary. No other books, notes, electronic devices etc. are
allowed. You may bring reasonable food etc. You may use your own
paper, which of course should not contain any other notes.
If you really want, you can write down your answers in German. The exam sheet will be in English, though. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Literature: |
Most of the lecture will follow Reinhard Diestel's great book on graph
theory. Visit
this page
to see the various formats in which the book is available (note that
there is a free PDF version). |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||