15-251Great Theoretical Ideas in Computer ScienceforSomeReview SessionWean 7500Saturday @ 1pmPizza will be served!Rules of the GameEach person will have a unique numberFor each question, I will first give the class time to work out an answer. Then, I will call three different people at randomThey must explain the answer to the TAs (who are all the way in the back). If the TAs are satisfied, the class gets points. If the class gets 1,700 points, then you winGCDDEFINITIONALGOPROPERTIESGCDALGORITHMCONVER-GENTSEXAMPLESRUNNING TIMEANALGORITHM400300200100100200300400CONTINUEDFRACTIONS1. The Greatest Common Divisor (GCD) of two non-negative integers A and B is defined to be:2. As an example, what is GCD(12,18) and GCD(5,7)The largest positive integer that divides both A and BGCD(12,18) = 6GCD(5,7)=1A Naïve method for computing GCD(A,B) is:Give an algorithm to compute GCD(A,B) that does not require factoring A and B into primes, and does not simply try dividing by most numbers smaller than A and B to find the GCD. Run your algorithm to calculate GCD(67,29)Factor A into prime powers. Factor B into prime powers.Create GCD by multiplying together each common prime raised to the highest power that goes into both A and B.Euclid(A,B) = Euclid(B, A mod B)Stop when B=0Euclid’s GCD algorithm can be expressed via the following pseudo-code: Euclid(A,B)If B=0 then return Aelse return Euclid(B, A mod B)Show that if this algorithm ever stops, then it outputs the GCD of A and BGCD(A,B) = GCD(B, A mod B)( d | A and d | B ) ( d | (A - kB ) and d | B )The set of common divisors of A, B equalsthe set of common divisors of B, A - kBProof:Show that the running time for this algorithm is bounded above by 2log2(max(A,B))Proof:Claim: A mod B < ½ AIf B = ½ A then A mod B = 0If B < ½ A then any X Mod B < B < ½ AIf B > ½ A then A mod B = A - B < ½ AEuclid(A,B) = Euclid(B, A mod B)Stop when B=0GCD(A,B) calls GCD(B, <½A)Proof of Running Time:which calls GCD(<½A, B mod <½A)Every two recursive calls, the input numbers drop by halfDAILY DOUBLEA simple continued fraction is an expression of the form:a +b +c +d +e + …1111Where a,b,c,d,e, … are non-negative integers. We denote this continued fraction by [a,b,c,d,e,…]. What number do the fractions [3,2,1,0,0,0,…] (= [3,2,1]) and [1,1,1,0,0,0,…] (= [1,1,1]) represent? (simplify your answer)Let r1= [1,0,0,0,…]r2= [1,1,0,0,0,…]r3= [1,1,1,0,0,0…]r4= [1,1,1,1,0,0,0…]::Find the value of rnas a ratio of something we’ve seen before (prove your answer)rn= Fib(n+1)/F(n) Fib(n+1)Fib(n)Fib(n)+Fib(n-1)Fib(n)= 1 + 1Fib(n)Fib(n-1)=Let = [a1, a2, a3, ...] be a continued fractionDefine: C1= [a1,0,0,0,0..] C2= [a1,a2,0,0,0,...] C3= [a1,a2,a3,0,0,...] :Ckis called the k-th convergent of is the limit of the sequence C1, C2, C3,…A rational p/q is the best approximator to a real if no rational number of denominator smaller than q comes closer to Given any CF representation of , each con-vergent of the CF is a best approximator for 1317115111292111111121 ....C1= 3C2= 22/7C3= 333/106C4= 355/113C5 = 103993/33102C6=104348/33215 Find best approximators for with denominators 1, 7 and 1131. Write a continued fraction for 67/29 2 +3 +4 +21112. Write a formula that allows you to calculate the continued fraction of A/B in 2log2(max(A,B))
View Full Document
Unlocking...