Department of Computer Science | Institute of Theoretical Computer Science
Department of Computer Science | Institute of Theoretical Computer Science
Hafsteinn Einarsson, Rajko Nenadov
Wednesday,
10.15 - 11.55 a.m., CAB G 51 (Lecture)
Thursday, 10.15 - 11.00
a.m., CAB G 59 (Exercises).
You
may use all material provided during the lecture (slides, exercises
etc.) and any handwritten material plus your own solutions to the
graded homeworks. (In particular you may thus not bring
books.)
Further typeset material can be
allowed if it is produced by yourself. Please contact us in advance if
you plan to use any such material.
The exam is 70% of your final grade. The remaining 30% are covered by graded homework (see Exercises).
For studying, here
is a
collection of questions from old
exams.
(IMPORTANT, the date was wrong previously on the website, now it is correct) Date of exam: Tuesday, June 4th 2013 from 10:00 to 13:00 (CAB G 11).
Graphs are an important concept in mathematics and computer science. This lecture presents algorithms for fundamental problems in graph theory. Amongst others, it covers the following topics:
Students of Computer Science or Mathematics in the 6th semester or later.
Lecture slides (ETH login required)
Some notes on finite two-player games
Regular Exercises: Every week there will be an exercise sheet handed out a couple of days before the exercise class. Students are expected to read and understand the exercises and are welcome to solve them. Solutions will be presented in the exercise class.
Graded Homework: In week 4, 7 and 10 of the term (roughly) we will hand out a specially marked exercise, whose solution (typeset in LaTeX or similar; see our guide to learning LaTeX in the theses section) is due two weeks later.
These solutions will be graded, and will each account for 10% of your final grade. You are welcome to discuss these exercises with
your colleagues, but we expect you to hand in your own writeup.
Note that credit points for PhD students will be given according to the regulations of their respective departments. In particular, for D-INFK PhD students the rule for obtaining credits (KE) will be the same as for masters students, i.e., they will not receive credit points for simply sitting in the course or only successfully solving the special exercises.
First Exercise session: February 21st.
Graded Homework
Regular Exercises
* Beware of the 1976 version Graph Theory with Applications which is not up-to-date and not recommended for this course.
The first student to successfully hand in a solution to the challenge exercise on graded homework sheet 3 receives a book of his/her choice from the following list (note that the fifth book is only available in German):