FINAL STATUS: July 6, 2003

This is the final version of the file (not to be updated in the future)

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

Information about Qualifying Exam in Summer 2003

Grading and Policies:

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

• Five homework assignments will be handled out. Each homework is worth 50 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-S03.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 took place on March 25, 2003.
  Detailed information about the midterm.
  Sample test problems for midterm and solutions to some/most of them (might not work in Unix - sorry).
  The midterm exam was worth 150 points.
  
  Grades (include Homework 1, 2 and Midterm)
  (Students names are sorted according to the last 3 digits of their IDs. The instructor doesn't have the ID of one student and since two students have the same 3 last digits of their ID, their initials has been put to distinguish between them.)

• The final exam took place on the finals week, on Tuesday, May 13, 6-9pm, in TIER 108.
  The final exam was worth 250 points. The final exam was cumulative (that is, all course material were examined) and was be open-textbook and open class-notes only.
  Detailed information about topics covered in the final.
  Sample test problems for the final

  Grades are available from the registrar office (and won't be posted on this web page).

Homework Assignments and Exams:

• Homework 1 was due Tuesday, February 25, 6:00 pm.
  (Due to continuing severe weather condition, all day and evening classes are cancelled for Tuesday, February 18. Therefore, we not only canceled the class on February 18, but also postponed the deadline for submitting Homework 1 by 1 week.)
  
  Solutions to Homework 1
  (Please inform the instructor if there are any typos, mistakes, or inaccuracies in the solutions.)
  
  
• Homework 2 was due Tuesday, March 11, 6:00 pm.
  
  Solutions to Homework 2
  (Please inform the instructor if there are any typos, mistakes, or inaccuracies in the solutions.)
  
  
• Homework 3 was due Tuesday, April 1, 6:00 pm.
  
  Solutions to Homework 3
  (Please inform the instructor if there are any typos, mistakes, or inaccuracies in the solutions.)
  
  Grades (include Homework 1, 2, 3 and Midterm)
  (Students names are sorted according to the last 3 digits of their IDs. The instructor doesn't have the ID of one student and since two students have the same 3 last digits of their ID, their initials has been put to distinguish between them.)
  
  
• Homework 4 was due Tuesday, April 22, 6:00 pm.
  
  Solutions to Homework 4
  (Please inform the instructor if there are any typos, mistakes, or inaccuracies in the solutions.)
  
  
• Homework 5 is due Sunday, May 4, 6:00 pm.
  
  Solutions to Homework 5
  (Please inform the instructor if there are any typos, mistakes, or inaccuracies in the solutions.)
  
  

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 Textbook:
  
  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.

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, as discussed in the class.
  
  

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.

Specific contents:

1. (1/21/03)
   • 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.
     • We proved (formally) that every tree with n nodes has n-1 edges.
   • Suggested reading: Chapters 22.1, B4, B5 in the textbook.
2. (1/28/03)
   • 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 and its analysis.
   • 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 haven't proved all details of the correctness of the BFS algorithm; but we have played a lot with its analysis).
   • Depth-first search algorithm (beginning only - more will be done in the next lecture).
   • Suggested reading: Chapters 22.1, 22.2, 22.3 in the textbook.
3. (2/4/03)
   • Detailed analysis of the breadth-first search algorithm (proof of correctness; see the proof of Theorem 22.5 [Correctness of breadth-first search] in Chapter 22.2 in the textbook).
   • Depth-first search algorithm and its analysis.
   • Main properties of depth-first search; analysis of the types of edges in DFS: tree edges, back edges, forwards edges, and cross edges.
   • Topological sorting algorithms: using depth-first search and using a direct approach.
   • Suggested reading: Chapters 22.2, 22.3, 22.4 in the textbook.
4. (2/11/03)
   • Discussion on the 1st homework assignment.
   • Lower bound for topological sorting in adjacency matrix representation.
   • k-connected and k-edge-connected graphs and Menger's theorem.
   • DFS-based algorithm for finding articulation points in a graph. (Running time is O(n+m).)
   • Reading: Textbook, Chapter 22. A very good description about the DFS-based biconnectivity algorithm is available from an old lecture notes of Prof. Mount (file in postscript format).
5. (2/18/03)
   Class cancelled
   Due to severe weather condition, all day and evening classes in NJIT are cancelled for Tuesday, February 18.
6. (2/25/03)
   • Algorithms for finding minimum spanning trees in graphs.
   • Meta-algorithm; proof of its correctness.
   • Kruskal's algorithm.
   • Prim's algorithm.
   • Reading: Textbook, Chapter 23. Look also at pages 57-61 in the postscript file of Prof. Mehlhorn for a good description of MST algorithms.
7. (3/4/03)
   • Implementation of Prim's algorithm for dense graphs - running time O(n² + m).
   • Round-robin algorithm for MST
     • Basic analysis leading to an O(m log(m))-time implementation.
     • Very brief sketch of the improved implementation that achieves the running time of O(m log log(m)) (see the Mehlhorn book for more details).
     • Linear-time implementation for planar graphs.
   • Planar graphs and some of their basic properties (Euler formula).
   • Introduction to the single-source shortest path problem.
   • Reading: Textbook, Chapters 23 and 24. Look also at pages 57-61 in the postscript file of Prof. Mehlhorn for a good description of MST algorithms.

8. (3/11/03)
   • Single-source shortest path problem:
     • Bellman-Ford algorithm achieving the running time of O(nm).
     • Efficient (optimal) algorithm for directed acyclic graphs - "variant" of Bellman-Ford algorithm with the running time of O(n+m).
     • Dijkstra algorithm - works only for graphs with non-negative weights - running time of O(m + n log n).
   • All-pairs shortest path problem:
     • Problem definition.
     • Simplest approach - call algorithms for single-source shortest path problem for each vertex being the source:
       • n times Bellman-Ford algorithm leads to an O(m n²)-time algorithm.
       • n times Dijkstra algorithm leads to an O(n (m + n log n))-time algorithm (works only for graphs with non-negative weights).
     • Simple algorithm achieving the running time of O(n⁴).
     • Improvement to the running time of O(n³ log(n)).
     • Further improvement - Floyd-Warshall algorithm - running time of O(n³).
   • Reading: Textbook, Chapters 24 and 25. I especially encourage all students to read in details Chapter 24.5, where a quite complete analysis of properties of single-source shortest path algorithms is given; it's very formal, but ... perhaps it makes sense for you to read it.
9. (3/25/03)
   • Midterm
     More detailed information about the midterm - and Sample test problems for midterm and solutions to some/most of them (might not work in Unix - sorry).
10. (4/1/03)
    • Detailed discussion about the midterm problems and Homework 3.
    • Problems that everybody should known about:
      • strongly connected components and finding strongly connected component (read in the textbook),
      • bipartite graphs and graph coloring (a graph is bipartite if and only if it's 2-colorable --- and if and only if every cycle in the graph has even length),
      • testing if a graph is 1-colorable, 2-colorable, ... and testing 3-colorability is NP-hard,
      • Euler tours/paths in undirected and directed graphs,
      • a sketch of an algorithm that finds an Euler tour in an Eulerian graph,
      • matchings: perfect, maximal, and maximum,
      • algorithmic proof that every 2^k-regular bipartite graph has a perfect matching.
11. (4/8/03)
    • Continuation: O(m)-time algorithm for finding a perfect matching in 2^k-regular bipartite graphs (where m = n 2^k-1).
    • Edge coloring.
    • An O(m log(m/n))-time algorithm for finding a 2^k-edge-coloring in 2^k-regular bipartite graphs (where m = n 2^k-1).
    • Vertex coloring.
    • A polynomial-time algorithm that for any undirected graph G with maximum degree D finds a (D+1)-vertex coloring of G.
    • Independent sets in graphs.
    • A polynomial-time algorithm that for any undirected graph G with n vertices and with maximum degree D finds an independent set of size at least n/(D+1).
      • Using a simple observation: in any proper vertex coloring of a graph, the vertices of any single color form an independent set.
    • A linear-time algorithm that finds a 6-vertex coloring in any planar graph.
      • The algorithm uses a simple corollary from the Euler's formula that every planar graph has at least one vertex of degree smaller than or equal to 5.
    • 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.
    • Reading: Textbook, Chapter 26, Problem 26-7 (pages 696-697).
      If you want to see some information about vertex-coloring, edge-coloring, independent-sets, efficient algorithms on trees, etc., ... then try to surf on the web - you should be able to find a lot of exciting information.
12. (4/15/03)
    • 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) by finding a maximum set of shortest vertex-disjoint augmenting paths in each step.
      • The running time is O(n^0.5 (n+m)).
    • Koning's theorem and its application to finding a minimum vertex cover and maximum independent set in bipartite graphs (haven't finished yet - will be continued in the next lecture).
    • Flows in networks (directed graphs with capacities) and the maximum-flow problem.
    • Reading: Textbook, Chapter 26 and Problem 26-7 (pages 696-697).
13. (4/22/03)
    • Long discussion about Homework 4 and Homework 5, and some general comments about the homeworks.
    • Koning's theorem and its application to finding a minimum vertex cover and maximum independent set in bipartite graphs (continuation from the previous lecture).
    • Maximum flow problem in graphs:
      • Residual networks and augmenting flow along augmenting paths.
      • Max-flow Min-cut theorem.
      • Ford-Fulkerson algorithm.
      • Edmonds-Karp algorithm.
    • Max-cut problem in graphs (a cute randomized algorithm).
    • The Planar Separator Theorem (only introduction).
    • Reading: Textbook, Chapter 26.
      Section 4.10 (pages 89-125) from Mehlhorn's book, where a fairly good description of planar graphs can be found. Theorem 7 (page 118) and Corollary 1 (page 123) are Planar Separator Theorems. Text following these theorems contains some examples of their use.
      Additionally, copies of three pages from the original article due to Lipton and Tarjan about applications of the Planar Separator Theorem are available here: page 1, page 2, and page 3. This text contains also a brief description of the algorithm for the matching problem in planar graphs, as discussed in the class.
14. (4/29/03)
    • Approximation algorithms.
    • 2-Approximation algorithm for the minimum vertex cover.
    • Traveling Salesperson Problem (TSP)
    • NP-hard,
    • For any c > 1, it's NP-hard to find an c-approximation algorithm,
    • ... but can be well approximated if triangle inequality is satisfied
      • 2-approximation algorithm for TSP (find a minimum spanning tree, and output the nodes in the Hamiltonian cycle according to the DFS-numbering in the tree); analysis by Euler tours and shortcuttings
      • 1.5-approximation algorithm for TSP (find a minimum spanning tree MST, find a minimum-weight perfect matching M on vertices of odd degree in MST, find an Euler tour on MST + M, and obtain the Hamiltonian path by traversing the Euler tour and shortcutting all nodes that appear not on the first time)
    • Linear programming and Integer programming: generic tools to solve many combinatorial optimization problems
    • Reading: Textbook, Chapter 35 (in particular 35.1 and 35.2).
15. (5/13/03)
    • Final Exam
    • The final exam took place on the finals week, on Tuesday, May 13, 6-9pm, in TIER 108.
    • The final exam was worth 250 points.
    • The final exam was cumulative (that is, all course material will be examined) and was open-textbook and open class-notes only.
    • Detailed information about topics covered in the final is available.
    • Sample test problems for the final are available.
    • Grades are available from the registrar office (and won't be posted on this web page).

If You will find 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. All of You are very welcome. If You have interest then please contact me via email czumaj@cis.njit.edu.