HW1

Submit a single .pdf for the written problems and .java codes for the coding problems to me via email by the date of the deadline (11:59 pm)

(1) Please show ALL of your work (Step by Step). 

******************************************** Written ********************************************

1. [Written 10pt] A peasant finds himself on a riverbank with a wolf, a goat, and a head of cabbage. He needs to transport all three to the other side of the river in his boat. However, the boat has room for only the peasant himself and one other item (either the wolf, the goat, or the cabbage). In his absence, the wolf would eat the goat, and the goat would eat the cabbage. Solve this problem for the peasant or prove it has no solution. (Note: The peasant is a vegetarian but does not like cabbage and hence can eat neither the goat nor the cabbage to help him solve the problem. And it goes without saying that the wolf is a protected species.) 

2. [Written 12pt] For each of the following functions indicate how much time the function’s value will change if its argument is increased fourfold (e.g., look at the ratio). 

a. log_2 n    b. sqrt(n)     c. n     d. n^2    e. n^3    f. 2^n 

3. [Written 12pt] For each of the following pairs of functions indicate whether the first function of each of the following pairs has a lower, same, or higher order of growth (to within a constant multiple) than the second function.  (Hint: For c, check out the log base conversion formula)

a. n(n + 1) and 2000n^2         c. log_2 n and ln(n)         e. 2^{n−1} and 2^n

b. 100n^2 and 0.01n^3     d. log_2^2 n and log_2 n^2     f. (n−1)! and n! 

Note: log_2^2 n can be viewed as (log_2 n)^2 

4. [Written 10pt] Show that Big Oh relationships are transitive. That is, if f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) = O(h(n)).

5. [Written 10pt] Consider the MinDistance algorithm (see below) for finding the distance between the two closest elements in an array of numbers. What is the algorithm's time complexity? Can you make it faster? If so, how? 

6. [Written 10pt] You have n > 2 identical-looking coins and a two-pan balance scale with no weights. One of the coins is a fake, but you do not know whether it is lighter or heavier than the genuine coins, which all weigh the same. Design an O(1) algorithm to determine whether the fake coin is lighter or heavier than the others.

7. [Written 10pt] Compute the sums (using summation)  below. 

8. [Written 8pt] Consider the Mystery algorithm (below).  

a. What does this algorithm compute?

b. What is its basic operation?

c. How many times is the basic operation executed (Hint: You only need to consider the main one)?

d. What is the efficiency class of this algorithm (Hint: You should measure the efficiency with respect to the input representation)? 

9. [Written 10pt] Consider the algorithm that starts with a single square and on each of its n iterations adds new squares all around the outside. How many one-by-one squares are there after n iterations? The results for n = 0, 1, and 2 are illustrated below.

Hint: Write out the number of additional squares you obtain after n=0, n=1, n=2, ... and sum all of them up. Keep trying different values of n (sequentially) until you see a pattern that can help you construct the summation. 

10. [Written 8pt] Solve the following recurrence relations. 

a. x(n) = x(n−1)+5     for n>1, x(1)=0 

b. x(n) = 3x(n−1)       for n>1, x(1)=4 

c. x(n) = x(n−1)+n     for n>0, x(0)=0 

d. x(n) = x(n/2)+n      for n>1, x(1)=1    (solve for n = 2k)

11. [Written 10pt] Consider the below recursive algorithm for computing the sum of the first n cubes:  S(n) = 13 + 23 + . . . + n3.

a. Set up and solve a recurrence relation for the number of times the algorithm’s basic operation (i.e., multiplication) is executed. 

b. How does this algorithm compare with the straightforward nonrecursive algorithm for computing this sum?

******************************************** Coding ********************************************

1. [Coding 10pt] Design an algorithm for checking whether two given words are anagrams, i.e., whether one word can be obtained by permuting the letters of the other. For example, the words tea and eat are anagrams. Please include some test cases to verify the correctness of your algorithm.