Some nice Markdown
==================
Some other section
------------------
1) First
2) Second
BBL!
Algorithms and Networks
On this webpage, information on the course Algorithms and Networks
will be posted.
Latest news
- Exercise set 6.
- Material of exam 1:
- Facility location: see sheets
BBL!
- 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.
- 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 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).
- 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.
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. Note that the real deadline is always the next morning at 09.15, and
that there is the {\em joker rule}.
- Exercise set 1:
Pdf-file.
Deadline: Monday, September 17, 2012.
- Exercise set 2:
Pdf-file.
Deadline: Monday, Oktober 1, 2012.
- Exercise set 3:
Pdf-file.
Deadline: Monday, Oktober 8, 2012.
- Exercise set 4:
Pdf-file.
Deadline: Monday, Oktober 15, 2012.
- Exercise set 5:
Pdf-file.
Deadline: Monday, Oktober 22, 2012.
- Exercise set 6:
Pdf-file.
Deadline: Monday, Oktober 29, 2012.
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.
- 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.
Certifying algorithms;
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:
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.