Final status: July 17, 2004

This is the final form of that web page. No updates are planned.

NEW! PhD Qualifying Exam Summer 2004

NEW! Course on Advanced Algorithms

 

CIS 665: »Algorithmic Graph Theory«

Spring 2004

Section 102 (3 credits)
  

Instructor:

Prof. Dr. Artur Czumaj

Office:  4103 (GITC Building, 4th floor)
Tel.:   (973) 596-3369
Fax:   (973) 596-5777
EMail:  czumaj@cis.njit.edu
WWW:  http://www.cis.njit.edu/~czumaj/

Schedule:

Class hours  Tuesday  6:00pm - 9:05pm  KUPF 104


Office Hours:		   Tuesday   4:00 pm - 5:25 pm
    Friday   11:30 am - 12:55 pm

By special appointment:		   Wednesday   12:15 pm - 12:55 pm

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-S04.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 will be worth 150 points.
    It took place during the class on March 2, 2004.
  • The final exam will be worth 250 points. The final exam will be cumulative (that is, all course material will be examined) and most probably it will be open-textbook and open class-notes only.

Homework Assignments and Exams:

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 ...)

Specific contents:

  1. (1/20/04)
    • 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/04)
    • Basic proof techniques, continuation
      • Proofs of some basic trees properties
      • Proofs of the following two simple results:
        • every tree with at least one edge has at least one vertex with degree 1
        • every directed acyclic graph has at least one vertex with in-degree 0 (source) and at least one vertex with out-degree 0 (sink)
    • Generic graph traversal algorithm and its analysis (in particular, its 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 (we were supposed to attempt to prove in all details the correctness of the BFS algorithm for this problem; but due to inclement weather the class ended earlier and students were asked to read the proof and detailed arguments from the textbook).
    • Suggested reading: Chapters 22.1, 22.2 in the textbook.

  3. (2/03/04)
    • 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.
    • Topological sort.
      • Basic properties (including: topological ordering exists if and only if the graph is acyclic).
      • Basic algorithm for topological sort.
      • 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.
    • Suggested reading: Chapters 22.2 - 22.4 in the textbook.

  4. (2/10/04)
    • Long discussion about Homework 1.
    • Lower bound for topological sorting in adjacency matrix representation:
      • In a graph G=(V,E) with n vertices and m edges represented by an adjacency matrix, every algorithm for topological sorting requires time W(n2).
    • A problem that can be solved in O(n)-time in the adjacancy matrix model: verify if a directed graph G contains a vertex with in-degree n-1 and out-degree 0.
    • Finding biconnected components (blocks) and 2-edge-connected components.
      • Basic properties of biconnected graphs and blocks (biconnected components).
      • Brief description of the DFS-based algorithm for finding all articulation points.
    • Suggested reading: Chapter 22 in the textbook. Article by Mount on biconnectivy testing.

  5. (2/17/04)
    • Finding biconnected components (blocks): continuation.
      • DFS-based algorithm - algorithms builds a DFS-tree and then: leafs 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.
      • Era decomposition and open ear decomposition: cyclic properties of 2-edge connected and biconnected graphs.
      • Brief discussion about basic properties of DFS-based algorithms for detetmining 2-edge connected components of a graph (no details has been said).
    • Finding strongly connected components
      • ... two runs of DFS aqre enough to check if a graph is strongly connected.
      • Reading assignment: read in the textbook how to find all strongly connected components using two calls to DFS.
    • 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.
    • Testing bipartitnes of a graph.
      • Bipartitnes is a special case of the coloring problem: graph is bipartite iff it's 2-colorable.
        • 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.
    • Suggested reading: Chapter 22 in the textbook. Article by Mount on biconnectivy testing.

  6. (2/24/04)
    • Brief discussion about Homework 2 and Midterm
    • Discussion about Homework 1
      • Quite detailed discussion about Problem 1 (not all detailes presented).
      • Discussion about Problem 2.
    • Algorithms for trees.
      • Many hard problems can be solved in polynomial-time when the input graph is undirected and acyclic (that is, is a tree).
      • Finding lowest common ancestors of a set of marked nodes in O(n) time.
      • Computing the number of descendants in O(n) time.
      • Independent sets and maximum independent sets - NP-hard problems and even very hard to approximate.
      • Computing the size of maximum independent set in a tree in O(n) time.
      • Computing the maximum-weight independent set in a tree in O(n) time.

  7. (3/2/04)
    • Midterm exam.

  8. (3/9/04)
    • Discussion of Homework 1, Homework 2, and Midterm Exam.
    • Minimum spanning trees - basic definitions.
    • Efficient algorithm for the MST problem in graphs with edge weights in {1,2,...,k}
      • Reducing the problem to finding connected components (or spanning trees) in the subgraphs induced by edge weights {1,...,s} for all s=1,2,...k.
      • Running-time O(k (n+m))
      • A simple formula for the weight of the MST:
        • MST = n - k + cc(1) + cc(2) + ... + cc(k-1),
        where cc(s) denotes the number of connected components in the subgraph induced by edge weights {1,...,s}.
    • Meta-algorithm for finding minimum spanning trees.
    • Suggested reading: Chapter 23 in the textbook and pages 57 - 61 in the textbook by K. Mehlhorn (postscript file available there).

  9. (3/23/04)
    • Minimum spanning trees - meta-algorithm and its basic properties.
    • Analysis of Meta-algorithm: 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 or hegight rule - O(m alpha(m))-time.
      • Kruskal algorithm can be implemented to run in time O(m log(m)).
      • If all the edge weights are integers in the interval {1, ..., nk}, where k is a constant (say, k=100), then Kruskal algorithm can be implemented to run in time O(m alpha(m)), or in general, in time O(log(k) m + m alpha(m)).
    • Introduction to Prim's algorithm.
    • Suggested reading: Chapter 23 in the textbook and pages 57 - 61 in the textbook by K. Mehlhorn (postscript file available there).

  10. (3/30/04)
    • Short discussion on Homework 3.
    • 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 heap implementation of priority queue, each of ExtractMin and O(m) operations DecreaseKey can be performed in time O(log n).
        • An O(m log m)-time implementation of Prim's algorithm.
      • 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 + n2)-time implementation of Prim's algorithm.
        • Optimal implementation for dense graphs (graphs with m = Q(n2)).
      • Fibonacci heaps 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 were supposed to talk about an improved implementation that achieves the running time of O(m log log(m)) (see the Mehlhorn book for more details) - but we skipped it.
      • 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.)
    • Introduction to shortest path problems.
    • Single-source shortest path problem.
    • Bellman-Ford algorithm achieving the running time of O(nm).
    • (Not finished yet:) Efficient (optimal) algorithm for directed acyclic graphs - "variant" of Bellman-Ford algorithm with the running time of O(n+m).

  11. (4/6/04)
    • Discussion about Homework 3 problems.
    • 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) ... almost optimal.
    • Matrix multiplication and solving the all pairs shortest path problem:
      • Matrix multiplication in closed semiring {0,1} leads to an O(n4)-time algorithm for the all pairs shortest path problem.
      • Easy improvement using doubling - gives an O(n3 log(n))-time algorithm.
    • Floyd-Warhshall algorithm: another dynamic programming leads to a very simple O(n3)-time algorithm.
    • Maximal and maximum matching problem.
    • Perfect matching in graphs.
    • Problem of finding a maximum matching in 2k-regular bipartite graphs is "easy" - can be solved in time O(m).

  12. (4/13/04)
    • Problem of finding a maximum matching in 2k-regular bipartite graphs is "easy" - can be solved in time O(m). Actually, every 2k-regular bipartite graph has a perfect matching; even more, for every k, every k-regular bipartite graph has a perfect matching.
    • A linear-time algorithm for finding a maximum-size matching in trees.
      • Recursive approach (kind of a dynamic programming approach).
    • Hall's theorem, and its application to the proof that every k-regular bipartite graph has a perfect matching.
      • Hall's theorem is "non-algorithmic" - its direct application leads to an exponential-time algorithm.
    • Maximum matchings in bipartite graphs: Introduction to the theory.
      • Augmenting paths.
      • A matching is maximum if and only if there is no augmenting path.
    • 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(n0.5 (n+m)).
    • Reading: Textbook, Chapter 26 and Problem 26-7 (pages 696-697), and Chapter 5 from the book of Bondy and Murty (about matching).

  13. (4/20/04)
    • Discussion about Homework 4.
    • Proof of Hall's theorem.
    • More details of the Hopcroft-Karp algorithm.
    • Koning's theorem and its application to finding a minimum vertex cover and maximum independent set in bipartite graphs.
    • 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.
    • Introduction to planar graphs:
      • Planar Separator Theorem and its applications (maximum matching and maximum independent set problems)
      • Euler formula and it applications (a proof of the standard fact that every planar (simple) graph has the number of edges upper bounded by 3n-6)
    • Reading: Textbook, Chapter 26, Chapter 5 from the book of Bondy and Murty (about matching), Chapter 9 from the book of Bondy and Murty (about planar graphs), and Mehlhorn book (especially Chapters 4.9 and 4.10).

  14. (4/27/04) Last day of classes
    • Discussion about Homework 4 and about grades for Homework 3.
    • Brief discussion about the max-flow problem:
      • Augmenting path and residual networks.
      • An algorithm (due to Ford-Fulkerson) for the max-flow problem.
      • Edmonds-Karp algorithm: Ford-Fulkerson algorithm in which a shortest path is always selected (achieves the running-time of O(n m2)).
      • 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.
      • Max-flow min-cut theorem.
    • Euler formula (in every simple planar graph: n + f = m + 1 + connected components) and it applications:
      • Proof of the Euler formula (by induction).
      • Proof of a property 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 graphs and their duals.
    • 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), and Mehlhorn book (especially Chapters 4.9 and 4.10).

6:00 pm - 9:00 pm, Tuesday, May 11, 2004

 

Artur Czumaj, FINAL STATUS - July 17, 2004