Homework 4 (assigned July 14, due July 17)

Reading: Rosen chapter 2, section 2.4.

Written assignment : Solve the following "Do" exercises and assigned problems. Only solutions to the assigned problems should be turned in. Note: You are responsible for the material covered in both "Do" exercises and assigned problems.

"Do" Exercises (not to be handed in):

1. Determine which of the following formulas define surjections from Z⁺ × Z⁺ to Z⁺.
   • f (a, b) = a + b.
   • f (a, b) = ab.
   • f (a, b) = ab(a + b)/2.

2. Consider f : A → B and g : B → A. Answer each of the following questions by providing a proof or a counterexample.
   • If f (g(y)) = y for all y ∈ B, does it follow that f  is a bijection?
   • If g(f (x)) = x for all x ∈ A, does it follow that f (g(y)) = y for all y ∈ B?

3. Prove that N × N has the same cardinality as N, where N is the set of natural numbers.

Assigned problems (to be handed in):

1. For any set A and a function f : A → A, the set F(f ) of fixed points is defined as follows.
   F(f ) = {x | x ∈ A ∧ f (x) = x}.
   For each of the following functions, find the set of fixed points and calculate the cardinality of this set. Assume that the set of natural numbers N = {0, 1, 2, …} is the domain and the codomain of all the functions. (2 points each)
   1. f₁(n) = 2n + 1
   2. f₂(n) = n² − 3n + 3
   3. f₃(n) = n³ − 24
   4. f₄(n) = 2ⁿ − 12
   5. f₅(n) = (−1)ⁿ ⋅ n

2. 1. If g o f  is an onto function, does g have to be onto? Does f  have to be onto? Prove or give a counterexample. (5 points)
   2. If g o f  is a one-to-one function, does g have to be one-to-one? Does f  have to be one-to-one? Prove or give a counterexample. (5 points)

   Prove that the function f : R → R defined by f (x) = xⁿ is strictly increasing when n is an odd natural number; R is the set of real numbers. Hint: Use induction on k to prove this for the power 2k − 1, k ≥ 1. Consider the cases x < 0 < x′, 0 < x < x′, and x < x′ < 0. (10 points)

   Let X = {1, 2, …, n}. Let A be the subsets of X that have even size and let B be the subsets of X that have odd size. Establish a bijection from A to B, thereby proving that |A| = |B|. (10 points)

   A hash function is a function h that maps a set S of keys k to a finite set of table indices, 0, 1, …, m − 1. A table whose information is found by a hash function is called a hash table.
   Given a hash function h′ : S → {0, 1, …, m − 1} which maps a set of keys S to the slots of a hash table T[0, …, m − 1], the method of linear probing uses a hash function of the form

   h(k, i) = (h′(k) + i) mod m

   for i = 0, 1, …, m − 1; h′ is referred to as an auxiliary hash function. Given key k, we first probe T[h′(k)], i.e., the table slot given by the auxiliary hash function. We next probe slot T[h′(k) + 1], and so on up to slot T[m − 1]. We then wrap around to slots T[0], T[1], …, until we finally probe slot T[h′(k) − 1].
   Quadratic probing uses a hash function of the form

   h(k, i) = (h′(k) + c₁i + c₂i²) mod m,

   where h′ is an auxiliary hash function, c₁ and c₂ are positive auxiliary constants, and i = 0, 1, … m − 1. The initial position probed is T[h′(k)]; later positions probed are offset by amounts that depend in a quadratic manner on the probe number i.
   Double hashing uses a hash function of the form

   h(k, i) = (h₁(k) + ih₂(k)) mod m,

   where both h₁ and h₂ are auxiliary hash functions. The initial probe goes to position T[h₁(k)]; successive probe positions are offset from previous positions by the amount h₂(k), modulo m. Unlike linear or quadratic probing, the probe sequence here depends in two ways upon the key k.
   Consider inserting the keys in S = {10, 22, 31, 4, 15, 28, 17, 88, 59} into an initially empty hash table T of size m = 11.

   1. Show the result of inserting the keys using linear probing, with the auxiliary hash function h′(k) = k. Construct the hash table by choosing a key for entry in T by the order that it is listed in S. (3 points)
   2. Show the result of inserting the keys using quadratic probing, with the auxiliary hash function h′(k) = k, c₁ = 1, and c₂ = 3. Again, choose a key for entry in T by the order that it is listed in S. (3 points)
   3. Show the result of inserting the keys using double hashing, with auxiliary hash functions h₁(k) = k and h₂(k) = 1 + (k mod (m − 1)). Again, choose a key for entry in T by the order that it is listed in S. (3 points)
   4. Which of the three methods required the least amount of probing on this set of keys? (1 point)