Status: June 30, 2001

 

»CIS 665: Algorithmic Graph Theory«

Spring 2001

Section 002
  

Instructor:

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  8:30 - 11:25  FAC 411
        
Office hours  Tuesday  11:30 - 12:55  GITC 4103
   Wednesday  11:30 - 12:55  GITC 4103
        
By special appointments  Thursday  11:30 - 12:10  GITC 4103
(only in very special cases)       

Information about PhD Qualifying Exam:

Info in postscript format and in PDF-Format

Contents:

NEW! 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. NEW!

 

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 - an algorithm without any arguments showing its correctness is useless). We will also analyze some foundamental properties of graphs.

Prerequisite: CIS 610 (if you didn't take this course, then contact the instructor immediately)

Description from the NJIT undergraduate course catalog:
CIS 665: Algorithmic Graph Theory
The elements of the theory of graphs and directed graphs with motivating examples from communication networks, data structures, etc; shortest paths, depth first search, matching algorithms, parallel algorithms, minimum spanning trees, basic complexity theory, planarity, and other topics. Programming assignments are included.

Grading and Policies:

  • Grading will be based on 5 problems sets (homeworks), two programming assignments, an in-class midterm, and a final.

  • NEW! Final exam will take place on May 4, 8:30am-11:00am, in KUPF 202. It is open textbook and it is worth 300 points.
    The final exam is cumulative and covers all course material.

  • Midterm exam took place place on March 6, 2001. It was open textbook and it was worth 200 points.

    Midterm covered the following material:

    • Graph representations (adjacency matrices, adjacency lists, etc.)
    • Graph traversals (depth-first search, breadth-first search - in undirected and directed graphs; and also properties of dfs-numbering, etc)
    • Topological sorting
    • k-connectivity and biconnectivity (including algorithms for testing if a given graph is k-vertex (or -edge) connected, and Menger's theorem)
    • Minimum spanning trees (meta-algorithm, proof of its correctness, its "implementations": Kruskal algorithm, Prim algorithm, round-robin algorithm)

    It was assumed (or required) that students understand the material presented in the class and hence, that students are able to use/manipulate these algorithms, know and use their properties, etc.

    Students should also know how to analyze algorithms, that is, how to provide the analysis of the correctness of an algorithm, the analysis of the running time of the algorithm, and eventually, how to prove a lower bound for the running time (that is, to show that no algorithm solving given problem can run (in the worst-case) faster than in ??? time).

    As always in this course, the efficiency of the algorithms designed played a very crucial role.

  • The assignments included periodic problem sets and one programming assignment.
    Five problem sets will be handled out. Each problem set is worth 50 points.
    Two programming assignment will be handled out. The programming assignments are worth 50 points and it will require implemention either in C or in C++.

    Tentative schedule of assignments:
    The two homeworks (out of the five problem sets and two programming assignment) with the lowest grade will be dropped from grade consideration. Thus, the homeworks contribute a total of at most 250 points towards the final grade.
    • Homeworks will posted on the course Web-page http://www.cis.njit.edu/~czumaj/TEACHING/CIS665-S01.html both in postscript and in Adobe Acrobat format.
    • Homeworks are due at the start of class on their due date. They can be submitted either per email czumaj@cis.njit.edu or be delivered 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 handwritting!!!), 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.
Exams, Homeworks, and Programming Assignments:
References:
  • Main textbook: T.H. Cormen, C.E. Leiserson, and R.L. Rivest, »Introduction to Algorithms«, The MIT Press/McGraw Hill, 1990

  • Large part of the course will follow chapters 5 and 23-27 from the main textbook.
    However, this textbook will not cover some parts of the material presented in the class!!!

  • Notes about biconnectivity algorithms are available as a postscript file (this file was prepared in 1998 by Prof. Dave Mount from CMU)

  • Additional references:
    • K. Mehlhorn "Data Structures and Algorithm. Volume II: Graph Algorithms and NP-Completness." (especially the part on planar graphs that is available in postscript here)

NEW! 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.

Artur Czumaj, June 30, 2001