## 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.