Homework 7 (assigned August 4, due August 9)

Reading: Rosen chapter 7, sections 7.1–7.3.

Written assignment : Solve the following "Do" exercises and assigned problems. Only solutions to the assigned problems should be turned in. Note: You are responsible for the material covered in both "Do" exercises and assigned problems.

"Do" Exercises (not to be handed in):

1. Find the closed form for the nth Fibonacci number defined by the following recurrence.
   F₀ = 0,
   F₁ = 1,
   F_n = F_{n − 1} + F_{n − 2}   (n ≥ 2).
   Use Theorem 1, section 7.2.

2. The Josephus problem is a problem based on an account by the historian Flavius Josephus, who was part of a band of rebels captured by the Romans during a first century A.D. war. The rebels decided to form a circle and to count off around the circle, killing every third rebel left alive. Josephus did not want to be killed in this way and calculated where he should stand in the circle to remain alive. The variation of the problem we consider begins with n people numbered 1 to n around a circle; we eliminate every second remaining person until only one survives. We denote the number of the survivor by J(n).
   For example, here is the starting configuration for n = 10. (Draw in the numbers from 1 to 10 clockwise, starting at the top.)
   
   • What is the elimination order? (Write out the list of numbers in order.) What is J(10)?
   • We might conjecture that J(n) = n/2 when n is even. Determine the value of J(n) for each integer n with 1 ≤ n ≤ 6. Do the data support this conjecture?
   • Suppose that we have 2n people originally. After the first pass around the circle, what is the number, in terms of n, of the last person remaining? What is the number of the next person to go, on the second pass around the circle? Write a recurrence for J(2n) in terms of J(n).
   • Suppose that we have 2n + 1 people originally. On the first pass around the circle, what is the number of the last person eliminated? What is the number of the next person to go, on the second pass around the circle? Write a recurrence for J(2n + 1) in terms of J(n).
   • What is J(1)? Write a recurrence that defines J in all cases.
   • Find a closed form for J. Hint: Determine the value of J(n) for each integer n with 1 ≤ n ≤ 16. Build a table of these values. Conjecture a formula for J(n) based on these values.
   • Prove that your closed form for J is correct by mathematical induction.
   • Compute J(100) from your formula.

Assigned problems (to be handed in):

1. At the start of each year, $100 is added to a savings account. At the end of each year, interest equal to 5% of the amount in the account is added by the bank. Let A(n) be the amount of money in the account after the interest payment in the nth year.
   1. Find a recurrrence for A(n). Include the initial condition. (3 points)
   2. Solve the above recurrence, i.e., find a closed form for A(n). (2 points)

2. A diagonal in a polygon is a line segment from one vertex to another nonadjacent vertex. For example, a triangle has no diagonals because each vertex is adjacent to the other vertices. A square has two diagonals.
   1. Find a recurrence for D(n), the number of diagonals in an n-sided polygon. State the initial condition. Analyze the problem and explain your recurrence. (5 points)
   2. Solve the recurrence from part (1) to obtain a closed form for D(n). (2 points)

3. In the Tower of Hanoi problem, suppose our goal is to find the minimum number of moves required to transfer all n disks from peg 1 to peg 3 if direct moves between peg 1 and peg 3 are disallowed; i.e., each move of a disk must be to or from peg 2. As usual, a larger disk can never be placed on top of a smaller disk.
   1. Find a recurrence for the number of moves required to solve the Tower of Hanoi problem for n disks with this added restriction. Include the initial condition. (5 points)
   2. Solve the recurrence from part (1) to obtain a closed form. (5 points)
   3. How many different arrangements are there of the n disks on 3 pegs so that no larger disk is on top of a smaller disk? (5 points)
   4. Show that, in the process of transferring the tower of n disks from peg 1 to peg 3 under the restricted version this problem, we will actually encounter every properly stacked arrangement of n disks on 3 pegs. (5 points)

4. Consider a staircase with n stairs. How many ways are there to ascend the staircase, if we can climb by 1 stair or 2 stairs in each step? In other words, how many ways are there to write the number n as a sum of 1's and 2's? Let S(n) denote the number of such solutions. Find a recurrence for S(n). Give the initial conditions. (5 points)

5. Determine the number of bit strings of length n that contain the string 01. Express your formula as a recurrence and state the initial conditions. Use your formula to compute the number of such strings of length 5. (8 points)

6. The following algorithm finds the largest and smallest numbers in a set of n numbers. If n = 2, compare the two numbers. If n > 2, (a) split the numbers into sets of sizes floor(n/2) and ceiling(n/2); (b) apply the algorithm recursively to determine the largest and smallest in each subset; (c) use the resulting numbers to compute the largest and smallest numbers in the original set.
   1. Let C(n) be the number of comparisons used on a set of size n. Obtain a recurrence for C(n). (5 points)
   2. Find a closed form for C(n) when n is a power of 2. (3 points)
   3. Compare your solution for C(n) to the closed forms obtained in class for the running times of Mergesort and Binary Search on inputs of size n. Which of these three algorithms is the fastest asymptotically? Which is the slowest asymptotically? (2 points)

7. Consider an n × n chessboard:
   

   Consider the shortest paths from the bottom left corner to the top right corner following the edges of the squares (each of them consists of 2n edges). How many such paths are there? For full credit you must analyze the problem and argue that your solution is correct. (10 points)