CSNumbertheoryv.ppt

* * * * * * * We’ll deal with summation notation in detail later. For now, explain what it means in this particular case. * * * * Have students write out pseudocode in class? * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Do another example on the board. * * * * * * * * * * * Put it somewhere else! - In open addressing, we have a rule to decide where to put it if the space is already occupied. Keep a list at each bin! - At each spot in the hash table, keep a linked list of keys sharing this hash value, and do a sequential search to find the one we need. This method is called chaining. Collision Resolution by Chaining The easiest approach is to let each element in the hash table be a pointer to a list of keys. ? Insertion, deletion, and query reduce to the problem in linked lists. If the n keys are distributed uniformly in a table of size m/n, each operation takes O(m/n) time. Chaining is easy, but devotes a considerable amount of memory to pointers, which could be used to make the table larger. Still, it is my preferred method. Open Addressing We can dispense with all these pointers by using an implicit reference derived from a simple function: If the space we want to use is filled, we can examine the remaining locations: Sequentially Quadratically Linearly * * * * * * Proof of Theorem 2 Theorem 2: If ac ≡ bc (mod m) and gcd(c,m)=1, then a ≡ b (mod m). Proof: Since ac ≡ bc (mod m), this means m | ac?bc. Factoring the right side, we get m | c(a ? b). Since gcd(c,m)=1 (c and m are relative prime), lemma 1 implies that m | a?b, in other words, a ≡ b (mod m). QED An Application of Theorem 2 Suppose we have a pure-multiplicative pseudo-random number generator {xn} using a multiplier a that is relatively prime to the modulus m. Then the transition function that maps from xn to xn+1 is bijective. Because if xn+1 = axn mod m = axn′ mod