Problem 1. (3 + 5 = 8 points) What Does This Code Do? You encounter the following mysterious piece of code.
Algorithm 1: Mystery Function
Function F(a,n)): If n = 0 :
Return (1,a) Else
Fori from1to2n b=b·a
(u,v)←F(a,n−1) Return (u · b/ a, v · b · a)
(a) What are the results of F(a,3), F(a,4), and F(a,5). You do not need to justify your answers.
(b) What does the code do in general, when given input integer n ≥ 0? Prove your assertion
by induction on n.
Problem 2. (5 + 5 = 10 points) Recursion and induction in binary codes
Digital transmission protocols transmit signals using binary codes. In order to minimize the effect of errors, protocols often use codewords for signals with the property that “similar” signals use “similar” codewords.
One such code is a list of 2n n-bit strings in which each string (except the first) differs from the previous one in exactly one bit. Let us call such a list a bit-flip list since we go from one string to the next by just flipping one bit.
Consider the following recursive algorithm for listing the n-bit strings of one such bit-flip list.
If n > 1, first take a bit-flip list of (n − 1)-bit strings, and place a 0 in front of each string. Then, take a second copy of the same bit-flip list of (n − 1)-bit strings, place a 1 in front of each string, reverse the order of the strings and place it after the first list.
For example, for n = 2, the list is 00,01,11,10, and for n = 3, we get 000,001,011,010,110,111,101,100. Prove the following two statements by induction on n.
(a) Every n-bit string appears exactly once in the list generated by the algorithm. (b) Each string (except the first) differs from the previous one in exactly one bit.
Problem 3. (7 points) Reconstructing a total order
A group of n runners finished a close race. Unfortunately, the officials at the finish line were unable to note down the order in which the racers finished. Each runner, however, noted the jersey number of the runner finishing immediately ahead of her or him. (There were no ties.)
The race officials ask each runner to give an ordered pair, containing two pieces of information: (a) first, his or her own jersey number and (b) second, the jersey number of the runner who finished immediately ahead of him or her. The winner of the race, who did not see anybody finish ahead of her, enters ⊥ for (b).
You have been asked to design an algorithm that takes as input the n pairs and returns the order in which the runners finished the race. Assume each runner is honest.
Give a deterministic Θ(nlogn) time algorithm, and justify the running time of the algorithm. (Hint: Use sorting.)