Consider a plate stacked with several disks, each of a different
diameter (they could all be, for instance, dosas or chapatis of different sizes). We want to arrange these disks in
decreasing order according to their diameter so that the widest disk
is at the bottom of the pile and every disk is smaller than the
disks below it.
The only operation available for manipulating the disks is to pick
up a stack of them from the top of the pile and invert that stack.
(This corresponds to lifting up a stack dosas or
chapatis between two big spoons and flipping the stack.)
Describe a precise method (algorithm) to sort the disks using
this flip operation.
What initial arrangement of n disks will force us to use the
flip operation the maximum number of times before the entire
pile is stacked up correctly?
A new test for tuberculosis is found to be 80% accurate--if a
person has the disease, the test is positive 80% of the time and if
a person does not have the disease, the test is negative 80% of the
time. A person is picked at random from a group in which 10% of
the people actually have tuberculosis.
If the randomly selected person's test result is positive,
what is the probability that he has tuberculosis?
If the randomly selected person's test result is negative,
what is the probability that he has tuberculosis?
In a normal pan balance (as used by, say, a vegetable vendor)
the item to be bought is balanced against a known combination of
weights. The weights may be applied on either side of the pan--for
instance, to weigh 1500 g of onions, the vendor may either place the
onions in one pan and a 1000 g and 500 g weight in the other, or
place the onions along with a 500 g weight in one pan and a 2000 g
weight in the other pan.
We would like to be able to weigh all quantities between 1 g and
4000 g to the nearest gram using such a balance. One way to do this
is to have 12 weights weighing 1 g, 2 g, 4 g, 8 g, 16 g,...,
2048 g.
Design a smaller set of weights to achieve the same objective.
In general, to weigh items between 1 g and
n g to the nearest gram, what is the smallest
sequence of weights we can use (in terms of n)?
Let A be a matrix of integers. Suppose we first arrange
each row in ascending order and then arrange each column in
ascending order. Show that the rows remain in ascending order
after rearranging the columns.
Let A be an n × n matrix of integers
such that each row and each column is arranged in
ascending order. we are told that a number k
appears in A and we would like to find out its
position--that is, the row i and column j
such that k.
Show that we can do this by examining at most 2n values
in A.
In what position should k be to force us to look at
2n values in A?
We have nballs that look identical but each of them has a
different weight. We have a balance in which we can weigh one
ball against another ball.
Describe an efficient method to find the heaviest ball. How
many weighings does the method require, in terms of n?
One way to find the second heaviest ball is to first find the
heaviest ball using the method from part (a), remove it from the
collection, and then find the heaviest among the remaining balls
using the same method. Describe a more efficient method to find
the second heaviest ball. How many weighings does the improved
method require, in terms of n?
We have a bucket full of marbles, some of which are black and
some of which are white. We also have a big sack with an unlimited
supply of black marbles.
We keep repeating the following step:
We close our eyes and pick out two marbles from the bucket at
random.
If both marbles are of the same colour, we throw away both of
them and put a fresh black marble from the sack into the bucket.
If the marbles are not of the same colour, we throw away the
black marble and replace the white marble back in the bucket.
With each step, the number of marbles in the bucket decreases by
one. Eventually, we are left with a single marble in the bucket.
What is the relationship, if any, between the colour of the last
marble and the contents of the bucket that we started with?