Algorithm Design: Foundations, Analysis and Internet Examples by Michael T. Goodrich and Roberto Tamassia, John Wiley and Sons, Inc., 2002.
Data Structures and Algorithms: Volumes I, II and III by Kurt Mehlhorn, Springer-Verlag.
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.
K. Mehlhorn and S. Naher, LEDA: a Platform for Combinatorial and Geometric Computing, Cambridge, UK, Cambridge University Press, 1999.
Motwani and Raghavan, Randomized Algorithms. -----------------------------------------------
We will have all the four lectures from July 25, 2002 onwards.
Considerable stress will be given on class tests and home assignments. Some assignments would include using LEDA for implementing algorithms. Sound knowledge of elementary data structuring and progamming is required to register for this course. ----------------------------------------------------
First set of problems. (July 27, 2002)
(i) Consider computing the length of the longest (strictly) increasing subsequence in an unsorted sequence of numbers. Design an O(n^2) algorithm, where the input sequence is of length n. Improve the algorithm to get a running time of O(n log n). (Consider the sequence (11,2,13,22,14,13,24) of 7 numbers. The length of the longest subsequence for the prefix sequence (11) is 1, (11,2) is 1, (11,2,13) is 2, (11,2,13,22) is 3, (11,2,13,22,14) is 3, (11,2,13,22,14,13) is 3, and, finally for (11,2,13,22,14,13,24) is 4.)
(ii) Design an O(n^3) algorithm to cut an n-sided simple polygon in to two simple polygons, where the cut must be across a segment connecting two vertices and the segment must not intersect the exterior of the given polygon. Note that such a cut leaves two polygons, each of which might have 3 or more vertices. Design an O(n^4) algorithm to get a cut that leaves two polygons with roughly balanced numbers of vertices e.g., each of the two polygons may be required to have at most 2n/3 and at least n/3 vertices.
(iii) Let a(G) denote the size of the largest independent set in a graph G. Let k(G) denote the smallest number of complete subgraphs that cover the vertex set of G. Let w(G) denote the size of the largest complete subgraph in G. Let chi(G) denote the minimum number of colours required to properly colour the vertices of G. Give examples for (a) a connected graph G with 6 vertices such that either a(G) is not equal to k(G) or w(G) is not equal to chi(G), (b) a connected graph G of 7 vertices such that a(G)=k(G) and w(G)=chi(G).
(iv) Show that any algorithm that sorts n numbers using comparisons can not do so in O(n) (linear time) time in the worst case.
(v) Show that log(n!) is at least C times n * log n, for n>N, where N is an integer and C is a constant independent of n.
(vi) You are given an algorithm which determines the median of an unsorted set of n numbers in O(n) time. Show that using this algorithm, you can sort a set of n numbers in O(n log n) time.
(vii) Consider 2,4-trees. Suppose we start with an empty tree and perform n operations comprising searches and insertions in arbitrary order. The leaf nodes store the actual data and the internal nodes simply store the keys required for searching operations. Ignore costs incurred in search operations. Show that the remaining cost of maintaining the 2,4-tree during the course of the n operations adds up to O(n). Also show that each search operation (done starting at the root) requires O(log n) time.
---------------------------------------------------------------------------
Second set of problems
----------------------
17621
--------
(i) If n distinct objects are placed around a round table, determine the number of distinct arrangements possible. (Hint: If you arrange n distinct objects in a line then there are n! arrangements.)
(ii) Write a C program for generating all the n! permutations of the first n integers.
(iii) Find an upper bound for the sum 1+1/2+1/3+1/4+...+1/n.
(iv) Show by induction that the number of edges in an n-vertex tree is n-1.
(v) Write a program to generate all the partitions of an integer. The integer 4 has partitions 4, 3+1, 2+1+1, 2+2, 1+1+1+1.
(vi) Show that the space requirement for the recursive implementation of mergesort is proportional to the number of elements being sorted.
(vii) In how many ways can you select n items from a set of r distinct items if you are allowed to choose items repeatedly. If n=2 and r=3 then the possibilities are 6 in number viz., 11, 22, 33, 12, 13, 23. If n=3 and r=3 then we have 111, 222, 333, 112, 113, 122, 133, 123, 223, 233, in all 10.
(viii) Design a polynomial time algorithm for computing the size of the maximum sized independent set for a tree with n vertices.
August 1, 2002
--------------------------------------------------------------------------
AUGUST 25, 2002
The assignments to be submitted by August 31, 2002 to Mr. Ta or in CSE Office will include problems (iv), (v) and (vi) from the first set of problems above and all problems from the second set of problems above. Late submissions will suffer from penalties. All submissions must be neatly written in A4 sheets in lucid language and clean hand. Explanations must be complete, rigorous and to the point with proper flow of thought and analysis. ALL PERSONS ATTENDING THE COURSE MUST DO THESE ASSIGNMENTS.
Assignments to be submitted in hadcopy by Oct 29, 2002 FN, sharp deadline.
(i) 18.2.3 page 363, Cormen et al.
(ii) 16-1 page 324-325, Cormen et al.
(iii) 16.4-1, page 324, Cormen et al.
(iv) 16-3 page 325, Cormen et al.
(v) 13-4 page 262, Cormen et al.
(vi) 9-1 (d) page 183, Cormen et al.
(vii) 9.3-2 page 180, Cormen et al.
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------