Status: May 11, 2005

Final status: no updates are planned

Grades has been submitted to the registrar office

Instructor:

Schedule:

Contents:

This is an advanced course on algorithms and data structures that concentrates on the topics in algorithmic theory of graphs and digraphs.

In the course we will discuss first briefly some basic facts from graph theory and present applications of graphs (in real life and in communication networks and data structures).
Then we will discuss 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, 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 is devoted to the issue of the analysis of graph algorithms. Therefore, we will present quite a few proofs of algorithms correctness (for the instructor, personally, an algorithm without any arguments showing its correctness is useless). We will also analyze some fundamental properties of graphs.

Prerequisite: CIS 610 or the permission of the instructor

Grading and Policies:

• Grading will be based on 4 problems sets, an in-class midterm, and a final.

• Four homework assignments will be handled out. Each homework is worth 67 points. One homework with the lowest grade will be dropped from grade consideration. Thus, the homework assignments contribute a total of at most 200 points towards the final grade. Homework assignments will be posted on the course Web-page http://web.njit.edu/~czumaj/TEACHING/CIS665-S05.html both in postscript and in Adobe Acrobat format.
  • All homework assignments are in the form of problem sets (no programming assignments).
  • Homework assignments are due at the start of class on their due date. They can be submitted either per email to czumaj@cis.njit.edu or be handed in a hard-copy at the beginning of the class. Handwritten or typed solutions will be accepted.
  • No later solutions will be taken into consideration!
  • If the homework is to be submitted per email, it must be in one of the following formats: postscript file (preferable), pdf-file (2nd preference), ASCII text, Word format.
  • Solutions must be readable (especially handwriting!!!), concise and complete.
  • Show your work, as partial credit will be given. You will be graded not only for the correctness and efficiency of your answers, but also on your clarity. Be neat.
  • Bonus points will be awarded for answers that are particularly clever, simple, or efficient.
  • Each time you must design an algorithm, try to design it as efficient as possible. The faster algorithm you will describe the better grade you will get.
  • Unless it is stated otherwise, each algorithm described must be provided with a full analysis of its correctness and its running-time.
  • The work you turn in must be your own personal work, composed and written by you. If you discuss a problem with a fellow student, you must mention this clearly in your homework (name the fellow student before the solution of the problem in question). Your work will then be compared to the other student's work to verify that your solution was written by you and reflect your own personal effort. If you don't report it, it will be considered a violation of the course rules, as described in the General Collaboration Policy section. (Collaboration of this kind is not allowed in the midterm and final exams.)
  • Cheating: it is surprisingly easy to detect when students are not doing their own work. Working with others on the assignments does not mean dividing the problems among you, and then swapping the answers.
  
  
• The midterm exam is worth 150 points.
  It took place during the class on March 10, 2005.
• The final exam took place on May 5 from 6:00pm till 8:50pm in room FMH 409 (the same where normal lecture take place). It was worth 250 points. The final exam was cumulative (that is, all course material will be examined) and open-textbook and open class-notes only.

  Sample self-test problems for preparation for the final (file in postscript format). Some of these questions are easy but some are hard/time consuming.

Homework Assignments and Exams:

• Homework 1 was due the class on February 17.
  • Sample solutions to Homework 1 are now available (postscript file too).
  • For students who don't have Acrobat reader or any program to read PDF files:
                    Click that icon to instal Acrobat reader
• Homework 2 was due the class on March 3, 2005 (postscript file with Homework 2).
  • Sample solutions to Homework 2 are now available (postscript file too).
• Homework 3 was due the class on April 14, 2005 (postscript file with Homework 3).
  • Sample solutions to Homework 3 are now available (postscript file too). [These files were updated on April 26, 2005 - another simple solution of Problem 4 was added.]

  Grades after Homework 3 are available.
           Grading of Homework 3 was by taking 3 best solutions (out of 4 problems in Homework 3) and giving each 1/3 of the score.
           Check with the instructor if you have any compliants or comments.

• Homework 4 was due the class on April 28, 2005 (postscript file with Homework 4).

           Grading of Homework 4 was by taking 3 best solutions (out of 4 problems in Homework 4) and giving each 1/3 of the score.

Specific contents:

1. (1/20/05)
   • Discussion of the syllabus, requirements, topics to be covered, textbooks.
   • What are graphs: definitions of undirected graphs, directed graphs, weighted graphs.
   • Graph representation:
     • graphical representation (how graphs can be drawn on the board),
     • computer representation: adjacency matrix and adjacency lists.
   • Trees, forests, and their basic properties.
   • Further definitions: paths, cycles, parallel edges, self-loops, connectivity, degree in undirected graphs, in-degree and out-degree in directed graphs.
   • Basic proof techniques: proofs by induction and proofs by contradiction.
   • Suggested reading: Chapters 22.1, B4, B5 in the textbook.

2. (1/27/05)
   • Basic proof techniques, continuation (we proved using a few different techniques that every tree with n vertices has n-1 edges)
   • Generic graph traversal algorithm and its analysis.
     • The running time is O(n + m) in the adjacency lists model, under the assumption that some basic operations can be performed in constant time.
   • Breadth-first search algorithm.
     • Using breadth-first search to find shortest paths (in the sense of the number of edges) from a source vertex to all other vertices.
   • Depth-first search algorithm.
     • Basic properties, including properties of dfs-numbering and finishing times.
     • Partition of edges into tree-edges, back edges, forward edges, and cross edges (for undirected graphs we have only tree and back edges).
   • Topological sorting.
     • So far only the definition of the problem and brief (and informal) discussion of some basic properties.
   • Suggested reading: Chapters 22.1, 22.2 in the textbook.

3. (2/03/05)
   • Topological sorting.
     • Basic properties (including: topological ordering exists if and only if the graph is acyclic).
     • Basic algorithm for topological sort:
       • take a vertex of indegree 0 and assign the lowest number to; remove all incident edges, and repeat the numbering for the remaining graph recursively
       • using data structures to implement the algorithm in time O(n + m) for graphs represented by adjacency lists
     • Application of DFS: directed graph is acyclic if and only if after a run of DFS no back edges is created.
     • Application of DFS: finishing times give topological ordering - O(n+m) - time algorithm for graphs represented by adjacency lists.
   • Lower bound for topological sorting in adjacency matrix representation:
     • In a directed graph G=(V,E) with n vertices and m edges represented by an adjacency matrix, every algorithm for topological sorting requires time W(n²). [This bound holds even if m is very small, much smaller than n².]
   • Not all problems require time W(n²) for graphs represented by an adjacency matrix and W(n + m) for graphs represented by adjacency lists:
     • A problem that can be solved in O(n)-time in the adjacancy list model: find a cycle in an undirected graph, if there is any.
     • A problem that can be solved in O(n)-time in the adjacancy matrix model: find a sink in a directed graph, if there is any. (A sink is a vertex with in-degree n-1 and out-degree 0.)
   • Suggested reading: Chapters 22.3, 22.4 in the textbook. For the lower bound for topological sorting in adjacency matrix representation see Theorem 2 (page 7) in the part of the book by K. Mehlhorn

4. (2/10/05)
   • Discussion on solving problems in Homework 1.
   • Finding biconnected components.
     • Basic properties of biconnected graphs and biconnected components.
     • DFS-based algorithm for finding all articulation points - algorithms builds a DFS-tree and then:
       • leaves are no articulation points,
       • root is an articulation iff it has more than one child, and
       • an internal (non-leaf, non-root) vertex is an articulation iff some property of function low fails.
   • Finding strongly connected components... two runs of DFS are enough to check if a graph is strongly connected:
     • Run DFS and compute the finishing time for every vertex.
     • Run DFS for the input graph with reversed directions of the edges; each call to DFS considers the vertices in order of decreasing finishing times.
   • Suggested reading: Chapter 22.5 and Problem 22-1 (pages 558-559) in the textbook. Article by Mount on biconnectivy testing.

5. (2/17/05)
   • Discussion on solving problems in Homework 1.
   • Testing bipartitnes of a graph.
     • Bipartitnes is a special case of the coloring problem: graph is bipartite iff it's 2-colorable.
       • A k-coloring of a graph is a coloring of the vertices of the graph so that no edge is monochromatic (the endpoints of every edge are of different colors)
       • Testing if a graph is 3-colorable is NP-complete.
     • O(n+m)-time algorithm that determines if a given graph is bipartite (2-colorable) and if it is, then it finds the partition (2-coloring) of the vertices.
     • Brief discussion of k-edge-coloring (assigning of k colors to the edges of the graph so that no two adjacent edges are of the same color)
       • A graph with maximum degree D cannot be k-edge colored with k < D
       • Every graph with maximum degree D has a (D+1)-edge coloring (Vizing's theorem)
       • Testing if a graph has a D-edge coloring is NP-complete
   • Eulerian tours/cycles and Hamiltonian tours/cycles.
     • Determining if a graph has a Hamiltonian tour or a cycle is NP-complete.
     • Determining if a graph has an Eulerian tour or a cycle is easy.
     • O(n + m)-time algorithm for finidng an Eulerian tour or a cycle in a graph.
   • Minimum spanning trees
     • Basic definitions
     • Meta-algorithm for finding a minimum spanning tree and its basic properties
   • Suggested reading: Chapter 23.1 and Problem 22-3 in the textbook.

6. (2/24/05)
   • Discussion of problems from Homework 1
   • Efficient algorithm for the MST problem in graphs with edge weights in {1,2,...,W}
     • Reducing the problem to finding connected components (or spanning trees) in the subgraphs induced by edge weights {1,...,s} for all s=1,2,...W.
     • Running-time O(W (n+m))
     • A simple formula for the weight of the MST:
       • MST = n - W + cc⁽¹⁾ + cc⁽²⁾ + ... + cc^(W-1),
       where cc^(s) denotes the number of connected components in the subgraph induced by edge weights {1,...,s}.
   • Due to the inclemental weather conditions, the lecture was only one hour long.

7. (3/3/05)
   • Discussion about solutions for problems from Homework 2
   • Analysis of Meta-algorithm for the Minimum Spanning Tree problem: formal proof of its correctness.
   • Kruskal algorithm as an implementation of Meta-algorithm.
   • Union-Find data structure and an efficient implementation of Kruskal algorithm
     • Union-Find algorithm using trees, Find with path compression, and Union with weight (rank) or height rule - O(m a(n,m))-time.
     • Kruskal algorithm can be implemented to run in time O(m log(m)).
   • Prim's algorithm as an implementation of Meta-algorithm.
     • An O(n²)-time implementation of Prim's algorithm. (Later we will discuss faster implementations.)
   • Suggested reading: Chapter 23 in the textbook and pages 57 - 61 in the textbook by K. Mehlhorn.

8. (3/10/05)
   • Midterm exam

     Results

     Sample solutions to all the problems (Solutions in postscript format are available here)

9. (3/24/05)
   • Detailed discussion of midterm problems (sample solutions have been posted)
   • Minimum spanning tree problem - further discussion
   • Prim's algorithm and its efficient implementations
     • Prim's algorithm can be implemented in time O(n+m) + the time needed to perform the following operations (in priority queue):
       • n-1 operations ExtractMin and
       • O(m) operations DecreaseKey.
     • Using "naive" implelemnation of priority queues using arrays, one can implement each ExtractMin operation in time O(n) and each DecreseKey operation in time O(1).
       • An O(m + n²)-time implementation of Prim's algorithm.
       • Optimal implementation for dense graphs (graphs with m = Q(n²)).
     • Using heap implementation of priority queue, each of ExtractMin and DecreaseKey can be performed in time O(log n).
       • An O(m log m)-time implementation of Prim's algorithm.
     • Fibonacci heaps (see the textbook for more information) can be used to perform each ExtractMin operation in time O(log n) and each DecreseKey operation in time O(1).
       • An O(m + n log n)-time implementation of Prim's algorithm.
   • Round robin algorithm:
     • Basic analysis leading to an O(m log(m))-time implementation
       • We partition the algorithm into phases;
       • each phase can be implemented in O(m) time,
       • there are at most O(log n) phases.
     • Linear-time implementation for planar graphs.
       • (This implementation uses the property that in every simple planar graph we have m < 3n; this will be proven formally later in the class.)
       • After finishing any single phase, we contract the graph by contracting all connected components into a single vertex.
       • Running time in phase i is O(n / 2ⁱ) -> implies the overall running-time O(n)
   • Suggested reading: Chapter 23 in the textbook and the textbook by K. Mehlhorn, pages 57-61 (especially his discussion on Round Robin algorithm).

10. (3/31/05)
    • Discussing Homework 3.
    • Once again, discussing details of Round robin algorithm:
      • Basic analysis leading to an O(m log(m))-time implementation
        • We partition the algorithm into phases;
        • each phase can be implemented in O(m) time,
        • there are at most O(log n) phases.
      • Linear-time implementation for planar graphs.
        • (This implementation uses the property that in every simple planar graph we have m < 3n; this will be proven formally later in the class.)
        • After finishing any single phase, we contract the graph by contracting all connected components into a single vertex.
        • Running time in phase i is O(n / 2ⁱ) -> implies the overall running-time O(n)
    • Discussing the problem of finding a spanning tree with the heaviest lightest edge - this problem can be reduced to the problem of finding a maximum spanning tree (a maxium weight spanning tree has the heaviest lightest edge), which in turns, is equivalent to the minimum spanning tree problem.
    • Introduction to shortest path problems.
    • Single-source shortest path problem.
    • Bellman-Ford algorithm achieving the running time of O(nm).
    • Suggested reading: Pages 57 - 61 in the textbook by K. Mehlhorn and Chapters 24 and 25 in the textbook.

11. (4/7/05)
    • Discussing Homework 3 (once again).
    • Bellman-Ford algorithm for the single-source shortest path problem and its extension to the linear (i.e. O(n+m))-time algorithm for directed acyclic graphs.
    • Dijkstra algorithm for the single-source shortest path problem:
      • Requires all weights to be non-negative (it's incorrect when some edges are allowed to be negative, even when there is no negative-weight cycle).
      • Dynamic programming approach.
      • Using standard priority queues - O((n+m) log n) running-time.
      • Using Fibonacci heaps - the running time of O(n log n + m), which is almost optimal.
    • Matrix multiplication and solving the all pairs shortest path problem:
      • Matrix multiplication (in a closed semiring) leads to an O(n⁴)-time algorithm for the all pairs shortest path problem.
      • Easy improvement using doubling - gives an O(n³ log(n))-time algorithm.
    • Floyd-Warhshall algorithm: another dynamic programming leads to a very simple O(n³)-time algorithm.
    • Finding shortest paths in a tree.
    • Maximal and maximum matching problem.
    • Perfect matching in graphs.
    • Problem of finding a maximum matching in 2^k-regular bipartite graphs is "easy" - can be solved in time O(m).
    • Suggested reading: Chapter 25 in the textbook.
      Slides about shortest path problems that accompany the book »Data Structures and Algorithms in C++« by Michael T. Goodrich, Roberto Tamassia, and David M. Mount, John Wiley & Sons, Inc. 2003 (see that page for slides accompanying the book in Java).

12. (4/14/05)
    • Discussing solutions to Homework 3.
    • Maximum matchings in bipartite graphs: Introduction to the theory
      • Alternating path, augmenting paths, and Berge's theorem (with a detailed proof)
      • Berge's theorem: Let G be a bipartite graph. Then, a matching M is maximum if and only if there is no augmenting path in G wrt. M.
    • Hall's theorem, its detailed proof, and its application to the proof that every r-regular bipartite graph has a perfect matching
      • Hall's theorem: A bipartite graph G = (L,R,E) has a perfect matching if and only if for every subset X of L, |X| ≤ |N(X)|
      • Hall's theorem is "non-algorithmic" - its direct application leads to an exponential-time algorithm for deciding if a bipartite graph has a perfect matching.
    • An efficient algorithm for finding a perfect matching in an r-regular graph (running-time O(m log m)).
    • König theorem (in every bipartite graph, the size of maximum matching is the same as the size of minimum vertex cover)
    • A linear-time algorithm for finding a perfect matching in trees (and its relation to the problem of finding a minimum vertex cover in a tree).
    • Reading: Chapter 5 from the book of Bondy and Murty (about matching - broken link has been fixed) and paper by Noga Alon (describing the algorithm for finding a perfect matching in bipartite regular graphs in time O(m log m)).

13. (4/21/05)
    • Maximum matching in bipartite graphs.
    • Augmenting paths and a simple algorithm for finding a maximum matching in bipartite graphs:
      • Repeat until no augmenting path: find an augmenting path and augment the current matching.
      • Finding if an augmenting path exists can be done in time O(n+m).
      • The running time is O(n(n+m)).
    • An improvement (Hopcroft-Karp algorithm) by finding a maximum set of shortest vertex-disjoint augmenting paths in each step.
      • The running time is O(n^0.5 (n+m)).
      • For the detailed analysis, see (file is in postscript format)
    • Flows in networks (directed graphs with capacities) and the maximum-flow problem.
      • Application to the maximum matching problem in bipartite graphs.
      • Application to the problem of computing the edge-connectivity of an undirected graph.
      • Augmenting path and residual networks.
      • An algorithm (due to Ford-Fulkerson) for the max-flow problem: until possible, find an augmenting path P and augment the flow wrt ot P.
      • Edmonds-Karp algorithm: Ford-Fulkerson algorithm in which a shortest path is always selected (achieves the running-time of O(n m²)).
      • If all capacities are integers, then the max-flow problem can be solved in time O(|f^*| m), where |f^*| denotes the value of the optimal flow.
      • Min-cut max-flow theorem.
    • Reading: Textbook, Chapter 26 and Problem 26-7 (pages 696-697), and Chapter 5 from the book of Bondy and Murty (about matching - broken link has been fixed).

14. (4/28/05) Last day of classes
    • Planar graphs
      • Euler's formula (in every simple planar graph: n + f = m + 1 + connected components) and it applications
        • Proof (by induction) of the Euler's formula.
        • Poof of the standard fact that every planar (simple) graph has the number of edges upper bounded by 3n-6.
        • Proof that every planar (simple) graph has at least one vertex with degree at most 5.
      • Coloring planar graphs:
        • Application of the Euler formula (in particular fact that a planar graph has at least one vertex with degree at most 5) to design an O(n)-time algorithm that color any planar graph using 6 colors.
        • The Four-Color Theorem: in fact every planar graph can be 4-colored.
      • Planar Separator Theorem and its applications (maximum matching in planar graphs)
    • Approximation algorithms
      • Approximation algorithms for the TSP problem:
        • 2-approximation algorithm based on doubling MST and shortcuttings.
        • Christofides algorithm: achieving 1.5-approximation by taking MST and a matching on vertices of odd-degree in MST.
      • Approximation algorithm for the minimum-vertex cover problem:
        • Simple greedy-like method gives a 2-approximation.
    • Discussion about the final exam.
    • Reading: Textbook, Chapters 26, 35, Chapter 9 from the book of Bondy and Murty (about planar graphs - broken link has been fixed) and Mehlhorn book (especially Chapters 4.9 and 4.10).

FINAL exam:     6:00 pm - 8:50 pm, Thursday, May 5, 2005, Room FMH 409

• Sample self-test problems for preparation for the final (file in postscript format).

• Material covered: everything discussed in the class
• Grades have been submitted directy to the registrar - they won't be posted on the course web page. Discussion of the grading can be handled on the individual basis (but be aware that the instructor will be away in the second half of May).

References:

Textbook:

There is a one main textbook which covers a large part of the material discussed in the class. This is not a perfect textbook and the instructor will use it mostly for references and as the place where students may find more detailed expositions of the material presented in the class.

• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: »Introduction to Algorithms«, The MIT Press 2001, 2nd edition (though the 1st edition is also fine). Mostly Part VI (Chapters 22 - 26) will be covered (plus additionally parts from Chapter 35 on Approximation Algorithms)
  

• Optional Textbooks:
  
  
  • R. Sedgewick: »Algorithms in C++: Part V. Graph Algorithms «, Addison-Wesley Pub Co; ISBN: 0201361183, 3rd edition (December 27, 2001).
    Eventually, you can also use the same book in C.

  • Bernhard Korte and Jens Vygen: »Combinatorial Optimization. Theory and Algorithms«, Volume 21 in the series Algorithms and Combinatorics, Springer-Verlag, ISBN: 3540431543, 2nd edition (May 2002).

  • Vijay V. Vazirani: »Approximation Algorithms«, Springer-Verlag, 2001.

  • J. A. Bondy and U. S. R. Morty: »Graph Theory with Applications«, North-Holland, 1976.

Links relevant to the course:

• A very good description of an DFS-based algorithm for biconnectivity is available from an old lecture notes of Prof. Mount (file in postscript format)
  
  
• Prof. Mehlhorn made parts of his book on algorithms available on his web-page. Look at pages 57-61 in the postscript file available there for a good description of MST algorithms. (But in the instructor's opinion also the handbooks have pretty good description of MST algorithms.)
  Actually, other parts from the text of Prof. Mehlhorn can be found very useful too.
  
  
• See Section 4.10 (pages 89-125) from Mehlhorn's book for a good description of algorithms on planar graphs. Theorem 7 (page 118) and Corollary 1 (page 123) are Planar Separator Theorems. Text following these theorems contains some examples of their use.
  
  Additionally, I put copies of three pages from the original article due to Lipton and Tarjan about applications of the Planar Separator Theorem: page 1, page 2, and page 3. This text contains also a brief description of the algorithm for the matching problem in planar graphs.
  
  

More advanced links (perhaps will be useful in later lectures, though they perhaps won't be of any use ...)

• »Lecture Notes on Approximation Algorithms« by David P. Williamson, 1998.
  
• Postscript file (gzipped) of »Lecture Notes on Approximation Algorithms - Volume I« by Rajeev Motwani, Stanford (10 years old ... but still quite OK)
  
• »Lecture Notes on Approximation Algorithms for Network Problems« by J.Cheriyan and R.Ravi
  
• Approximation algorithms - a collection of Bin Ma.