Status: December 17, 2002

Instructor:

Schedule:

Contents:

This graduate course in CS deals with advanced analysis of algorithms and data structures. It should be considered as a course extending the material presented in CIS 610 and partly in CIS 665.

Main Topics: approximation algorithms and string matching algorithms.

Approximation Algorithms deal with efficient algorithms for intractable (hard) optimization problems for which approximately optimal solutions are sought. Combinatorial algorithms for a number of important problems using a wide variety of algorithm design technique will be discussed. Then, linear programming based algorithms will be presented. Special attention will be paid to approximation algorithms for graph problems and for problems in large-scale networks.

String/Pattern Matching Algorithms deal with the basic problem of searching for a text (pattern) in a larger text or a set of texts, and its various extensions. Classical algorithms (including Knuth-Morris-Pratt and Boyer-Moore algorithms) and its more practical or advanced variants (including very efficient and practical algorithms using suffix trees) for string matching will be discussed. Extensions to problems arising in applications in databases and computational biology will be presented.

Recent advances in algorithms - Primality in P: very recently (summer 2002), a polynomial time algorithm has been designed to verify if a given number is prime. Since this is a landmark result in the area of algorithms (solving a long standing open problem), the primality testing algorithms will be tentatively presented in the class.

Even though most of the algorithms discussed arose from practical applications, emphasis will be mostly on theoretical aspects of the algorithms.

Prerequisite: CIS 610 or the permission of the instructor

Grading and Policies:

Homework Assignments:

1. Students were asked to write a short essay about a few basic NP-hard problems for which approximation algorithms were discussed in the class.
   • Vertex cover by Christopher Leberknight.
   • Set cover by Katherine Herbert.
   • Graph coloring by Roger G. Doss.
   • Traveling salesman problem by Han Wang and Jian Chen.
   • Steiner tree problem in graphs by Yumei Huo.
   • Approximation algorithms for NP-hard problems on Euclidean graphs by Hairong Zhao.
   
   
   
2. Students are asked to read very carefully a few papers about TSP and cycle cover problem.

   On Thursday, December 12, from 5:30pm, there will be a meeting in (tentatively) large conference room GITC 4415, where students are supposed to discuss the papers on TSP they have been assigned to.

References:

Textbooks:

There are no single textbooks used by the instructor. However, there are a few books which could be very useful in the course.

• »Approximation Algorithms« by Vijay V. Vazirani, Springer, 2001.
  An excellent and very up-to-date textbook on approximation algorithms. A large part of the course material on approximation algorithms will be based on the presentation from this textbook.



• »Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties« by G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Springer, 1999.
  A standard textbook on optimization problems/algorithms and approximation algorithms.



• »Approximation Algorithms for NP-hard Problems« edited by D.S. Hochbaum, PWS Publishing, Boston, MA, 1997.
  A (very good) collection of survey articles dealing with various approximation algorithms.



• »Randomized Algorithms« by R. Motwani and P. Raghavan, Cambridge University Press, Cambridge, UK, 1995.
  An excellent (standard) textbook on randomized algorithms.



• »Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology« by D. Gusfield, Cambridge University Press, Cambridge, UK, 1997.
  Standard book on string matching algorithms and their applications to computational biology. Many classical algorithms are explained in a simple way.



• »Text Algorithms« by M. Crochemore and W. Rytter, Oxford University Press, 1994.
  An excelent textbook on string matching algorithms.



• »Jewels of Stringology« by M. Crochemore and W. Rytter, World Scientific Pub Co; ISBN: 9810247826, 2002.
  A new book on string matching algorithms (I myself haven't seen it yet ...)

Links relevant to approximation algorithms:

• »A compendium of NP optimization problems«, maintained by Pierluigi Crescenzi and Viggo Kann (sometimes it is not very up-to-date, some problems are missing, but otherwise, it's a great compendium). This compendium will be very helpful in the course ...
  
  
• »Lecture Notes on Approximation Algorithms« by David P. Williamson, 1998.
  
  
• A preliminary draft of Vazirani's book (some parts are missing, some are perhaps not as good as in the book, but it's free)
  
  
• 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.
  
  
• Postscript file of »Lecture Notes Approximationsalgorithmen« by Rolf Wanka (... if you can read German). Web page for this class is available too.
  Christian Scheideler used that lecture notes in his class and he has some lecture notes too.
  
  
• Very short text (in postscript) »Lecture Notes: Complexity of Approximation« by Berthold Vöcking
  
  
• Link to a much more advanced course »Advanced Topics in Theory of Algorithms : Approximation Algorithms« by Moses Charikar, Fall 2001, Princeton
  
  
• Link to a paper on approximation algorithms for Max-SAT: New 3/4-approximation algorithms for the maximum satisfiability problem by Michael Goemans and David P. Williamson
  
  
• Linear programming - various links
  • Linear Programming Frequently Asked Questions
  • Mysteries in Linear Programming by Komei Fukuda
  • Geometric Linear Programming
  • Open problem: Linear Programming: Strongly Polynomial?
  • A Short Course in Linear Programming by Harvey J. Greenberg
  
  
  

Links relevant to the primality testing algorithm:

• The paper
  
  
• Some random links (haven't checked them yet ...)
  • Links to things relevant to the polynomial-time primality testing algorithm
  • Brief description of the polynomial-time primality testing algorithm (Professor Caldwell's Prime Pages)
  • »The PRIMES is in P little FAQ«
  • »An exposition of the Agrawal-Kayal-Saxena primality-proving theorem« by D. J. Bernstein
  • »Notes on primality testing« by M. Michiel Smid
  
  
  

Links relevant to string/pattern matching:

• Pattern Matching Pointers (maintained by Stefano Lonardi)

• Handbook of Exact String-Matching Algorithms (pdf file with a text authored by C. Charras and T. Lecroq)

• An interesting Web page maintained by Thierry Lecroq

• Suffix Trees: Information Retrieval (class notes by Harry Hochheiser)

Other links:

• A new approximation algorithm for the asymmetric TSP with triangle inequality by Markus Bläser. Technical Report SIIM-TR-A-02-20, Institute für Informatik und Mathematik, Universtität Lübeck, September 2002, revised October 2002.
• An 5/8-approximaxtion algorithm for the maximum assymetric TSP by M. Lewenstein and M. Sviridenko, 2002.
• An 8/13-approximation algorithm for the asymmetric maximum TSP by Markus Bläser. Technical Report SIIM-TR-A-01-21, Institute für Informatik und Mathematik, Universtität Lübeck, December 2001. (Conference version available at http://doi.acm.org/10.1145/545381.545389).
• Long tours and short supertstring by S.R. Kosaraju, J.K. Park, and C. Stein, Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS), pages 166-177, Santa Fe, NM, November 20-22, 1994.
• The maximum traveling salesman problem by A. Barvinok, E.Kh. Gimadi, and A.I. Serdyukov, in The Traveling Salesman problem and its variations, 585-607, G. Gutin and A. Punnen, eds., Kluwer, 2002.
• A 7/8-approximation algorithm for metric Max TSP by R. Hassin and S. Rubinstein, Information Processing Letters 81(5):247-251, 2002.
• Better approximations for max TSP by R. Hassin and S. Rubinstein, Information Processing Letters 75(4):181-186, 2000.
• An approximation algorithm for the maximum traveling salesman problem by R. Hassin and S. Rubinstein, Information Processing Letters 67:125-130, 1998.

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.