Status: July 6, 2002

Instructor:

Schedule:

Information about PhD Qualifying Exam:

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.

Next semester Prof. Czumaj is teaching an advanced course in algorithms, CIS 786: Selected Topics: Advanced Algorithms, Fall 2002.
All of you are welcome to attend that course. The course will extend many topics discussed in CIS 665 and also a lot of new material will be presented.

Exams and Homeworks:

• Problem Set 1 was due February 27, 2002.
  It is available in postscript format and in (Adobe) PDF format
  Solutions are available in postscript format and in (Adobe) PDF format
  
  
• Problem Set 2 was due March 13, 2002.
  It is available in postscript format and in (Adobe) PDF format
  Solutions are available in postscript format and in (Adobe) PDF format
  
  
• Midterm exam was on Wednesday, on March 13, 2002.
  A (quite large) collection of problems for preparation for the midterm exam is available in postscript format and in (Adobe) PDF format. To verify whether students solutions are correct, solutions were posted here in postscript format and in (Adobe) PDF format. Additionally, to help students to prepare to the midterm a couple of handouts have been prepared.
  Partial solutions are available in postscript format and in (Adobe) PDF format
  
  
• Problem Set 3 was due April 3/5, 2002.
  It is available in postscript format and in (Adobe) PDF format
  There has been an error in the previous version of the problem posted here, so please read the problems once again. (The error was in Problem 2 where the required running time is O(n_1 * n_2).)
  Solutions are available in postscript format and in (Adobe) PDF format
  
  
• Problem Set 4 is due April 24, 2002.
  It is available in postscript format and in (Adobe) PDF format
  Solutions are available in postscript format and in (Adobe) PDF format
  
  
• Problem Set 5 is due May 1/6, 2002.
  It is available in postscript format and in (Adobe) PDF format
  Solutions are available in postscript format and in (Adobe) PDF format
  
  
• Grades are available. They include all Homeworks 1-5 and Midterm, and sum of the points after dropping the homework with the lowest grade.
  
  
• Final Exam took place on Wednesday, May 15, 2002, 6:00-9:00pm, in classroom TIER 105. Information about the topics covered are available here.

  Grades are available from the registrar office.

  Solutions to the final exam questions will NOT be put on the class web page.
  Every student willing to know the solutions or willing to discuss her/his final exam, should try to make an appintment with the instructor.

Contents:

This is an advanced course on algorithms and data structures that concentrates on the area of 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 foundamental properties of graphs.

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

Grading and Policies:

• Grading will be based on 5 problems sets (homeworks, possibly including one programming assignment), an in-class midterm, and a final.

• Five homeworks will be handled out. Each homework is worth 50 points. One homework with the lowest grade will be dropped from grade consideration. Thus, the homeworks contribute a total of at most 200 points towards the final grade. Homeworks will be posted on the course Web-page http://web.njit.edu/~czumaj/TEACHING/CIS665-S02.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.
  
  
• The midterm exam took place on Wednesday, on March 13, 2002.
  It was closed book/note/etc.
  The midterm exam was worth 150 points.
  Grades for midterm are available (For any questions please contact the instructor during his office hours)

• The final exam took place on Wednesday, May 15, 2002, 6:00-9:00pm, in classroom TIER 105.
  The final exam is cumulative (that is, all course material will be examined) and will be open-textbook and open class-notes only.
  Information about the topics covered are available here.
  The final exam is worth 250 points.
  Grades will be available on Friday, May 17, from the registrar office.

References:

• MAIN TEXTBOOK:
  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.

Handouts/Links to further references:

• A very good description of an DFS-based algorithm for biconnectivity is available from an old lecture notes of Prof. Mount (file in postscripf format)
• Prof. Mehlhorn made parts of his book on algorithms available on his web-page. Look at pages 57-61 in the postcript 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.

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.