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).