Algorithms and data homework help

Question

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

b=1

Fori from1to2n b=b·a

(u,v)←F(a,n−1) Return (u · b/ a, v · b · a)

1. (a) What are the results of F(a,3), F(a,4), and F(a,5). You do not need to justify your answers.
2. (b) What does the code do in general, when given input integer n ≥ 0? Prove your assertion
3. 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.

1. Ifn=1,thelistis0,1.
2. 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.
3. 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.
4. (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.
5. Problem 3. (7 points) Reconstructing a total order
6. 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.)

2

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.)

Problem 4. (5 points) Use induction to prove that logarithmic functions are “smaller” than polynomials In class we assert without proof that “logarithmic functions are smaller than polynomials.”

Specifically, that (log2 n)a = O(nb) for every a > 0 and b > 0. In this problem you will use √

induction to prove a special case of this fact, that log2 n = O( n).

First prove by induction that, for every k≥2 k ≥ 4, log (2 ) ≤ 2

. Then, prove that log2n ≤ 2n for all n ≥ 1 by using the fact that log2n is at most log2(2k) for the smallest

√

integer k such that n ≤ 2 .

k

Problem 5. (3 × 4 = 12 points) Growth of functions

For each of these parts, indicate whether f = O(g), f = Ω(g), or both (i.e., f = Θ(g)). In each case, give a justification for your answer. Your justification can be in the form of a proof from first principles or a proof using limits, and can use any of the facts presented in the lecture or the text. (Hint: It may help to plot the functions and obtain an estimate of their relative growth rates. In some cases, it may also help to express each function as a power of 2 and then compare.)

nn (a) f(n)=n2 ;g(n)=3 .

4/3 (b) f(n)=nlogn;g(n)=n .

√ (c) f(n)=10n+(logn)2;g(n)=100n−8 n.

Problem 6. (4 + 4 = 8 points) Properties of asymptotic notation

Let f (n) and g(n) be asymptotically positive and monotonically increasing functions.

1. (a) Defineh(n)=max{f(n),g(n)},foralln≥0.Provethatf(n)+g(n)=Θ(h(n)).
2. (b) Let a be an arbitrary positive real number. Prove that if f (n) = O(g(n)), then f (n)a is O(g(n)a).

Answer 1

For problem 1, the problem is missing data...

What is the value of A that is passed?

if the for loop inside the else or not?

What is this function supposed to return?

You are returning an ordered pair, or are you

trying to recursively call F(1,a)

Problem 2: do a digit radix sort

Problem 3: sort the list by the second coordinate

Problem 4:

N is an integer, as it represents the size

of the array, so it cannot be zero, it is base 2 logs.

N=1 --> log(N) = 0 <= 1 = N

N=2 --> log(2) = 1 < 2= N

Suppose log(n) < n for some positive integer n>1 ,

as the given induction hypothesis

N>1 then 1> 1/n ---> 1 - 1/n>0

Then

F(n) = n - log(n) > 0 by induction hypothesis

F'(n) = 1 - 1/n > 0