==============================================================================
============================================================================
Department of Computer Science and Engineering, IIT Kharagpur 721302, India
=============================================================================
Updated: April 12, 2014
======================
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Evaluation: 20 for teacher's assessment, 30 for midsems and 50 for endsems as per rules.
--------------------------------------------------------------------------------------
Teaching Assistant: Satheesh Dannuri (M. Tech. 2012-2014)
--------------------------------------------------------------------------------------
=====================
[Not restricted to] Proposed topics:
=======================
Use of the probabilistic method in the design and analysis of algorithms and protocols, and demonstration of upper and lower bounds on combinatorial complexities of structures.
Combinatorial and computational issues in geometric visibility.
Problems and applications of graph and hypergraph theory.
=======================================
Instructor: Sudebkumar Prasant Pal
=======================================
TEXTS and REFERENCES:
=============================
(i) Motwani, R. and Raghavan, P., Randomized Algorithms, Cambridge University Press.
(ii) Chazelle, B., The Discrepancy Method: Randomness and Complexity, Cambridge University Press.
(iii) Ghosh, S. K., Visibility Algorithms in the Plane, Cambridge University Press.
(iv) Bollabas, B., Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability, Cambridge University Press, 1986.
(v) Molloy and Reed, Graph Coloring and the Probabilistic Method, Springer, 2002.
(vi) Pach, J., and Agarwal, P., Combinatorial Geometry, John Wiley and Sons, 1995.
(vii) Alon, N. and Spencer, J., The probabilistic method, John Wiley and Sons, Inc., 2000.
========================================================================
Elements of the Probabilistic Method
-------------------------------------------------------
-------------------------------------------------------