Previous: Homework assignment 11Homework assignment 11 Up: Homework assignmentsHomework assignments Next: Homework assignment 13Homework assignment 13
Document also available in PDF, Postscript, DVI, pure text and LaTeX.

Homework assignment 12



4.4. Functions

Exercise 1  [11 p. 303]   Let S = {a,b,c,d} and T = {x,y,z}.
  1. Give an example of a function from S to T that is neither onto nor one-to-one.
  2. Give an example of a function from S to T that is onto but not one-to-one.
  3. Can you find a function from S to T that is one-to-one?
Proof: [Correction]
  1. f defined as follow: f(a)=f(b)=f(c)=f(d)=x.
  2. f defined as follow: f(a)=f(b)=x, f(c)=y, f(d)=z.
  3. No. If a function is one-to-one, its image have the same size as its domain, and so the codomain cannot be of strictly smaller size than the domain.
Exercise 2  [18 p. 303]   Ackermann's function, mapping N2 to N, is a function that grows very rapidly. It is given by
A(0,y) = 1   for all yinN
A(1,0) = 2
A(x,0) = x+2   for x>= 2
A(x+1,y+1) = A(A(x,y+1),y)   for all xinN, yinN
  1. Find an equation f(x) to describe A(x,1) for all x>=1.
  2. Find an equation g(x) to describe A(x,2) for all x>=1.
  3. Compute the value of A(4,3).
Proof: [Correction]
  1. Let x>=1 be an integer. Then A(x,1)=A(A(x-1,1),0)=A(x-1,1)+2. With A(1,0)=2, this defines f recursively. By solving this (easy) recurrence, we get f(x)=2x.

  2. By a similar reasoning, we get g(x) = 2x.
  3. A(4,3) = A(A(A(A(1,2),2),2),2) = 265536-1 approx 2.0035299304 × 1019728
Exercise 3  [36 p. 306]  
  1. For |S| = 2, 3 and 4, respectively, use the theorem on the number of functions to show that the number of one-to-one functions from S to S equals the number of onto functions from S to S.
  2. Argue that for |S|=n, f:S-> S is one-to-one if and only if f is onto.
  3. Find an infinite set S and a function f:S-> S such that f is one-to-one but not onto.
  4. Find an infinite set S and a function f:S-> S such that f is onto but not one-to-one.
Proof: [Correction]
  1. Direct computation (check them!).
  2. If f is one-to-one, then the size of the image is the size of the domain, which is n. So, since the codomain is also of size n, the image is equal to the codomain, and f is onto. If f is not one-to-one, then the size of the image is strictly smaller than the size of the domain. So the image is a strict subset of the codomain, and f is not onto.
  3. Take S:=N, and define f by f(x):=x+1. It's obviously one-to-one, but 0 has no preimage.
  4. Take S:=N, and define f by f(0)=0 and f(x)=x-1 for x>0. Then f is onto, but f(0)=f(1), so f is not one-to-one.
Exercise 4  [38 p. 306]  
  1. A system development project calls for 5 different tasks to be assigned to Maria, John, and Suzanne. In how many ways can this be done if each of the 3 workers must get at least 1 task?
  2. In how many ways can the project be assigned if Maria must develop the test plan, which is 1 of the 5 tasks, buy may do other tasks as well? (Hint: Consider the two cases where Maria does and does not do any of the other tasks.)
Proof: [Correction]
  1. This is the number of surjection from a set of size 5 (tasks) and a set of size 3 (workers): 150.
  2. First case: Maria does at least one other task. We count the number of surjection from a set of size 4 (remaining tasks) and a set of size 3 (workers). Second case: Maria only does the test plan. We count the number of surjection from a set a set of size 4 (remaining tasks) and a set of size 2 (remaining workers). This adds up to 50.
Exercise 5  [43 p. 307]   When a computer program is compiled, the compiler builds a symbol table to store information about the identifiers used in the program. A scheme is needed to quickly decide whether a given identifier has already been stored in the table and, if not, to store the new identifier. A hash function is often used to locate a position in the table at which to store information about an item. A hash function should be quick to compute and should ideally give a wide distribution of locations throughout the table.

For simplicity, assume that the items to be stored are integers and that the table can hold 17 items in positions 0-16. If n is the item to be stored, let the hash function f(n) be f(n) = n mod 17, which is the integer remainder when n is divided by 17. Under this hashing function, the integer 23 hashes to 23 mod 17 = 6, and 23 would be stored at location 6 in the table. However, 6, 40, and many other numbers also hash to 6. There must be some algorithm for collision resolution that tells how to proceed if a number to be stored hashes to an already occupied spot in the table. One technique is to use linear probing, which simply means that if the number hashes to an already occupied spot in the table, then it should be stored in the next open position, wrapping around to the top of the table if necessary.

  1. Using the hash function and collision resolution scheme described, store the sequence of values 23,14,52,40,24,18,33,58,50. Give the locations in the table at which each is stored.
  2. After the table in part (a) has been filled, describe the process to search for 58 in the table. Describe the process to search (unsuccessfully) for 41 in the table.
  3. Explain what problem can arise if an item stored in a hash table is later deleted.
Proof: [Correction]
  1. Position: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
    Value: 50 52 18       23 40 24 58         14   33
  2. If we wanted to find 58 in the table, we would first compute f(58)=7 and check to see whether or not position 7 is filled. Since it is filled, we compare the values at position 7 to see if it is equal to 58. Since H(7)!= 58, we check to see if H(7+1) is filled and if it is whether H(7+1) = 58. This is continued until either H(n)=58 is found or H(n) is empty.

    If we wanted to find 41 in the table we would first find f(41)=6. We would first test if H(6) is filled, since it is we would test if H(6)=41. If it doesn't, we would test whether H(6+k) is occupied and if it is, whether or not it is equal to 41. This would continue until we found that H(10) is empty.
  3. If an item stored in the hash table is later deleted, say 40, the search algorithm would stop without finding 24 or 58.
Previous: Homework assignment 11Homework assignment 11 Up: Homework assignmentsHomework assignments Next: Homework assignment 13Homework assignment 13
Homework assignment 12 / CSM MACS-358 / Nicolas M. Thiéry
Last modified: Tue Dec 2 13:40:44 2003