15-451 Algorithms 10/05/11 RECITATION NOTES * B-trees, Treaps: Go over mini * Hashing * Checking matrix multiplication ======================================================================= B-trees, Treaps: Go over questions from mini Hashing ======= - Recap universal hashing. - Do argument in 10.6.1 of the lecture notes for alternative universal hashing scheme using prime-number-sized tables. - cryptographic hash functions. For cryptographic hash functions, think of M as an exponentially large number, like 2^256. Now, we are not going to have a table (would be bigger than the # electrons in the universe!). Instead, we are just going to think of h(x) as a "fingerprint" of x. In particular, think of x as something like a document or a file or a computer program or a movie. [Note, even though M is big like 2^256, the indices h(x) are fairly small -- e.g., only 256 bits (32 bytes)] The main property you want for a cryptographic hash function is that given x, it should be computationally intractable for anyone to find y!=x such that h(y)=h(x). That way you can use h(x) as a public certificate of x. E.g., think of downloading a computer program. If you have h(x), and then download a program z that is purported to be x, you can verify that h(z)=h(x) and be confident that z=x (e.g,, nobody has inserted a virus into the program). Even better, it should be computationally intractable to even find *any* distinct x,y such that h(x)=h(y). Note: we know by the pigeon-hole-principle that there will *exist* pairs that collide (so long as the universe is big enough, like 80-character strings). But the key point is you want it to be hard to find them. Checking matrix multiplication ============================== How can we check that a program correctly computes the product of two nxn matrices A,B? Say the program computes the answer C, and let's assume everything is over bits, mod 2. Here is one nice way to do it. We select a random n-bit column-vector r and check if ABr = Cr. Note that we can do this *fast*, without multiplying A with B, by writing ABr = A(Br). Claim: If AB != C then Pr(ABr = Cr) <= 1/2. (So, by doing this check with k randomly chosen r, the probability of detecting an error (like the probability of getting k Heads in a row of k coin tosses) is 1/2^k). Proof: 1. Let v and w be two distinct (different) n-bit vectors, like <0,1,0,1> and <1,1,0,0>. Let r be a random n-bit vector. Show that Pr(v*r = w*r) <= 1/2. Here * denotes standard vector dot product, and the probability is over all 2^n n-bit vectors r. 2. Let A and B be two distinct nxn matrices of 0s and 1s. Let r be a random n-bit column vector. Use (1) to show thatÂ Pr(Ar = Br) <= 1/2. As before, the probability is over all 2^n n-bit vectors r. Application: Suppose we want to check if B = A^{-1} (the inverse of A) without multiplying A and B. Idea: For k random column vectors r, just check that ABr = Ir (where I is the identity matrix, so Ir = r).