IIT Kharagpur

Department of Computer Science and Engineering. Advances in Algorithms (Graduate level course in Autumn 2004) PG number CS60001 and UG number 60036, Updated August 09, 2004, 3:15 pm

All the exercises below may be attempted and submitted in handwriting.

------------ Main texts:

A. V. Aho, J. E. Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addision-Wesley, 1983.

T. H. Cormen, C. E. Leiserson and R. L. Rivest, Introduction to Algorithms, 1990.

F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction, New York, NY, Springer-Verlag, 1985.

Motwani and Raghavan, Randomized Algorithms.

Ketan Mulmuley, Computational Geometry: An Introduction through Randomized Algorithms.

Data Structures and Algorithms: Volumes I, II and III by Kurt Mehlhorn, Springer-Verlag.

Introduction to Algorithms: A creative approach, by Udi Manber, Addision-Wesley, 1989.

Foundations of algorithmics, Gilles Brassard and Bratley.

------------ References:

Bernard Chazelle, The discrepancy method: Randomness and complexity.

Martin Charles Golumbic, Algorithmic graph theory and perfect graphs.

R. E. Tarjan and , Data Structures and Network Algorithms, Society for Industrial and Applied Mathematics (SIAM).

Algorithm Design: Foundations, Analysis and Internet Examples by Michael T. Goodrich and Roberto Tamassia, John Wiley and Sons, Inc., 2002.

K. Mehlhorn and S. Naher, LEDA: a Platform for Combinatorial and Geometric Computing, Cambridge, UK, Cambridge University Press, 1999.

Monographs of Dexter Kozen

Basic graph theory by K. R. Parthasarathy.

Art Gallery Theorems and Algorithms by Joseph O'Rourke, Oxford Univ. Press.


We will have all the four lectures every week from July 27, 2004 onwards.

Considerable stress will be given on class tests and home assignments. Sound knowledge of elementary (i) data structuring (ii) design and analysis of algorithms (ii) discrete strcutures, and (iv) computational combinatorics is required to register for this course.


  End semester examination question paper (download postscript file).