Home assignments should be submitted to mailbox 02 on Schreiber's ground floor (next to labs 004 and 005).
Please make sure to save a copy of the assignment in case it gets lost!
If you would like an extension for the homework, you can have an automatic extension of 4 days (96 hours), without asking the course instructors. An additional extension will only be given in case of miluim or sickness over 4 days long. There will be no exceptions.
You may submit the homework up to a week late, and have a reduction of 25% from the grade, or up two weeks late with reduction of 50%.
All exercises will consist of 8 questions. The final grade for the exercise will be the average of the best 7 answers.
All deadlines are 12:00 (noon) of the due date. This includes extensions.
Unless stated otherwise (or obvious from the context), the graphs are simple and are represented using adjacency lists (not using an adjacency matrix).
Question 4: A path may cross the same edge more than once.
You may not only use algorithms and variations of algorithms learned in class (e.g. you may not use Dijkstra's algorithm).
Hint for Question 2a: it is better to present an algorithm whose complexity depends polynomially on k, which you can prove, than one whose complexity does not depend on k which you cannot prove.
Solutions and Polls
We will publish a detailed solution to 2 questions from each homework, and outline solutions for the other 6.
You can decide which questions we publish detailed solutions for by participating in the poll.
The polls close 3 weeks after the submission date of the exercise.
The solutions will be published one week after the poll closes.