Question

1. Suppose there is a point x in the middle of my block of cheese, and all of my n straight planar cuts must go through a single common point x. Then the number of pieces is smaller than the number without that restriction, but is still a cubic polynomial in n.

2. Suppose that a and b are each powers of 2, with a > b. Then the Euclidean Algorithm, on inputs a and b, will terminate after at most log₂ a steps.

3.

Recall that F(n) is the Fibonacci function defined by F(0) = 0, F(1) = 1, and F(n+1) = F(n) + F(n-1).

If I start the Euclidean Algorithm with inputs F(n+3) and F(n), for any n, it will terminate after about n/3 steps.

4. If we start the EA with any two three-digit numbers, it will finish with at most twelve divisions.

T or F questions TY :)

Answer 1

Sol.

part 2.

Euclidean algorithm

F(m,n){

if n==0 return m

if m=0 return n

F(m%n, m)

}

lets take an example where m = 128 , n=64

F(128,64) => F(128%64, 128) => F(0,128)

So, if both n and m are power of 2 then EA will terminate in next iteration because 2^xmod2^y = 0 .

False becuase it will take O(1) time to terminate in case of power of 2.

Part 3.

F : 0 1 1 2 3 5 8 13

n : 0 1 2 3 4 5 6 7

lets take n = 2

F(2) = 1 , F(5) = 5

GCD(5,1) => GCD(1,0) => return

n = 3

F(3) = 2 , F(6) = 8

GCD(8,2) => GCD(2,0) => return

SO, the upper bound of euclidean algo will be Log(n or m can take any) => Log(n) here base does not matter becuase every time we are dividing by different number so T(n) = O(logn) but in power of 2 it will be O(1).So from here we can say that taking n/3 steps to execute EA is com[pletely a guess. SO FLASE

PART 4.

we have seen that algorithm will take atmost log(n) steps to terminate so guessing the 12 division is wrong.

SO False

Part 1.

cutting cheese problem will take polynomial time i can not reduce so TRUE.