UU
HOME cs.uu.nl

MASTER PROGRAM: APPLIED COMPUTING

MSc Programma ``Algorithmic Systems" 2004-2005

Course: Network Algorithms (Netwerkalgoritmen, NA)

In many applications, networks and graphs are used as a model. Tyical examples are networks of roads, or electronic networks. In other applications, the graph model may be less obvious, but appears to be very useful, like for scheduling problems. In this course, we look to the translation of problem to network model, and we look to algorithmic problems and their solutions on networks and graphs.

Lecturer:

Grading

There are two exams, and a number of exercises. The end note for the course of a student is Each of these three parts should have a note of at least 4 to have a sufficient end note. So, both exams count for 30 procent, and the exercises for 40 procent.

It is possible to replace one or both of the exams by an assignment. This can be a literature study, or an experimentation/implementation task. In case a student want to do this, the following rules apply:

Notes

Schedule

Part 1: Paths, flows, and matchings

  1. February 7, 2005. Monday. Shortest Paths I.
  2. February 9, 2005. Wednesday. Shortest Paths II.
  3. February 14, 2005. Monday. The Travelling Salesman Problem.
  4. February 16, 2005. Wednesday. Network Flow I.
  5. February 21, 2005. Monday. Network Flow II. Minimum Cost Flow I.
  6. February 23, 2005. Wednesday. Minimum Cost Flow II.
  7. February 28, 2005. Monday. Matching I.
  8. March 2, 2005. Wednesday. Matching II. Stable marriage problem.
  9. March 7, 2005. Monday. First Exam.

Part 2: Advanced topics

  1. March 9, 2005. Wednesday. Graph Isomorphism.
  2. March 14, 2005. Monday. Graph Isomorphism on trees. Planarity I.
  3. March 16, 2005. Wednesday. Planarity II and Graph Drawing.
  4. March 21, 2005. Monday. Trees and Treewidth I. Note that there is no class on Wednesday, March 23 (and neither on 2nd Eastern Day).
  5. March 30, 2005. Wednesday. Treewidth II.
  6. April 4, 2005. Monday. Sets in Graphs.
  7. April 6, 2005. Wednesday. Coloring.
  8. April 11, 2005. Monday. The Steiner Tree Problem
  9. April 13, 2005. Wednesday. The Steiner Tree Problem; Fixed Parameter Complexity.
  10. April 20, 2005. Wednesday. Second Exam. (9-11.)

Exercises

There will be eight sets of exercises. The exercises will be listed here. For each exercise, there is a deadline for handing in the solution, which is usually two weeks after the moment the relevant material has been lectured.

Solutions should be written out in detail, with carefull explanation of the methods and arguments used, and written legibly, in correct Dutch or English.

  1. Exercise 24-5 from Introduction to Algorithms, Cormen et al (2nd edition), page 617, 618. This is exercise 25-5 from the first edition from this book. Deadline: wednesday, February 23, 2005.
  2. Postscript file exercise set 2. Pdf file exercise set 2. Postscript file exercise set 2 (english). Pdf file exercise set 2 (english). Deadline: wednesday, March 2, 2005.
  3. Exercises 26-1 and 26-5 from Introduction to Algorithms. Deadline: wednesday, March 9, 2005.
  4. Postscript file exercise set 4. Pdf file exercise set 4. Deadline: wednesday, March 16, 2005.
  5. Postscript file exercise set 5. Pdf file exercise set 5. Deadline: wednesday, March 30, 2005.
  6. Postscript file exercise set 6. Pdf file exercise set 6. Deadline: wednesday, april 6, 2005.
  7. Postscript file exercise set 7. Pdf file exercise set 7. Deadline: wednesday, april 13, 2005.
  8. Postscript file exercise set 8. Pdf file exercise set 8. Deadline: wednesday, april 20, 2005.

Course overview

There will be two lectures of two hours per week (see schedule.)

During the course, 8 sets of excercise sets are handed out to the students.

Grading

The exams and excercises should be at least 4 for a sufficient end note. The end note then is the average of the note for the first test, the note for

Course overview

There will be two lectures of two hours per week (see schedule.)

During the course, 8 sets of excercise sets are handed out to the students.

Grading

The exams and excercises should be at least 4 for a sufficient end note. The end note then is the 0.3 times the note for the first test, plus 0.3 times the note for the second test, plus 0.4 times the average of the notes of the exercises, i.e., 0.3*T1+0.3*T2+0.4*E.

Additional exams

In case the end note is not sufficient, you can do in some cases an addtional exam. You can redo an exam, when (Note that you cannot redo exams which you passed.)

You can do one additional exercise set, whose note then replaces the lowest note obtained for one of the eight exercise sets.

Powerpoint files

  1. Shortest paths.
  2. Traveling Salesman Problem.
  3. Powerpoint file Maximum flow. (Version 2005b.)
  4. Powerpoint file Minimum cost flow. (Version 2005.)
  5. Powerpoint file Matching. (Version 2005a, revised February 28, 2005.)
  6. Powerpoint file Stable Marriage. (New file: March 1, 2005.)
  7. Graph Isomorphism Powerpoint file. (Version 2005.) PDF-file of text on graph isomorphism. (In Dutch.)
  8. Power point file Planarity.
  9. Power point file Graph drawing: force directed methods. (New: March 15, 2005.)
  10. Power point file Treewidth. (Version March 29, 2005.)
  11. Power point file Vertex cover and related problems (Version April 28, 2005.).
  12. Power point file Coloring.
  13. Power point file Steiner Trees. (Version April 14, 2005.)
  14. Power point file Fixed Parameter Tractability. (Version April 14, 2005.)

Literature

The following are recommended sources for this course. It is not necessary to purchase these books for the course.

Language

In case all participants of the course are Dutch-speaking, the course will be given in Dutch; in all other cases, the course will be given in English.

Links for references

Traveling salesmen problem

Graph coloring

Email me if you know more relevant links for the course!

Other links


Last modified: June 28, 2005