Homework Help!

[johnnyzags]

Hey whats up guys?? I needed some help with some homework, and I wondered if anybody could provide me the answers to these questions. Thank you.

The following Algorithm will calculate the greatest common divisor of two numbers:

GCD (M, N)
M, N are the two integers of interest
GCD returns the interger greatest common divisor
if (M < N ) then
swap M and N
end if
if ( N = 0 ) then
return M
else
quotient = M/N //Note: integer division
remainder = M mod N
return GCD ( N, remainder )
end f

Give the reucrrence relation for the number of multiplications (in this case, the division and the mod) that are done in this function.


Put the following recurrence relaiton into closed form
T(n) = 3T(n-1)-15
T(1) = 8


And the last one.. if someone could help explain to me how to..
Draw the decision tree for the binary search algorithm for a list of 12 elements. For the internal nodes of your decision tree, the node should labeled with the element checked, the left child should represent what happens if the target is less than the element checked, and the right child should represent what happens if the target is greater than the element checked.



I really appreciate the help. This is my indepdent study and I am working on this final, but i am really not too good at it at all, so any help would be greatly appreciated!

[mehdi62b]

Give the reucrrence relation for the number of multiplications (in this case, the division and the mod) that are done in this function.this is euclid algorith,Function Euclid(m,m)
while m>0 do
t=m;m=n mod m; n=t;
return n;thats clear which every time n mod m is less than n/2 because

if m > n\2 : n mod m = n-m < n-n/2 < n/2
if m < n/2 : n mod m < m < n/2
so for every 2 executions of the cycle the n would become less than its half in which m also is less than n,so suppose if L is the number of executions of the cycle(m=n mod m) we would have this relation (L could be less or greator than 2 it could be less than 2 in conditionslike when one of the number ia zero or one if the is devisible by another one)

t(L) = is like bellow

1 if L<2
2+t(L div 2) otherwise
which is similar to Binarry search algorithm which would have the logaritimic order.
Put the following recurrence relaiton into closed form
T(n) = 3T(n-1)-15
T(1) = 8T(n)-3T(n-1)=-15 so (x-3)(x-1)=0
T(n)=C1 *3^n+C2 *1^n
T(1)=8 so T(2)=9 so
3C1+C2=8
9C1+C2=9
C1=1/6,C2=15/2

T(n)=1/6 *3^n+15/2