IIT Kharagpur

Department of Computer Science and Engineering.

Advances in Algorithms (Graduate level course in Autumn 2003) PG number CS60001 and UG number 60036, Updated November 17, 2003, 3:15 pm

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

Class test on September 10, 2003 at 7:30 am.

Class test on November 13, 2003 at 9:30 am.

CLASSES resume Monday October 5, 2003 at 9:30 pm

Final end semester examination 1:30 pm - 4:30 pm Sunday in CSE seminar room November 23, 2003.

Grades obtained:

Ex- Devendra, Gawas, Sudhir Kumar Singh

A- Animesh, Sai Kiran, Hrishikesh, Vikram, Lt. Roy, Sudhir Porwal, Sima

B- Ajit Sen, Suryakanta, Srihari, Dandadpat, Nitin, Debasri, Dipti Ranjan, Lt. Vatsa, Piu, Rakesh

C- Srinivasulu, Juri, S. K. Singh, Najumudheen, Arundhati

D- Raja Sekhar Singh, Jala Srinivas

------------ 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, 2003 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.

----------------------------------------------------

QUIZ on July 28, 2003 at 10 am; the class starts at 9:30 am. The quiz will be aimed at determining your level of understanding of prerequisites for the course.

--------------------------------------------------------------------

  Mid-semester examination question paper (download postscript file).

Lectures on July 30, 2003.

--------------------------

Introduction to graphs, perfect graphs, hypergraphs, chromatic number, stability, maximum clique size and minimum clique cover numbers. Chordal and interval graphs.

----------------------------------------------

E1:

Exercises.

----------

**(i) Argue that trees and interval graphs are perfect graphs.

*(ii) Show that an interval graph is also a chordal graph.

(iii) Show that the problem of determining whether an undirected graph with n vertices has an independent set of size n/3 is an NP-complete problem. (Assume that n is a multiple of 3).

*(iv) Suppose you are given a set of n intervals on the line. Consider the intersection graph of the n intervals. Design O(n log n) algorithms for computing the maximum clique and the maximum stable set of this graph.

-----------------------------------------

Lecture on July 31, 2003.

---------------------------

Graph isomorphism and non-isomorphism, computing independent sets for trees.

-------------------------------

E2:

Exercises.

--------------

(i) Show that the graph isomorphism problem is in NP.

*(ii) Show that the graph non-isomorphism problem is in PSPACE. (PSPACE is the class of problems decidable using computations requiring at most p(n) time where p is a polynomial and n is the input size.)

*(iii) Show that the maximum independent set for a tree can be computed in polynomial time.

*(iv) Show that the problem of finding the minimum sized vertex cover for an undirected graph is NP-hard.

------------------------------------------------------------------

Lecture on August 4, 2003

-----------------------------

Computing independent sets, chromatic numbers and clique numbers for interval graphs; using dynamic programming for computing maxmimum cardinality independent sets for trees.

--------------------------

E3:

Exercises

----------------------

(i) Suppose we put nonzero positive weights to vertices in a tree and seek the maximum weighted independent set instead of the maximum cardinality independent set. Show that this problem can also be solved in polynomial time.

(ii) Study exercises: weak and strong perfect graph conjectures (see for instance the books by Golumbic or K. R. Parthasarathy).

Click here for more.

----------------------------

Lectures on August 6, 2003

-----------------------------

Computing weighted independent sets for trees using dynamic programming; introduction to dominating and independent dominating sets, edge-independent sets or matchings, line graphs and the graph reconstruction problem.

E4:

Exercises.

------------

(i) Show that a maximum cardinality independent set is also a dominating set.

(ii) Show that a minimum cardinality dominating set is not necessarily an independent set.

-----------------------------------------------------

Lectures on August 7

-------------------------------

An art gallery theorem (showing that n/3 vertex guards are sufficient (and sometimes necessary) for a simple polygon)- proof using 3-colouring of the triangulation graph; introduction to cuts in graphs, computing the minimum cut in an undirected graph using maximum flows in networks, computing a min-cut with high probability.

E5:

Exercises

---------------------------

(i) Write your own proofs for the art gallery theorem on the number of sufficient vertex guards. Use induction if you wish.

(ii) Show that if the edges of the simple polygon are either vertical or horizontal then we need no more than n/4 vertex guards.

-------------------------------------------

Lecture on August 11

----------------------------

The design of (i) a slow worst-case polynomial time algorithm and (ii) a faster Monte Carlo algorithm for min-cuts in undirected graphs.

E6:

Exercises.

--------------

(i) Design your fastest deterministic (sequential) algorithm for computing the minimum sized cut in an undirected graph.

(ii) Suppose you have n letters and n envelopes with labels for indicating which letter must go into what envelope. Then, show that the probability that each letter goes into a wrong envelope approaches a constant as n blows up. What is the value of this constant? (This is assuming that each permutation is equally likely in the assignment of letters to envelopes.)

------------------------------------------------

Lectures on August 13.

---------------------------

Analysis of the Monte Carlo min-cut algorithm; amortization example for 2-4 trees.

E7:

Exercises.

---------------

(i) Develop a potential function that lends to an O(n) time bound in an amortised analysis of 2-4 trees' maintenance work when we consider not just insertions but also deletions in random order and ignore search costs altogether as we did for the "only insertions" case in class.

(ii) Is it possible to reduce the error probability in the min-cut algorithm to an inverse exponential in the number of vertices keeping the running time polynomial in the number of vertices? Explain.

--------------------------------------

Lecture on August 14.

------------------------------------------

Amortization examples for 2-4 trees (contd.); another amortization example, the case of a binary counter; introduction to the longest upsequence problem, an example in dynamic programming.

E8:

Exercises.

--------------

(i) Consider the LCS problem as given in Cormen et al. Given two strings A and B, we wish to determine the length of the longest common subsequence between A and B. Study the dynamic programming solution to this problem and find the fastest implementation possible.

(ii) Provide a dynamic programming O(n^2) algorithm for the longest upsequence problem. Is it possible to use the LCS problem to solve this problem? Explain.

(iii) Design an O(n log n) (dynamic programming ?) algorithm for the longest upsequence problem. Explain the data structuring required to get the improvement over (ii) above.

----------------------------

Lectures on August 20.

--------------------------------

Applications (in VLSI routing and scheduling) of the properties of chordal graphs; partitioning simple polygons into convex polygons, triangulating with minimum ink.

E9:

Exercises

------------------------

(i) State a version of the knapsack problem and show that an algorithm running in time proportional to the magnitude of certain input parameters is possible for this problem. Does this problem belong to the class P?

(ii) Work out the detailed implementation using data structures for computing a triangulation of a convex polygon with minimum ink. Repeat the process for simple polygons.

---------------------------------------------

Lecture on August 21

----------------------

Continuation of the routing example from VLSI using chordal graph properties; an example of a Markov process-- a signature for stack distance distributions using dynamic programming;

Lecture on August 25

------------------------------------

Continuation of generic signature computation for stack distance distributions; hiding people in polygons-- yet another example for dynamic programming;

Lectures on August 27

------------------------------------

Shortest paths in simple polygons, computing the maximum hidden set;

Lecture on August 28

------------------------------------

Sorting using randomization, building and analyzing randomized search trees;

Lecture on September 1

--------------------------------

Expected O(n log n) time building of randomized search trees; expected O(log n) time searching in randomized search trees.

Lectures on September 3

--------------------------------

Analysis of expected search time in randomized search trees; the problem of computing the planar map of n finite length line segments in the plane.

Lecture on September 4

--------------------------------

The problem of generating a truly random permutation of n objects using O(n log n) truly random bits; introduction to the problem and the motivation behind constructing n pseudo-random numbers using only O(log n) truly random bits--- the linear congruential generator.

Lecture on September 8

--------------------------------

Generating a truly random permutation in O(n log n) time using O(n log n) truly random bits;

Lectures on September 11

---------------------------------

The DCEL (doubly coupled edge list) data structure for planar maps, trapezoidal decomposition of the map of n segments in the plane.

Lectures on September 15 and 17

---------------------------------

Definition of t-wise independence and the proof of t-wise independence of pseudo-random numbers generated by the linear congruential generator; the randomized incremental algorithm for computing planar maps;

Lectures on October 6 and 8

---------------------------------

Expected values of $a$th order conflict changes for truly random insertion sequences and pseudo-random insersion sequences, for bounded degree configuration spaces.

Lecture on October 13

---------------------------------

Applications of the main lemma- reducing the number of truly random bits using the linear congruential generator for preserving the asymptotic expected running time for sorting and planar map computations.

Lectures on October 15

---------------------------------

Trivial configutation spaces, configuration space of raquets with maximum degree 6, viewing planar map building costs as first-order conflict changes over insertion sequences for raquet and trivial configuration spaces.

Applying the main lemma for such spaces to argue the asymptotic expected running time bounds with pseudo-random sequences with enough ideally random seeds.

The slot on October 23 will be compensated in an extra hour.

---------------------------------

Lecture on October 20

---------------------------------

Simulations of Turing Machines using conventional programming languages and boolean circuits, the class P and the simulation of deterministic polynomial time TMs with boolean circuits whose construction is done in logspace, the circuit value problem and P-completeness (see Papadimitriou, 1994, and my handouts).

------------------------------------

Assignment 2: October 21/10/2003

Submission by Nov 10, 2003. ------------------------------------

(i) Show the logspace reducibilities between REACHABILITY, 2SAT and CIRCUITVALUE problems.

*(ii) Show that the problem of determining whether a context-free grammar generates an empty language is P-complete (see Hopcroft and Ulmann, 1979).

(iii) Show that Knapsack and Halmiltonian problems are NP-hard.

(iv) Show that Minimum Linear Arrangement and Maxcut are NP-hard.

------------------------------------

Lecture on October 22

---------------------------------

The detailed construction of the circuit for simulating a deterministic one-tape polynomial time TM in logspace, cascading logspace reductions.

Study exercises.

--------------------------------

Show that logspace reductions can be cascaded.

-------------------------------------

Lecture on October 27

---------------------------------

Random sampling, introduction to recursive randomized algorithms based on random sampling.

----------------------------------------------

Lectures on October 29

---------------------------------

The Grosso theorem on random sampling limiting the asymptotic (maximum) size of conflict sets, generalization of the theorem for configuration spaces of bounded valence.

----------------------------------------------

Lecture on October 30

---------------------------------

Randomized divide-and-conquer algorithms based on top-down random sampling for query data structures.

------------------------------------

Lecture on November 3.

---------------------------------

The notions of bounded degree, valence and dimension and their interrelationships.

-------------------------------------

Lectures on November 5.

---------------------------------

Range spaces and epsilon nets-- the dimension of a configuration (range) space, the main theorem showing the existence of epsilon nets for spaces of bounded dimension and their construction with high probability, example of 2-d upper half-planar ranges and the interpretation using geometric duality in the dual plane, the upper bound on the number of ranges due to a random sample.

-------------------------------------

Lecture on November 6.

---------------------------------

Half-planar range spaces and their dimensions, towards Vapnik-Chevronenkis dimension of a range space.

-------------------------------------

Lecture on November 10.

---------------------------------

Using epsilon nets for range queries with bounded VC dimensions.

------------------------------------

-------------------------------------

Lectures on November 12.

-----------------------------------

The probabilistic method: a probabilistic algorithm for a hypergraph colouring problem and its derandomization, the work of Raghavan in the mid eighties.

-----------------------------------

Class test (quiz) on November 13, 9:30am to 10:25 am on the entire syllabus.

--------------------------------------------

November 17, 9:30 am.

----------------------------------

Range queries and epsilon nets (continued), revising the probabilistic method and the consequent derandomization technique using the method of conditional probabilities, winding up and revision.

-------------------------------

---------------------------------

Intended further lectures

-----------------------

Generating a random sample--- lower bounds on the number of required truly random bits, different options in sampling- with and without repetitions;

Dynamic programming for shortest path trees in graphs.

Data structuring for graph and geometric problems;

Randomized algorithms-- randomized rounding, random sampling, incremental constructions;

Introduction to the theory of NP- and P- completeness and approximation algorithms;

Introduction to interactive protocol (games) for graph isomorphism and non-isomorphism.

---------------------------------------------

Intended lectures in October and November 2003

--------------------------------

Randomness, pseudo-randomness and techniques for derandomization;

Integer and linear programming in fixed dimensions; polynomial-time linear programming, semi-definite programming.

Geometric searching, e-nets, cuttings and simplex range searching.