COMPSCI 170 Study Guide - Midterm Guide: The Algorithm, Universal Hashing, Bmw I8
Document Summary
1 true/false: the mayan base 20 system produces representations of size that is asymptotically di erent from that of decimal (base 10) system. Solution: false log20(n) = number of digits using base 20 and log10(n) = number of digits using base: log20(n) (log10(n), if f (n) = o(g(n)), then there is some value of n where f (n) g(n). Solution: true f (n) cg(n) = log f (n) log g(n) + log c 2 log c log g(n: if f (n) = o(g(n)), then 2f (n) = o(2g(n)). Solution: false consider f (n) = n and g(n) = n/2: x(p 1)(q 1) = 1 (mod pq) for all x 6= 0 (mod pq) if p and q are distinct primes. Solution: false this implies that x has an inverse mod pq and that gcd(x, pq) = 1, which would not be true if x = p: x(p 1)(q 1)+1 = x (mod pq) if p and q are distinct prime.
