Algorithms and Networks (2010-2011)
On this webpage, information on the course Algorithms and Networks
will be posted.
Latest news
- 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.
Exam 2
Exam 2 takes two hours.
The precise topics of Exam 2 will be announced later. The exam is about
approximately the second half of the course; to be precisely: those topics not
covered by Exam 1.
It will also include the material of exercises for these topics.
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 once one of the exercise sets three days after
the deadline. (Joker rule.)
- If you miss a deadline for a second 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 regeling.
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.
- 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 absense during exams: If you have a good
reason for absense 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 excercises. 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 excercise 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:
- Exercise set 3:
- Exercise set 4:
- Exercise set 5:
- Exercise set 6:
- Exercise set 7:
- Exercise set 8:
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 preliminary 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.
Network flow.
- Wednesday, February 22, 2012.
Minimum cost flow.
- Friday, February 24, 2012.
Matching
- Wednesday, February 29, 2012.
Matching. The stable marriage problem.
- Friday, March 2, 2012.
Certifying algorithms; planarity.
- 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: Black Friday (Goede vrijdag); Friday before Eastern.
- Wednesday, April 11, 2012.
Treewidth I.
- Friday, April 13, 2012.
Treewidth II.
Topic to be determined.
- 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.