# Algorithms and Networks

On this webpage, information on the course Algorithms and Networks will be posted.

## Latest news

• You can check here an Excell spreadsheet with the notes.
• October 31, 2012: Notes of exercise set 1 till 8, and the notes of exam 2.
• Viewing your exam: tuesday, november 13, 1.00 - 1.30, or friday, November 23, 9 - 10 and 14 - 15.
• Note: the deadline for handing in exercise 8 will be strict: with joker rule, it's Friday 09.15.
• October 31, 2012: Notes of exercise set 1 till 7, and the notes of exam 2.
• You can check here an Excell spreadsheet with the notes till November 8. Friday, the last exercise sets 7 will be graded; you need at least a 5.5 for a sufficient note for the course.
• October 31, 2012: Notes of exercise set 1 till 6, and a few notes of 7 (others still to be graded) and the notes of exam 2.
• Material of exam 2:
• NP-completeness: see sheets
• Exact algorithms: see sheets
• Fixed parameter tractability: see sheets, but NOT:
• Kernelization for cluster editing
• Kernelization for non-blocker
• Treewidth: see sheets
• Coloring: NP-completeness of coloring. (I.e., from the sheets for coloring, only the NP-completeness proof.)
• October 31, 2012: Notes of exercise set 1 till 6.
• October 29, 2012: Notes of exercise set 1 till 5.
• Added: exercise set 8: Pdf-file.
• Added: exercise set 7: Pdf-file.
• Thursday, October 18, 2012: Notes of exercise set 1 till 4, now with two extra notes for students that used the joker rule.
• Thursday, October 18, 2012: Notes of exercise set 1 till 4.
• Monday, October 15, 2012: Notes of exercise set 1 till 3.
• View your exam: in the break in class on monday, or monday at 13.30 in Hans' office.
• An additional rule is added, that allows in more cases a re-exam. (Note: when you were elegible for a re-exam under the old rules, you still are. The new rule is below in bold.)
• Notes of Exam 1.
• Exercise set 6.
• Material of exam 1:
• Facility location: see sheets
• Shortest paths, but NOT bottleneck sortest paths
• TSP, but NOT the Held-Karp algorithm
• Maximum Flow, but NOT the Lift-to-Front algorithm
• Minimum Cost Flow
• Matching, but NOT the Tic-Tac-Toe diversion
• The Stable Marriage problem
• Note: Exam 1 is scheduled Wednesday October 10, at 11.00 in room BBL-023.
• Friday, October 5, 2012: Notes of exercise set 1 and 2.
• Notes of exercise set 1.
• Exercise sets 4 and 5 online:
• The exam is now scheduled on Wednesday, October 10, at 11.00 hours, probably in BBL-023. (Check the room number later.)
• Exercise set 3 online: Pdf-file.
• Please note that the first exam will not be on the scheduled time. More info later.
• Exercise set 2 online: Pdf-file.
• Exercise set 1 online: Pdf-file.
• The course starts on Wednesday, September 5, 2012. There is no course on Monday Sep 3, because of the Master introduction.

## General information

For general information, see the Departments webpage on this course.

The language of the course is English, unless all students following the course are Dutch speaking.

## Exams and exercises

The course has two exams, the first approximately half the course and the second at the end of the course. In addition, you must make a number of exercises.

### Exam 1

Exam 1 takes two hours. The precise topics of Exam 1 will be announced later. The exam is about approximately the first half of the course, and will at least cover: flow, shortest paths, matching, stable marriage. It will also include the material of exercises for these topics.

You may have with you four pages (sides) with written or printed notes, but not more.

### Exam 2

Exam 2 takes three hours. The precise topics of Exam 2 will be announced later. It covers basically the second half of the course, assuming you did not forget the first half. It will also include the material of exercises for these topics.

### Re-exam

There is one possibility to do a re-exam.
• The re-exam replaces the lowest score of your two exams.
• The re-exam is about the entire material.
• See below for the rules if you are entitled to such a re-exam.
• If you do a re-exam then the maximum possible score for the course is an 8. This does not apply if you could not do one of the exams earlier due to reasons like illness, or other permitted absences.

### General information

• Note that a significant part of the information will be given only in the lectures. Several of the results discussed are very scattered in the literature, and thus it is recommended to follow the course, and make your own course notes. If you cannot follow a lesson, it is recommended to borrow and copy course notes from another student.
• You must hand exercises at most two weeks after they have been handed out. The deadlines will be mentioned on this webpage.
• Extensions of the deadline will usually not be granted. It is a good idea to finish the exercises earlier than the deadline. In particular, there is the following rule:
• You may hand in at most two times, one of the exercise sets three days after the deadline. (Joker rule.) This year, three days means: ultimately Monday morning 09.30.
• If you miss a deadline for a third or later time, this is acceptable only in case of special circumstances (serious illness, etc.). Otherwise, you score a 0.
• You must have an average of at least 6.0 for the exercises.
• In case you have an average smaller than 6.0 for the exercises, then you are subject to the aanvullende toets rules. In this case, you must hand in all exercise sets again which receive an insufficient grade, or, subject to a decision of the lecturer, you get a number of replacement exercises.
• You must have an average of at least 5 for the exams.
• 50 percent: exercises
• 25 percent: exam 1
• 25 percent: exam 2
If you have an insufficient final grade, then the following rules apply:
• Illness or other absence during exams: If you have a good reason for absence during an exam, you get a replacement exam. This may possibly be an oral exam, or a written exam. After this, there is no re-exam.
• Inspanningsverplichting: If you have less than a 4 for the average, you fail the course.
• Aanvullende toets: If you have a 4 or more for the average, but no sufficient final grade, you can do a re-exam (additional testing).
• You can also do a re-exam IF you have at least a 5.5 for one of the exams and at least a 6 for the average of the exercise sets.
• If your average note is at least 5.2 and the average of your exams is at least 4.8, then you can do instead of a re-exam, an extra written task. If you pass this, you obtain a 6 for the course.

You may consult notes, and printouts of sheets during the exam: in total at most four pages, but no books.

## Handing in and grading of exercises

Please hand in the solutions on paper to the lecturer mentioned at the beginning of a set of exercises. This must be done on or before the deadline. More precisely: you can hand in the work on paper in the classroom just before or after the lectures (put the exercises in the folder with the right number) , or place the work in the mailbox of Hans Bodlaender at the 5th floor of the BBL. The deadline is slightly soft: the real hard deadline is the day after the deadline at 09.00 hours sharp. See also above about the rule of 'missing one deadline a few days'.

You can write either in English or in Dutch.

• well phrased
• understandable
• and of course, correct.
Work that is hard to read or very messy will be graded with a 0. Do not forget your name and student number on your work.

Exercises will be graded from a natural number from 0 to 13 (usual at most a 10). Often, there is an easy exercise giving one point, and a hard one giving one point. In several cases, more exercises will be given than needed to obtain a 10; making more exercises can give a higher grade. However, grades above 10 only count if your average for all exercise grades up to 10 is at least a 6. Grades depend both on the correctness, and on the quality of your writing and explanations.

### Working together on exercises

It is allowed to discuss solutions with other students, under the following rules:
• If you worked together, you must mention this at the start of each handed in exercise set, with the names of the other students you cooperated with.
• Cooperation is allowed in finding the solutions, but NOT in writing. You must write down in your own words the solutions.

## Exercise sets

The exercise sets will be posted here. Note that the real deadline is always the next morning at 09.15, and that there is the {\em joker rule}.

1. Exercise set 1: Pdf-file.
2. Exercise set 2: Pdf-file.
3. Exercise set 3: Pdf-file.
4. Exercise set 4: Pdf-file.
5. Exercise set 5: Pdf-file.
6. Exercise set 6: Pdf-file.
7. Exercise set 7: Pdf-file.
8. Exercise set 8: Pdf-file.

## Schedule and materials

The schedule is as follows. Changes to the schedule are always possible.
• Monday, September 3, 2012. No course yet, because of the introduction of the Master programme.
• Wednesday, September 5, 2012.
• Week of September 10 - 14: Hans Bodlaender is travelling; no course. Time to make your first exercise set!
• Monday, September 17, 2012.
• Shortest paths.
• Wednesday, September 19, 2012.
TSP and variants.
• Monday, September 24, 2012.
The Travelling Salesman Problem.
Network flow.
• Wednesday, September 26, 2012.
Minimum cost flow.
• Monday, Oktober 1, 2012.
Minimum cost flow
Matching
• Wednesday, Oktober 3, 2012.
Matching and stable marriage.
• Monday, Oktober 8, 2012.
NP-completeness and complexity I.
• Wednesday, Oktober 10, 2011.
Exam 1. Note the time!
• Monday, Oktober 15, 2012.
• Wednesday, Oktober 17, 2012
NP-completeness and complexity II.
• Monday, Oktober 22, 2012.
Exact, exponential time algorithms.
• Wednesday, Oktober 24, 2012.
Parameterized complexity.
• Monday, Oktober 29, 2012.
Kernelization
• Wednesday, Oktober 31, 2012.
Treewidth I.
• Monday, November 7, 2012.
Treewidth II. Planar graphs. Coloring
• Exam 2
Reserve topics:
• Graph coloring
• Vertex cover and related problems
• Approximation
• Small world graphs
• Logspace

## Materials of previous years

These are still materials of last year. Some changes are expected. Zipfiles:

• Shortest paths.
• Introduction to Algorithms, chapter 24 and 25.
• Combinatorial optimization, chapter 7.
• Network flows, section 4.2.
• The Travelling Salesman Problem
• M. Jünger, G. Reinelt, and G. Rinaldi. The Traveling Salesman Problem. In Handbooks in Operations Research and Management Science, Volume 7, Network Models. Elsevier, 1995.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, 2nd edition. MIT Press, 2001. Chapter 35.2, pages 1027 - 1032.
• Network flow I.
• Introduction to Algorithms, chapter 26.
• Network flows, section 6.2.
• Minimum cost flows.
• Network flows. Chapter 9.
• Matching.
• Introduction to Algorithms, chapter 26.
• Network flows, chapter 12.
• Stable marriage problem
• Algorithm Design, chapter 1.
• NP-completeness.
• Introduction to Algorithms, chapter 34.
• Treewidth
• Algorithm Design, chapter 10.2, 10.4 and 10.5.
• Planar graphs
• Graph Drawing: Algorithms for the Visualization of Graphs
Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ionannis G. Tollis, Prentice Hall, 1998, ISBN 0133016153.
The planarity testing algorithm discussed in the course is described here.
• More on planar graphs e.g., in: Planar Graph Drawing. Takao Nishizeki and Md. Saimur Rahman. Lecture Notes Series on Computing - vol 12, 2004.
• Vertex cover and related problems

### Recommended books (not obligatory)

None of these books is needed to be able to follow the course. For some topics, they help.
• John Kleinberg, Eva Tardos. Algorithm Design. Pearson/Addision Wesley, 2005. ISBN 0-321-29535-8.
• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms. MIT Press / McGraw-Hill, 2001. ISBN 0-262-03293-7. (References are to the second edition. The first edition is also usable.)
• Alexander Schrijver. Combinatorial Optimization. Polyhedra and Efficiency. Springer, 2003. ISBN 3-540-44389-4.
• Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. Network flows. Theory, Algorithms, and Applications. Prentice Hall, 1993. ISBN 0-13-617549-X.