Discrete structures: Sample questions

6. A string that contains only 0s 1s and 2s is called a ternary string
a) find a recurrence relation for the number of ternary strings that contain two consecutive 0s
b) what are the initial conditions
c) how many ternary strings of length six contain two consecutive 0s

The next 3 problems deal with a variation of the Josephus problem described by Graham, Knuth, and Patashnik in [GrKnPa94].? This problem is based on an account by the historian Flauvius Josephus, who was part of a band of 41 Jewish rebels trapped in a cave by the Romans during the Jewish-Roman war of the first century.? The rebels pre-ferred suicide to capture; they decided to form a circle and to repeatedly count off around the circle, killing every 3rd rebel left.? However, josephus and another rebel did not want to be killed this way; they determined the positions where they should stand to be the last two rebels remaining alive.? The variation we consider begins with n people, numbered 1 to n, standing around a circle.? In each stage, every second person still left alive is eliminated until only one survives.? We denote the number of the survivor by J(n).

7) Determine the value of J(n) for each integer n with 1 <= n <= 16.? Use these values to conjecture a formula for J(n).? Hint: Write n=2^m +k, where m is a nonnegative integer and k is a nonnegative integer less than 2^m.

8) Show that J(n) satisfies the recurrence relation J(2n) = 2J(n) - 1 and J(2n+1) = 2J(n) + 1, for n >= 1, and J(1) = 1.

9) Use mathematical induction to prove that the formula you conjectured in exercise 50, making use of the recurrence relation from the previous exercise.

10) a. Assume that in the average case, the running time for Quicksort is f(n) = 2f(n/2)+ n. Use the Master Theorem to estimate its closed-form running time.

b. Do the same for Slowsort, whose running time is f(n) = 4f(n/2)+n.