(For problems 1 - 12 gaalis > suban; for problems 13 - 17 gaalis > rohitk)

- 1.
- Prove that all all natural numbers of the form
*n*+ 2^{3}*n*are divisible by 3. - 2.
- Suppose we have coins of two different denominations, 3 paise and
5 paise. Show that it is possible to make up exactly any postage
of 8 paise or more using stamps of these two denominations.
In other words show that every positive integer is
expressible as
*n*= 3*i*+ 5*j*where . - 3.
- Let be the Fibonacci
sequence where for all ,
*F*_{n}=*F*_{n-1}+*F*_{n-2}. Let . Show that for all positive*n*. - 4.
- Prove the following statement using
**PMI**: If a line of unit length is given, then a line of length can be constructed using*ruler and compass*for every positive integer*n*. - 5.
- Prove by
**PMI**, that every integer*n*> 1 is either a*prime*or a*product of primes*. - 6.
- Consider the following
*tiling*problem. You are given a board with*m*squares in each row and*m*squares in each column where*m*is a power of 2. One arbitrary square on the board is distinguished as*special*. You are also given a supply of tiles, each of which looks like a board with one square removed (L shaped). Your puzzle is to cover the board with these tiles so that each square is covered exactly once, with the exception of the*special*square, whic is not covered at all. Such a covering is called a*tiling*. Show, using**PMI**, that the*tiling*problem can always be solved. - 7.
- Consider the following algorithm:

Prove that the above algorithm computes*n*for . Estimate the number of steps required as a function of^{2}*n*. - 8.
- Consider the following algorithm:

Prove that the above algorithm computes*x*^{n}for all and all . Also show that the number of steps required is bounded by . - 9.
- Consider the following algorithm for computing the
*maximum*and*minimum*element in an array*S*of size . Assume that*n*is a perfect power of two. Let*T*(*n*) be the total number of comparisons required to compute the above function. Clearly,*T*(2) = 1, and to solve a problem of size*n*we have to solve two sub-problems of size*n*/2 and carry out two additional comparisons. Thus, we have the following recurrence for*T*(*n*): Show that at least (3*n*/2) -2 comparisons are necessary. - 10.
- Solve the following recurrences. Try to obtain tight asymptotic
upper and lower bound in each case. (Can the tutors please
explain
*O*, , ,*o*, , ...?). Assume, in each case,*T*(*n*) is constant for .- (a)
- (b)
- (c)
- (d)
- (e)
- (f)
- (g)

- 11.
- Find the number of ways for a rook to move from the southwest corner of a chessboard to the northeast corner by moving one square at a time eastward or northward only. Note that rook is a chesspiece that can move horizontally and vertically on a chessboard.
- 12.
- Suppose you have an infinite supply of coins of denomination
50
*p*, 25*p*, 10*p*, 5*p*and 1*p*. In how many ways can you generate change for a given amount, say Rs. 1/- = 100*p*. Given that a function*d*(*n*) is available which gives the denomination of the*n*^{th}type of coin, develop a recursive algorithm to count the number of ways to generate change for a given amount. What can you say about the number of steps required for the computation? - 13.
- In to how many regions is the plane divided by
*n*straight lines in general position (no two parallel, no three concurrent)? How many of the regions are bounded? - 14.
- Suppose there are
*n*points on a circle. We draw all chords between those points. Suppose that no three of these chords pass through a single point. How many regions do these chords divide the interior of the circle in to ? - 15.
- In a sufficiently large set,
*n*subsets are chosen. What is the maximum number of sets that can be formed from these*n*sets using (for example) intersection and complementation? What does "sufficiently large" mean? - 16.
- If every two cities are joined by a one-way road, then is it
possible to find a starting city
*C*and a route from*C*that passes through every city exactly once? - 17.
- In an ancient village, there were some green-eyed and blue-eyed
persons. One fine day, God instructed them, "the day on which you
come to know that you are a green-eyed, you should commit suicide
..." He also assured them that there was at least one green-eyed
among them. Well, all the villagers were very intelligent and
strict followers of God. But, no one knew colour of his own eyes!
They didn't have mirrors. They couldn't even communicate with
each other. All that they could do is to see colour of other's
eyes. It happened that on 20
^{th}day, all the green-eyed people committed suicide. So, how many green-eyed were there ?