# Algorithms and data help!

+1 vote
17 views

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

+1 vote

So... what kind of "help" do you want?

a.  you tell us what you've done so far and where and why you are stuck and want a little direction, a tiny shove to get you to the right track

b. you're completely lazy and worthless and want someone here to do your work for you

by (756,620 points) 1 flag
0

No need to be an ass

0

Let me see if I understand you here...

YOU come on here posing a question, saying you need help.  *I* suggest that if you don't let us know what kind of help you need and how much work you have done on the question by trying to do the answer yourself...

and I imply that if you DON'T try to do at least SOME of your own work, you're a lazy, worthless mass of human flesh...

Now, the NORMAL person would say, "Gee, I should let them know exactly where I need the help."

But YOU.... lol  YOU.... YOU call ME an ass????   Hahahahahahaha!!!!! That's rich!

BUT WAIT.... maybe I misunderstood your reply.  MAYBE you meant there was no need for YOU to have been an ass...

If that's the case, I take back my remarks above and forgive you.  So... let us know what work you HAVE done, and we'll try to help you out.  Peace.

+1 vote

Function homework

{

a = 'easy'

b = 'difficult'

c = 'assignment'

d = 'cheating'

if c = a then

d = 'minimal'

else c = b

d = 'post on AO-R'

end

}

by (3,902,671 points)