# News

April 26th

Re-exam or additional exam Grades and endnotes.

If you want to view your work, contact Hans Bodlaender for an appointment before May 20.

February 22th

Computation of final results: Grades.

Hans

February 15th

Notes of Exercise set 6: Grades.

Johan

February 15th

Notes of Exercise set 7, now with "joker exercises": Grades. Set 6 will follow later.

February 10th

### Notes

Tuesday, February 14, 2017: You can view your work in Room BBG-503 from 9.00 - 9.30.
Wednesday, February 15, 2017: You can view your work in Room BBG-503 from 9.00 - 9.30.
February 1th

Nores of Exercise set 7: Grades. Set 6 will follow later.

January 26th

On request, an old exam. Note that NP-completeness was part of the exam material that year, and is not this year.

January 24th

### 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 copy-past 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 NOT-ALL-EQUAL-SAT, 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

January 12th

### 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

January 12th

### Results of Exercise Set 5 and Exercise Set 7 on-line

The results of exercise sets 1-5 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

January 12th

January 10th

January 4th

January 4th

### Notes

Tuesday, January 10, 2017: You can view your work in Room BBG-503 from 14.00 - 15.00.
December 14th

December 14th

December 13th

### Exercise sets 5 and 6

Sorry guys, I forgot to put exercise set 5 on-line yesterday. I just published it, so you can start working on it.

Next week (the week of the first exam), there will not be an exercise set. So exercise set 6 will become available after the christmas break.

Johan
December 13th

### Exponential-time algorithms and the first exam

During the lectures, we did not treat the 'local search' part of the lecture 'Some Techniques for Exact Exponential-Time 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 exam. 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.

Johan
December 6th

Johan

December 6th

### PACE 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, fine-grained, parameterized, or fixed-parameter tractable algorithms.

This may be a nice topic for a experimentation project or thesis project.

Hans and Johan
December 6th

### A 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 x-th 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

November 29th

### First exam starts at 8:30 and an update to the Schedule

The first exam 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 exam, we will move to EDUC-GAMMA for this exam.

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

November 8th

### 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 e-mail Hans Bodlander using [AN] in the subject of your e-mail. We use grep to filter the appropriate e-mail 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

Oktober 12th

### 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.

NP-Completeness 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 exponential-time 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

August 16th

### 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 e-mail to Johan van Rooij.

Johan