Description
1) We are given twelve coins and one of them is a counterfeit but we do not know if it is
heavier or lighter. Determine which one is a counterfeit and if it is lighter or heavier
by weighing coins on a pan balance three times only.
Hint: divide and conquer; note that you can reuse coins that are established not to be
counterfeit!
2) n thieves have robbed a warehouse and have to split a pile of items without price tags
on them. How do they do this in a way that ensures that each thief believes that he has
got at least as much as any of the two remaining thieves?
3) Tom and his wife Mary went to a party where nine more couples were present. Not
every one knew everyone else, so people who did not know each other introduced
themselves and shook hands. People who knew each other from before did not shake
hands. Later that evening Tom got bored, so he walked around and asked all other
guests (including his wife) how many hands they had shaken that evening, and got 19
different answers. How many hands did Tom shake?
4) In Elbonia all cities have a circular one-way highway around the city; see the map.
All streets in the cities are one-way, and they all start and end on the circular highway
(see the map).
A city block is a part of the city that is not intersected by any street. Design an
algorithm that, given a map of a city, finds a block that can be circumnavigated while
respecting all one-way signs.
2
5) There are five pirates who have to split 100 bars of gold. They all line up and proceed
as follows:
i) The first pirate in line gets to propose a way to split up the gold (for example:
everyone gets 20 bars)
ii) The pirates, including the one who proposed, vote on whether to accept the
proposal. If the proposal is rejected, the prate who made the proposal is killed.
iii) The next pirate in line then makes his proposal, and the 4 pirates vote again. If
the vote is tied (2 vs 2) then the proposing pirate is still killed. Only majority
can accept a proposal. The process continues until a proposal is accepted or
there is only one pirate left. Assume that every pirate :
iv) above all wants to live;
v) given that he will be alive he wants to get as much gold as possible;
vi) given maximal possible amount of gold, he wants to see any other pirate
killed, just for fun;
vii) each pirate knows his exact position in line;
viii) all of the pirates are excellent puzzle solvers.
Question : What proposal should the first pirate make?
Hint: By recursion. Assume first that there are only two pirates, and see what happens.
Then assume that there are three pirates and that they have figured out what happens if
there were only two pirates and try to see what they would do. Further, assume that there
are four pirates and that they have figured out what happens if there were only three
pirates, try to see what they would do. Finally assume there are five pirates and that they
have figured out what happens if there were only four pirates. The assumption that the
pirates are excellent puzzle solvers is important!
6)
a) Describe an Θ(n log2(n)) algorithm (in the sense of the worst case performance)
that, given an array S of n integers and another integer x, determines whether or
not there exist two elements in S whose sum is exactly x.
b) Describe an algorithm that accomplishes the same task, but runs in Θ(n) average
(i.e., expected) time
Note that brute force does not work here, because it runs in Θ(n2
) time.
7) Read what RADIX SORT is on pages 170-173, and then describe an algorithm which
sorts n numbers smaller than n
7
in time O(n). (Hint: Think of numbers represented in
base n rather than binary or base ten. You can make enough “numerals” for such a
base using the standard base 10 numbers plus a single special symbol to provide
proper interpretation.)
8) Given n real numbers x1,…,xn where each xi is a real number in the interval [0, 1],
devise an algorithm that runs in linear time and that will output a permutation of the n
numbers, say y1, …., yn, such that ∑ n
i=2 |yi – yi-1| < 2.
3
(Note: this is easy to do in n log n time: just sort the sequence in an ascending order.
In this case ∑ n
i=2 |yi – yi-1| = ∑ n
i=2 (yi – yi-1) = yn – y1 ≤ 1 – 0 = 1. Here
|yi – yi-1| = yi – yi-1 because all differences are positive, and all terms in the sum but
the first and the last one cancel out. To solve Problem 3 one might think about the
Bucket Sort algorithm.)
9) Suppose that you are taking care of n kids, who took their shoes off. You have to take
the kids out and it is your task to make sure that each kid is wearing a pair of shoes of
the right size (not necessarily their own, but one of the same size). All you can do is
to try to put a pair of shoes on a kid, and see if they fit, or are too large or too small;
you are NOT allowed to compare a shoe with another shoe or a foot with another
foot. Describe an algorithm whose expected number of shoe trials is O(n log n)
which properly fits shoes on every kid.
10) Given two arrays of n integers, design an algorithm that finds out in Θ(n log2(n))
steps if the two arrays have an element in common. (Microsoft interview question)
11) Given an array A[1..100] which contains all natural numbers between 1 and 99,
design an algorithm that runs in O(n) and returns the duplicated value. (Microsoft
interview question)
12) On a circular highway there are 11 petrol stations, unevenly spaced, each containing a
different quantity of petrol. It is known that the total quantity of petrol on all stations
is enough to go around the highway once, and that the tank of your car can hold
enough fuel to make a trip around the highway. Prove that one can pick one of the
stations as a staring point, take the fuel from this station and make a trip around the
highway never emptying the tank before reaching the next station to refuel.
13) Determine if f(n) =Ω (g(n)) , f(n) =Θ(g(n)) or f(n) =O(g(n)) for the following pairs:
f(n) g(n)
n
2 (n – 2 log(n))(n + cos(n))
(log(n))2 log(nlog(n)
) + 2 log(n)
n(1+sin (πn/2))/2 √n (a plot might help)
P.S. Do NOT use Google to find solutions. The goal is to PRACTICE the hard way, so
do not give up easily!!! Enjoy!
Extended classes 3821 and 9801 only
14) Show that in the third case of the Master Theorem condition f(m)=Ω(�!”#!!!!)
follows from the condition a f(n/b)< c f(n) for some 0<c<1.
15) We have seen that for the recurrence T(n)= 2 T(n/2) + n log n the Master Theorem
does not apply. Use the method from the proof of the Master Theorem to estimate the
asymptotic behavior of T(n) satisfying this recurrence.
