Status: July 1, 2000

Instructor:

Schedule:

Contents:

In this course we will cover foundations of the algorithmic theory of graphs and digraphs.
We will discuss first some basic facts from graph theory and discuss applications of graphs (in real life and in communication networks and data structures).
Then we will present efficient algorithms for most basic problems on graphs: framework of graph traversing (depth-first search and breadth-first search), minimum spanning trees, shortest paths problems, matching and assignment problem, and maximum flow problem.
In the last part of the course we will discuss some more advanced topics in algorithmic graph theory: planar graphs and planarity testing, connectivity problems, theory of graph minors (tentatively), and approximation graph algorithms.

In this course the main emphasis is on understanding algorithms on graphs. Much of the material covered will be presented on a high level and we will try to avoid going into technical implementations details. A very important part of this course will be devoted to the issue of the analysis of graph algorithms. Therefore, we will present quite a few proofs of algorithms' correctness (for me personally - algorithm without any arguments showing that it is correct is useless). We will also analyze some foundamental properties of graphs.

Course info:

• If You've found this course interesting and You're still looking for a topic of your PhD - You can make Your PhD in a topic related to algorithms or graph algorithms. All of You are very welcome. If You have interest then please contact me via email czumaj@cis.njit.edu.

• Final exam took place on Friday, May 5, 2000, at 8:30 am in Culm Lect 1. It was open textbook and it was worth 250 points. The final exam was cumulative and covered all course material.

  For those willing complain for final grades - the grades have been made not only on the basis of the points from all the exams and homeworks.

• Midterm exam (close textbook) took place on March 7, 2000.

• The assignments included periodic problem sets and one programming assignment.
  Five problem sets were handled out. Each problem set was worth 50 points. Because of some delay, problems from the 5th problem set were included in Problem Set 3 and Problem Set 4.
  A single programming assignment was handled out. The programming assignment was worth 50 points and it required implemention either in C or in C++.
  The two homeworks (out of the five problem sets and one programming assignment) with the lowest grade were dropped from grade consideration. Thus, the homeworks contributed a total of at most 200 points towards the final grade.

  Assignments
  
  

  1. Problem Set 1 was due (8:30 am) February 22, 2000.
     
     
  2. Problem Set 2 was due (1:00 pm) March 14, 2000.
     
     
  3. Programming Assignment 1 was due April 1 (8:00 am), 2000.
     
     
  4. Problem Set 3 was due (8:30 am) April 11, 2000.
     
     
  5. Problem Set 4 was due (1:30 pm) May 2, 2000.
     
     

• T.H. Cormen, C.E. Leiserson, and R.L. Rivest: »Introduction to Algorithms«, The MIT Press/McGraw Hill, 1990
• Large part of the course followed chapters 5 and 23-27 from the main textbook.
• For a part of the course dealing with planar graphs I followed the book of Mehlhorn "Data Structures and Algorithm. Volume II: Graph Algorithms and NP-Completness."
• Presentation of the Separator Theorem was based on the original article due to Lipton and Tarjan ("Applications of a planar separator theorem," SIAM Journal on Computing, Vol. 9, No. 3, pages 615-627, August 1980).
• In my presentation of approximation algorithms I partly used Chapter 37 from the main textbook.
• Although I have introduced hypergraphs in the class, there was no question about hypergraphs on the final exam.
• Good description of vertex cover and set cover problem/algorithms is in the lecture notes of Williamson distributed in the class.
  Actually, also the main textbook (Chapter 37) contains a reasonable good description of these problems.
  Notice however, that in these references the authors didn't use (explicitly) hypergraphs.

Info on Qualifying PhD Exam in Summer 2000:

The Qualifying PhD Exam in Summer 2000 covered the following material (it is a subset of the material taught in CIS 665 in Spring 2000, see above):

• From the main textbook "Introduction to Algorithms" by T.H. Cormen, C.E. Leiserson, and R.L. Rivest, and published by The MIT Press/McGraw Hill, 1990:
  • Chapter 5.4 Graphs
  • Part VI Graph Algorithms (Chapters 23-27) (one may skip Chapters 23.5, 25.5, 27.4, 27.5)
  • Chapter 37 (37.1, 37.2, and 37.3) on approximation algorithms
• Chapter 4.10 from the book "Data Structures and Algorithms. Volume II: Graph Algorithms and NP-Completness" by K. Mehlhorn