## Description

1. Suppose that you and your friend are playing a game of guessing a number. At the

beginning, your friend writes down an integer x in the range [1, N]. Your goal is to

guess that number using the minimum number of guesses. Each time when you guess

a number, your friend will tell you whether the number you guess is equal to, less than,

or greater than the number x he initially sets. Once your guess equals x, the game

ends.

Describe a good strategy that you could use to guess the initial number using as few

number of guesses as possible. Suppose that N = 2m − 1. What is the number of

guesses required in the worst case? What is the number of guesses required on average? Give the exact value, not the big-oh, big-omega, or theta notation.

2. Consider the following code

while(n > 1)

{

if(n % 2 == 1)

n = 3 * n + 1;

else

n /= 2;

}

What is the best lower bound f(n) so that the complexity of the above code is in the

set Ω(f(n))?

3. Is the statement n

100 = O(1.001n

) true or not? Prove your answer in a strict way.

4. Prove the following result on the theta notation based on its definition:

Suppose that g1(n) and g2(n) are non-negative functions when n ≥ 0. If f1(n) =

Θ(g1(n)) and f2(n) = Θ(g2(n)), then f1(n)+f2(n) = Θ(h(n)), where h(n) = max{g1(n), g2(n)}.

1

5. Consider the following code

void func(int n, int a, int b) {

for(i = 1; i <= n; i *= a)
for(j = 1; j <= i * b; j++)
Statement;
}
Assume that n ≥ 1, a > 1, and b ≥ 1 are integers. How many times will “Statement”

be called? Write the answer in terms of n, a, and b.

6. A new house is being built down the street. The builders are currently working on

the roof. From observation, there seems to be three different methods for moving the

shingles from the shingle truck to the roof.

Method 1: A builder can carry two packages (known as squares) of shingles on his

shoulder as he climbs up the ladder. He then climbs down and carries two more

squares up the ladder. So on and so forth. Each round trip (up the ladder with

two squares and down the ladder with none) costs $2.

Method 2: A builder rents a lift for $10. The lift can move 20 squares up the roof at

one time at a cost of $1 per round trip.

Method 3: A builder rents a super-lift for $40. Unfortunately, the lift has a slow

leak in its hydraulic system. The lift is able to lift roughly half of the necessary

squares to the roof on the first round trip. However, on the second trip the lift

is only able to lift half of the remaining squares, then half of the remaining, and

so on. To be strict, if the number of the remaining squares is n, the lift lifts b

n

2

c

squares. Even when the super-lift has no hydraulic fluid left in its system, it can

still lift one square of shingles. Each round trip using the super lift costs $2.

Note that in all three methods, it costs $4/square to nail the shingles into the roof.

Question:

In the following questions, “cost” refers to total cost, including nailing shingles to the

roof.

(a) For each method, write a formula T(n) that expresses the number of round trips

required to move n squares of shingles to the roof.

(b) For each method, write a formula C(n) that expresses the entire cost to install n

squares of shingles on the roof.

(c) Which is cheapest method for a doghouse (8 squares)? How much does it cost?

(d) Which is cheapest method for a shed (128 squares)? How much does it cost?

(e) Which is cheapest method for a house (2048 squares)? How much does it cost?

2