Final status: May 5, 2006 (no further updates of this web page are planned)

Thanks for taking the course!

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

• Three homework assignments will be handled out. Each homework is worth 67 points. 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-S06.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 9, 2005. For more details (including grades and sample solutions) see here
• The final exam is worth 250 points. The final exam is cumulative (that is, all course material will be examined) and open-textbook and open class-notes only.

  Date of the final exam: 6:00-8:45pm, Thursday, May 4, 2006.

• The NJIT Academic Honor Code (http://www.njit.edu/academics/honorcode.php) will be upheld.
  In particular, copying homework solutions or programs, in full or in part, is forbidden. You may discuss ideas and concepts with your fellow students, but you may NOT copy it. Any violations will be brought to the immediate attention of the Dean of Students.

• Homework 1 was due February 16, 2006 (postscript file is also available)
  Sample solutions to problems in Homework 1 are available (postscript file too).
• Homework 2 was due March 30, 2006 (postscript file is also available)
  Sample solutions to problems in Homework 2 are available (postscript file too).
• Homework 3 was due April 30, 2006 (postscript file is also available)
  Sample solutions to problems in Homework 3 are available (postscript file too).
• To enable students to prepare better to the final exam etc., we made available some materials from the last year (2005):
  • Homework 1 with solutions
  • Homework 2 with solutions
  • Homework 3 with solutions
  • Homework 4 without solutions
  • Midterm with solutions
  • Final exam without solutions

1. (1/19/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/26/05)
   • Basic proof techniques, continuation (proving that every tree with n vertices has n-1 edges, that a forest with n vertices and cc connected components has n-cc edges)
   • Graph traversal algorithms.
   • Breadth-first search (BFS) scheme to traverse the graph
     • its basic properties,
     • its running time (O(n+m) in adjacency list model and O(n²) in adjacency matrix model),
     • using BFS to find the shortest distances (in the sense of the minimum number of edges) from a single vertex to all other vertices.
   • Depth-first search (DFS) algorithm.
     • Basic properties, including properties of dfs-numbering and finishing times.
     • Partition of edges into tree-edges, back edges, forward edges, and cross edges.
   • Suggested reading: Chapters 22.1, 22.2 in the textbook.

3. (2/2/05)
   • Topological sorting.
     • Discussion of some basic properties,
     • Two "linear-time" algorithms for topological sort (in adjacency list representation).
   • Suggested reading:Chapter 22.3 in the textbook.

4. (2/9/05)
   • Brief discussion about Homework 1
   • 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 source is a vertex with in-degree 0 and out-degree n-1.)
   • 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².]
   • 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.
     • Running-time O(n+m).
   • 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. For biconnectivity testing, see the article by Mount.

5. (2/16/05)
   • Brief presentation of solutions to Homework 1 (see here for more details).
   • More details on biconnectivity testing.
   • Finding strongly connected components by two runs of DFS.
   • Testing bipartitness of a graph:
     • Graph G = (V,E) is bipartite if we can partition the set of vertices V into two sets V₁ and V₂ such that every edge in E has one endpoint in V₁ and another in V₂.
     • Simple O(n+m)-time algorithm for testing if graph is bipartite - if G is bipartite, then the algorithm can find the required partition of V into V₁ and V₂.
   • Graph coloring.
     • For an undirected graph G=(V,E), a k-coloring is any function χ : V → {1,2,...,k} such that for every edge (v,u) in E we have χ(v) ≠ χ(u).
     • The problem of verifying if a given graph G = (V,E) has a k-coloring is NP-complete for all k ≥ 3.
     • The problem of testing if G = (V,E) has a 2-coloring has an O(n+m)-time algorithm (because G has 2-coloring iff G is bipartite).
   • Edge-coloring of a graph.
     • For an undirected graph G = (V,E), a k-edge-coloring is any function χ : E → {1,2,...,k} such that for every vertex v in V and every two distinct edges (v,u) and (v,w) in E we have χ(v,u) ≠ χ(v,w).
     • Vizing's Theorem: Every undirected graph G = (V,E) has a k-edge-coloring for Δ(G) ≤ k ≤ Δ(G)+1, where Δ(G) is the maximum degree in G.
     • The problem of verifying if a given graph has a Δ(G)-edge-coloring is NP-complete.
   • Suggested reading: Chapter 22.5 in the textbook (strong connectivity); for biconnectivity testing, see the article by Mount.

6. (2/23/05)
   • Vertex colorings and chromatic number χ(G).
   • O(n+m)-time algorithm that finds a (Δ(G)+1)-vertex-coloring of a graph with maximum degree Δ(G).
   • 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:
       • G has an Eulerian cycle if and only if G is connected and every vertex has even degree.
       • G has an Eulerian tour if and only if G is connected and at most two vertices are having odd degree.
     • O(n + m)-time algorithm for finding an Eulerian tour or a cycle in a graph.
   • Proof of the Vizing's theorem: every undirected simple graph G = (V,E) has Δ(G) ≤ χ'(G) ≤ Δ(G)+1, where Δ(G) is the maximum degree in G and χ'(G) denotes the minimum number k for which G has a k-edge-coloring.
     • See here for a proof.

7. (3/2/05)
   • Discussion about Midterm exam (by Xin Wang).
   • For more details see here.

8. (3/9/05)
   • Midterm exam:
     • it was open textbook/notes
     • it was about 2 hours 45 minutes long
     • there were 4 problems to be solved - all problems had the same weight in the final score
     • you should have known all what has been discussed in the class
     • and the main goal was to understand algorithms and graph theory
     • sample problems (with sample solutions):
       • Midterm from 2005
       • Randomly chosen sample problems
   • Grades
   • Sample solutions to Midterm are available (postscript file too).

9. (3/23/05)
   • Discussion about Midterm exam and Homework 2
   • Minimum spanning trees
     • Basic definitions
     • Meta-algorithm for finding a minimum spanning tree: construct minimum spanning tree by analysing one edge after another and either taking the edge to the tree or removing it from further consideration
     • Cycle rule: the heaviest edge on any cycle can be eliminated (avoided) from a minimum spanning tree
       • Proof of correctness of that claim: Let C be an arbitrary cycle in a graph and let e be the heaviest edge in C (ties allowed), then there is a minimum spanning tree that doesn't contain edge e
     • Cut-rule: the lightest edge across any cut can be added to a minimum spanning tree
       • Proof of correctness of that claim: Let (V₁, V₂) be an arbitrary cut in G and let e be the lightest edge across the cut (that is, e has one endpoint is in V₁ and another in V₂, and for any other edge e' across the cut, w(e) ≤ w(e')), then there is a minimum spanning tree that contains e
   • Kruskal algorithm as an implementation of Meta-algorithm
     • Kruskal algorithm:
       • T - edge-less forest
       • for every edge e in the non-decreasing order of edge weights:
         • if T + {e} has no cycle then
           • T = T + {e}
       • return T as a minimum spanning tree
   • Union-Find data structure and an efficient implementation of Kruskal algorithm
   • Suggested reading: Chapter 23 in the textbook and pages 57 - 61 in the textbook by K. Mehlhorn

10. (3/30/05)
    • Union-Find data structure and an efficient implementation of Kruskal algorithm
      • Union-Find algorithm using trees (for more information, see Chapters 21.3-21.4 in the textbook): 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
    • Efficient implementations of Prim's algorithm
      • 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, Chapter 20, 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
        • 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)
    • Planar graphs and their applications
      • 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 (left to students)
        • Proof of the standard fact: every planar (simple) graph has the number of edges upper bounded by 3n-6
    • Suggested reading: Chapter 23 in the textbook and pages 57 - 61 in the textbook by K. Mehlhorn (especially his discussion on Round Robin algorithm)

11. (4/6/05)
    • Introduction to shortest path problems
    • Single-source shortest path problem
    • Bellman-Ford algorithm achieving the running time of O(nm)
    • Extension of the Bellman-Ford algorithm 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, similar to Prims' algorithm
      • 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
    • All pairs shortest path problem
    • 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-Warshall algorithm: another dynamic programming leads to a very simple O(n³)-time algorithm
    • Suggested reading: Chapters 24 and 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/13/05)
    • Euler's formula (in every simple planar graph: n + f = m + 1 + connected components)
      • Two different proofs (by induction) of the Euler's formula
      • Proof that every planar (simple) graph has at least one vertex with degree at most 5
      • Proof that every planar (simple) graph has at least 1% of vertices with degree at most 6
    • Coloring planar graphs
      • The Four-Color Theorem: every planar graph can be 4-colored (famous and very hard result)
      • 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
      • Finding an independent set of size at least n/6 (in planar graphs); using the Four-Color Theorem, an independent set of size at least n/4 can be found
    • Maximal and maximum matching problem
    • Perfect matching in graphs
    • Alternating paths and augmenting paths
    • Berge theorem:
      • Let G=(V,E) be an undirected graph and let M be a matching in G. Then, M is a maximum matching if and only if there is no augmenting path in G (with respect to M)
      • Proof of Berge theorem
    • Problem of finding a maximum matching in 2^k-regular bipartite graphs is "easy" - can be solved in time O(m)
    • Suggested reading: Chapter 5 from the book of Bondy and Murty (about matching)

13. (4/20/05)
    • An efficient algorithm for finding a perfect matching in an 2^k-regular graph (running-time O(m))
    • Hall's theorem, sketch of its 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
    • 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 http://www.cs.umd.edu/class/spring2002/cmsc651/lec06.ps (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
      • 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 of P
      • Edmonds-Karp algorithm: Ford-Fulkerson algorithm in which a shortest path is always selected (achieves the running-time of O(n m²))
      • Min-cut max-flow theorem
    • Suggested reading: Textbook, Chapter 26 and Problem 26-7 (pages 696-697), Chapter 5 from the book of Bondy and Murty (about matching), and text (in postscript format) about Hopcroft-Karp matching algorithm

14. (4/27/05)
    • k-vertex-connectivity and k-edge-connectivity
    • Menger's theorem
    • Application of the max-flow problem to compute the edge-connectivity of an undirected graph
    • Planar Separator Theorem and its applications
      • maximum matching in planar graphs
      • maximum independent set 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
      • Approximation algorithm for the minimum-weight vertex cover problem
    • Discussion about the final exam
    • Suggested reading: Chapter 35 in the textbook, Chapter 9 from the book of Bondy and Murty (about planar graphs), and Mehlhorn book (especially Chapters 4.9 and 4.10)

• Material covered: everything discussed in the class
• Grades will be submitted directly to the registrar - they won't be posted on the course web page. Discussion of the grading can be handled on the individual basis.

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

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

• Postscript file (gzipped) of »Lecture Notes on Approximation Algorithms - Volume I« by Rajeev Motwani, Stanford (14-15 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.