15 251 Some Great Theoretical Ideas in Computer Science for Review Session Saturday 1pm Wean 7500 Pizza will be served Rules of the Game Each person will have a unique number For each question I will first give the class time to work out an answer Then I will call three different people at random They 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 win 400 RUNNING TIME 400 AN ALGORITHM 300 300 200 200 100 100 ALGO PROPERTIES GCD ALGORITHM GCD DEFINITION CONVERGENTS EXAMPLES CONTINUED FRACTIONS 1 The Greatest Common Divisor GCD of two non negative integers A and B is defined to be The largest positive integer that divides both A and B 2 As an example what is GCD 12 18 and GCD 5 7 GCD 12 18 6 GCD 5 7 1 A Na ve method for computing GCD A B is 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 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 Euclid A B Euclid B A mod B Stop when B 0 Euclid s GCD algorithm can be expressed via the following pseudo code Euclid A B If B 0 then return A else return Euclid B A mod B Show that if this algorithm ever stops then it outputs the GCD of A and B GCD A B GCD B A mod B Proof d A and d B d A kB and d B The set of common divisors of A B equals the set of common divisors of B A kB Euclid A B Euclid B A mod B Stop when B 0 Show that the running time for this algorithm is bounded above by 2log2 max A B Claim A mod B A Proof If B A then A mod B 0 If B A then any X Mod B B A If B A then A mod B A B A Proof of Running Time GCD A B calls GCD B A which calls GCD A B mod A Every two recursive calls the input numbers drop by half DAILY DOUBLE A simple continued fraction is an expression of the form 1 a 1 b 1 c 1 d e Where 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 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 rn as a ratio of something we ve seen before prove your answer Let rn Fib n 1 F n Fib n 1 Fib n Fib n Fib n 1 Fib n 1 1 Fib n Fib n 1 Let a1 a2 a3 be a continued fraction Define C1 a1 0 0 0 0 C2 a1 a2 0 0 0 C3 a1 a2 a3 0 0 Ck is 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 convergent of the CF is a best approximator for 1 3 1 7 1 15 1 1 Find best approximators for with denominators 1 7 and 113 C1 3 C2 22 7 C3 333 106 C4 355 113 C5 103993 33102 C6 104348 33215 1 292 1 1 1 1 1 1 1 2 1 1 Write a continued fraction for 67 29 1 2 1 3 4 1 2 2 Write a formula that allows you to calculate the continued fraction of A B in 2log2 max A B steps A A B B 1 B A mod B
View Full Document
Unlocking...