Algorithms and Networks
On this webpage, information on the course Algorithms and Networks
will be posted.
Latest news
- On the re-exam: it is on wednesday, May 30, 14-17; room BBL-001.
- You can do a re-exam for part 1, or a re-exam for part 2; not for both.
- The note replaces the note for the part that you redo.
- But you cannot get a lower note
- You are allowed to do a re-exam to get a higher note, even if you had a sufficient note.
- The material is the same as for the exam that you re-do.
- You still are allowed four sides a4 of self-made notes.
- Grades of the course.
- Looking at your exam: Tuesday, May 1, 9-9.45 and 10.30 - 11.00.
If you cannot come at that time, email Hans Bodlaender.
- Grades of the second exam. If yours in not
there or not correctly displayed on the webpage, contact Hans Bodlaender. Some of you need a re-exam. Given the
fact that exam 2 was somewhat tough, the condition that the average of exams should be at least a 5 is scrapped.
A few exercise 7's are graded; a few by email still have to be done, but you can see an estimate of your endnote already.
- Grades of exercise set 6. It yours in not
there or not correctly displayed on the webpage, contact Hans Bodlaender.
- Question hour: Thursday, April 19, 11.00; meeting room near elevator at 5th floor BBL.
- Grades of exercise set 5. It yours in not
there or not correctly displayed on the webpage, contact Hans Bodlaender.
- Grades of exercise set 4. It yours in not
there or not correctly displayed on the webpage, contact Hans Bodlaender.
- We decided that this year there will only be seven exercise sets. (If you disagree with
this last minute change, then let Hans Bodlaender know, and he will hand you an eight set.) Your grade
will be the average grade of the seven sets. For this reason, you also receive a second joker.
- Grades of exercise set 3.
- Notes of exam 1.
- Hours for looking at your exam (room BBL 503):
- Tuesday, March 20, 9 - 9.30
- Tuesday, March 20, 10.30 - 11
- Wednesday, March 21, 15.30 - 16.30
- Notes exercise set 2.
Please check if your note is correctly noted here! If you handed in work, but your
note isn't here, contact Hans Bodlaender.
- Exercise 3: I received some questions when a graph is a path. Exercise 3 now has a clarification
with a simple picture for this.
- NOTE: The first exam is in the morning, NOT in the afternoon. As this is a 2 hour exam, we start at 09.00.
Your teacher will be there at 08.30, however.
- Notes exercise set 1. Corrected: Feb 29, 2012.
Please check if your note is correctly noted here!
Login with your solis-id for looking at the file. If your note isn't there, you probably forgot your name or
studentnumber on your work; send an email with your name and student number to Hans Bodlaender: H.Bodlaender@uu.nl
- February 21, 2012: different materials are posted. Note for the joker rule: the ultimate time
is monday 09.30 (in the morning) after the original deadline.
- February 8, 2012: first lesson. Materials are online.
- January 31, 2012: schedule posted
- January 19, 2012: starting to update the website for 2011/2012.
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.
Topics of the exam: what has been discussed on the first weeks, till Friday, March 2, 2012
and what is on these topics in the exercise sets.
The following from the slides were not covered and thus are not part of the exam:
- From Shortest Paths: Bottleneck shortest path
- Flow: The lift-to-front algorithm (part 6, slide 41 till 53)
- Matching: Schrijver's algorithm (dia 33-37)
Exam 2
Exam 2 takes three hours.
The precise topics of Exam 2 have been announced: the material covered by Stefan Kratsch and
the last part on certifying algorithms.
It will also include the material of exercises for these topics.
Re-exam
You can do a re-exam for one of the two exams, not both. Email Hans Bodlaender at least three
days before the re-exam that you want to take a re-exam. You cannot obtain a lower note by
doing a re-exam. The time and place of the re-exam can be found on the department page of the course.
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. (Not enforced in 2011/2012.)
- The final grade is made as follows:
- 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 aanvullende toets.
- 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 an aanvullende toets
(additional testing). Depending on why you had an insufficient final
grade, and the distance of your grade to a 6, you get an additional task
(e.g., additional exercises or small project, either programming or
theoretical), or have an additional exam.
(Example: your grades for the exercises are 7; and the average for your
exams is 4.7. Your task consists of some additional exercises on the
topics where you gave wrong answers in the test.) The aanvullende toets
is also given with a deadline. If you do not hand in the task at or
before the deadline, you fail 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.
Your work should be
- well phrased
- readable
- 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.
Grading
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.
- Exercise set 1:
Pdf-file.
Deadline: Wednesday, February 22, 2012.
- Exercise set 2:
Pdf-file.
Deadline: Wednesday, February 29, 2012.
- Exercise set 3:
Pdf-file.
Deadline: Friday, March 9, 2012. 09.15 sharp.
Joker: Wednesday, March 14, 09.15 sharp.
- Exercise set 4:
Pdf-file.
Deadline: Wednesday, March 21, 2012.
- Exercise set 5:
Pdf-file.
Deadline: Wednesday, April 4, 2012.
- Exercise set 6:
Pdf-file.
Deadline: Wednesday, April 11, 2012.
- Exercise set 7:
Pdf-file.
Deadline: Wednesday, April 18, 2012.
Below, you see the exercise sets of last year. Note that there will
be some changes for the sets of this year.
- Exercise set 1 2010/2011:
Pdf-file.
Deadline: Monday February 21, 2011.
- Exercise set 2 2010/2011:
Pdf-file.
Deadline: Monday February 28, 2011.
- Exercise set 3 2010/2011:
Pdf-file.
Deadline: Monday March 7, 2011.
- Exercise set 4 2010/2011:
Pdf-file.
Deadline: Monday March 21, 2011.
- Exercise set 5 2010/2011:
Pdf-file.
Deadline: Monday March 28, 2011.
- Exercise set 6 2010/2011:
Pdf-file.
Deadline: Monday April 11, 2011.
- Exercise set 7 2010/2011:
Pdf-file.
Deadline: Monday April 18, 2011.
- Exercise set 8 2010/2011:
Pdf-file.
Deadline: Tuesday April 26, 2011.
Schedule and materials
The schedule is as follows. Changes to the schedule are
always possible.
- Wednesday, February 8, 2012.
- Friday, February 10, 2012.
- Wednesday, February 15, 2012.
TSP and variants.
- Friday, February 17, 2012.
The Travelling Salesman Problem.
Network flow.
- Wednesday, February 22, 2012.
Minimum cost flow.
- Friday, February 24, 2012.
Minimum cost flow
Matching
- Wednesday, February 29, 2012.
Matching.
- Friday, March 2, 2012.
Matching; stable marriage.
- Wednesday, March 7, 2012.
No course: Turing symposium. Recommended!
- Friday, March 9, 2011.
8.30 - 11.30: Exam 1. Note the time!
- Week of March 12 - March 16, 2012.
Re-exam week. No course.
- Wednesday, March 21, 2012.
NP-completeness and complexity I.
- Friday, March 23, 2012
NP-completeness and complexity II.
- Wednesday, March 26, 2012.
Exact, exponential time algorithms.
- Friday, March 28, 2012.
Parameterized complexity.
- Wednesday, April 4, 2012.
Kernelization
- Friday, April 6, 2012.
No course: Good Friday (Goede vrijdag); Friday before Eastern. (University is closed.)
- Wednesday, April 11, 2012.
Treewidth I.
- Friday, April 13, 2012.
Treewidth II.
Certifying algorithms;
- Friday, April 20, 2012.
Exam 2
Reserve topics:
- Graph coloring
- Vertex cover and related problems
- Approximation
- Small world graphs
- Logspace
Materials of last year
These are still materials of last year. Some changes are expected.
Zipfiles:
- Monday, February 7, 2011:
- Thursday, February 10, 2011:
- Monday, February 14, 2011:
- Thursday, February 17, 2011 and Monday, Februari 21, 2011:
- Maximum flow.
Powerpoint file lecture. Revised version, Friday February 18, 2011.
- Handouts Maxflow.
(Powerpoint converted to pdf; handout format. Version 2010/2011.)
- Handouts Maxflow.
(Powerpoint converted to pdf; handout format. 6 pages per sheet.
Version 2010/2011.)
- Thursday, February 24, 2011:
- Monday, February 28, 2011:
- Matching.
Powerpoint file lecture.
- Handouts Matching.
(Powerpoint converted to pdf; handout format. Version 2010/2011.)
- Handouts Matching.
(Powerpoint converted to pdf; handout format. 6 pages per sheet.
Version 2010/2011.)
- Thursday, March 3, 2011:
- Thursday, March 10, 2011 and Monday, March 21, 2011:
- Thursday, March 24, 2011:
- Monday, March 28, 2011:
- Thursday, March 31, 2011:
- Thursday, April 7, 2011:
- Monday, April 11, 2011:
- Thursday, April 14, 2011:
Materials of previous years
Some of this will be reused, possibly after being changed. These also can be
consulted for further background.
Some other files, and files of previous years.
Further reading
See below for more information on the books.
- 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.
Webpage made and maintained by Hans Bodlaender.
Thanks to several students who helped with links, pdf-versions of
powerpoint files, etc.