News
Notes
Tuesday, February 14, 2017: You can view your work in Room BBG503 from 9.00  9.30.Wednesday, February 15, 2017: You can view your work in Room BBG503 from 9.00  9.30.
On request, an old exam. Note that NPcompleteness was part of the exam material that year, and is not this year.
Two notes on Exercise Set 7
Students pointed out to me that there are two small errors in the exercise set:
 Question 2: The definition of a grid graph contains a copypast error. The current formulation of E_{p x q} has the same edges twice. Of course the definition should de the union of the horizontal edges and the vertical edges, otherwise the result would not be a grid.
 Question 4: In the definition of NOTALLEQUALSAT, we unfortunately omitted that all clausese have size at least two. A clause of size less than two would make no senses in this case as it would never contribute to the value of the solution. Thus the hint in the question should be interpreted as if all clauses have size at least two.
Johan
Updated results of Exercise Set 5
I have updated the results of exercise set 5. The grades can be found here: Grades.
If your grade is still missing (both if you handed it in very early, or when you used a joker), please let us know, because then something has gone wrong.
Johan
Results of Exercise Set 5 and Exercise Set 7 online
The results of exercise sets 15 can be found here: Grades. Note that exercise set 5 has not been checked yet for students who handed in their work late. Also, work for at least three groups of students seems to be missing in the set of printed solutions that I have now, while they are handed in on time. We will fix this and add the results next week.
Exercise set 7 is online, see Exercises. In one of the exercises, you are asked to use the gap technique that we have not yet treated as such in the lecture. However, we have treated, without knowing the name 'gap technique', several examples of proofs that certain approximation algorithms cannot exists assuming that P differs from NP. A proof like this (some approximation algorithms cannot exists assuming that P differs from NP) is exactly what we expect here. Good luck.
Johan
Notes
Tuesday, January 10, 2017: You can view your work in Room BBG503 from 14.00  15.00.Exercise sets 5 and 6
Sorry guys, I forgot to put exercise set 5 online yesterday. I just published it, so you can start working on it.
Next week (the week of the first examn), there will not be an exercise set. So exercise set 6 will become available after the christmas break.
JohanExponentialtime algorithms and the first examn
During the lectures, we did not treat the 'local search' part of the lecture 'Some Techniques for Exact ExponentialTime Algorithms'. We also did not treat the 'Steiner Tree' part of the lecture 'Inclusion/Exclusion'. Both of these are NOT part of what you should study for the first examn. I, however, did not remove these two cases from the slides in case anyone is interessted in them. Note that, maybe, we will move the Steiner Tree case to the second part of the course.
JohanPACE Challenge
The goal of the Parameterized Algorithms and Computational Experiments Challenge is to investigate the applicability of algorithmic ideas studied and developed in the subfields of multivariate, finegrained, parameterized, or fixedparameter tractable algorithms.
This may be a nice topic for a experimentation project or thesis project.
Hans and JohanA note on the first exercise (Lift Scheduling) in exercise set 3
After some questions from students, let me emphasise two points regarding exercise 1 in exercise set 3. I guess they follow from the statement of the exercise, but to avoid confusion I post them here.
 AGV's can only enter the lift on its floor of origin and only leave the lift at its destination floor. So we disallow solutions where an AGV is temporarily parked at another floor.
 Queue's have the property that no AGV can pass another AGV standing in the same queue. That is, in order to let an AGV at the xth position in the queue enter the lift, all AGV's on positions 1 up to x have to be processed first.

Succes with the exercises!
Johan
First exam starts at 8:30 and an update to the Schedule
The first examn will start at 8:30, NOT at 9:00 as the regular lectures. Please remember this. You will not get extra time if you are 30 minutes late. Since our standard lecture rooms are too small for the first examn, we will move to EDUCGAMMA for this examn.
Futhermore, I have updated the schedule to match the progress we have made thus far in the lectures (for the track on Tuesdays). In the future, I will keep making small updates. Only when large changes are applied, I will anounce it through a news item like this one.
Johan
A change in the rules regarding the exercise sets
I am delighted by the very high number of students that have signed up for the Algorithms and Networks course this year. Thank you all for showing an interrest in our course. However, for obvious practical reasons, this forces us to change the rules regarding the exercise sets: you are now obliged to hand in your exercise sets in pairs. With the current amount of participants, it is simply not feasible for your teachers to grade individuale exercises on a weekly basis.
The new rules are as follows: you must hand in your answers to the exercise sets in pairs. In the case that more than one person hands in his/her answers to the exercises alone, we will not grade any work handed in by a single person, unless the person has our explicit approval. If you do not (yet) have a partner and are unable to find one yourself, please email Hans Bodlander using [AN] in the subject of your email. We use grep to filter the appropriate email for this course, failing the use the appropriate [AN] tag in the subject is at your own risk. Hans will match students who ask for a partner by mail at random.
See you next week!
Johan
Algorithms for Decision Support and Website Updates
Due to a change in the curriculum with respect to last year, some content from the course Algorithms and Networks has been moved to the course Algorithms for Decision Support. Consequently, this material is removed from this course and new material on new topics are added.
NPCompleteness is now considered to be known to the students, and most content on the Travelling Salesman Problem has been removed. The part on shortest paths has also been reduced in size due to other courses covering this topic. To compensate for this, we will add content on approximation algorithms, exact exponentialtime algorithms, transformations for dynamic programming, and some related complexity theory. An overview of the course in its new form can be found under Lectures / Schedule.
In the comming weeks we will continuously update the website to update the materials accordingly.
Johan
New Algorithms and Networks website created
Welcom to the new Algorithms and Networks website. This site contains the same information as the previous website, it only looks better, and we hope you can find way around more easily.
For any feedback on the website, including errors, broken links, etc. please send an email to Johan van Rooij.
Johan