COMP 280 Assignment 10

These problems total to 130 points.

For the problems from Rosen 6th ed. 3.2, your answers should be based upon the definitions of O(), Ω(), and Θ(). You may use either the definitions in the textbook or those that I gave in class.

When providing recurrence equations, always provide an explicit base case, even though it is common practice to leave that implicit.

1. (10 points) Rosen 6th ed. 3.2 #24d

   Show that log₂(x²+1) is Θ(log₂ x).

2. (10 points) Rosen 6th ed. 3.2 #26

   Show that if f(x) and g(x) are functions from the set of real numbers to the set of real numbers, then f(x) is O(g(x)) if and only if g(x) is Ω(f(x)).

3. (5 points) Rosen 6th ed. 3.2 #36

   Suppose that f(x) is O(g(x)). Does it follow that 2^f(x) is O(2^g(x))?

4. (5 points) Find a closed form for ∑_k=i…j (3k²-k+1).

5. (5 points) Consider the problem of checking whether all the elements in a given array are distinct. The following is an algorithm for this:

   for i = 0 to n-2
      for j = i+1 to n-1
         if A[i]=A[j] return false
   return true
   

   Write the summation formula for the maximum number of comparisons, and find its closed form.

6. (10 points) Show that ∑_k=0…∞ k²x^k = x(1+x)/(1-x)³ for 0<|x|<1.

7. (10 points) Rosen 6th ed. 4.1 #10a-b

   1. Find a formula for 1/(1×2) + 1/(2×3) + &hellip + 1/(n(n+1)) by examining the values of this expression for small values of n.
   2. Prove the formula you conjectured in part (a).

8. (10 points)

   Suppose that you have an unlimited supply of red, white, blue, green, and gold poker chips, which are indistinguishable except for color. Write recurrence equations defining s_n, the number of ways to stack n≥0 chips with no two consecutive red chips. Briefly explain your answer.

   (You are not asked to solve for a closed form, although you should be able to.)

9. (30 points — 5 points each parts a and c, 10 points each parts b and d) Rosen 6th ed. 7.2 #46abcd, reworded

   Suppose that there are two goats on an island initially. The number of goats on the island doubles every year by natural reproduction, and some goats are either added or removed each year.

   1. Construct a recurrence relation for the number of goats on the island at the start of the nth year, assuming that during each year an extra 100 goats are put on the island.
   2. Solve the recurrence relation from part (a) to find the number of goats on the island at the start of the nth year.

   On another island, we again start with two goats and double their number annually via reproduction. But we also remove n goats during the nth year for each n≥3.

   3. Construct a recurrence relation for the number of goats on this island at the start of the nth year.
   4. Solve the recurrence relation in part (c) for the number of goats on the island at the start of the nth year.

10. (25 points — 10 points each parts a and c, 5 points part b) A variation of Rosen 6th ed. 7.3 #18

    Suppose that each person in a group of n people votes for exactly two people from a slate of candidates to fill two positions on a committee. The top two finishers both win positions as long as each receives more than n/2 votes.

    1. Devise a divide-and-conquer algorithm that determines whether the two candidates who received the most votes each received at least n/2 votes and, if so, determine who thesese two candidates are.
    2. Use the Master Theorem to estimate the number of comparisons needed by the algorithm you devised in the previous part.
    3. Prove the same bound without using the Master Theorem.

11. (10 points) Rosen 6th ed. 7.3 #22b

    Suppose that the function f satisfies the recurrence relation f(n) = 2f(√n) + log n whenever n is a perfect square greater than 1 and f(2)=1.

    Find a big-O estimate for f(n). [Hint: Make the substitution m=log n.]