1
h03
CS32 S17
Name:
(as it would appear on official course roster)
Umail address: @umail.ucsb.edu section
Optional: name you wish to be called
if different from name above.
Optional: name of "homework buddy"
(leaving this blank signifies "I worked alone"

h03: Hashing

ready? assigned due points
true Thu 04/27 09:30AM Tue 05/02 09:30AM

You may collaborate on this homework with AT MOST one person, an optional "homework buddy".

MAY ONLY BE TURNED IN IN THE LECTURE/LAB LISTED ABOVE AS THE DUE DATE,
OR IF APPLICABLE, SUBMITTED ON GRADESCOPE. There is NO MAKEUP for missed assignments;
in place of that, we drop the three lowest scores (if you have zeros, those are the three lowest scores.)

https://ucsb-cs32-s17.github.io/hwk/h03/

Reading: Hashing, DS 12.2

  1. (10 pts) Fill in the information in the header. The following are required to get the 10 "participation" points.
    • Filling in your name and umail address.
    • WRITING (not circling!) either 11, 12, 1, or 2, to indicate your discussion section (lab) meeeting time.
    • Writing your first and last initial in large capital letters.

    Also: For paper submission PLEASE submit on ONE SHEET OF PAPER, double-sided if at all possible. If you must submit on two printed sheets write name on BOTH sheets and no staples, paperclips, or folded corners.
    For gradescope self-submission: PLEASE get the pages in the correct order. First page of your PDF file is p1, the next is p2.

  2. There is a technique known as "double-hashing".
    1. (4 pts) What is the problem that double-hashing is designed to solve? Explain briefly.
    2. (4 pts) How does double-hashing solve that problem? Explain briefly.
  3. The ADT known as a "dictionary" provides a way to look up with keys to find values. We define these operations as:
       
    • lookup(key) which returns either a value, or a "not-found" indicator.
      •  
    • remove(key) which removes the item with that key (if it exists).
      •  
    • insert(key,value) which adds the new key-value pair, or replaces the value if it already exists.
    We could implement a dictionary with an array of (key,value) pairs, sorted by key. We could use binary search for lookup. We'd have to figure out a way to put new values into the sorted list, and remove values. Or we could use hashing.
    1. (2 pts) If we use binary search on a sorted array, what is the worst case time for lookup(key) in terms of big-O. (No explanation needed, just state the answer.)
    2. (8 pts) If we use binary search on a sorted array, what is the worst case time for remove(key)? This time, briefly explain your answer.
    3. (8 pts) If we use binary search on a sorted array, what is the worst case time for insert(key,value)? This time, briefly explain your answer.
    4. (4 pts) If we use hash tables instead, what is the worst-case big-O time for lookup(key)? (Just state it.)
    5. (3 pts) Is the worst case for lookup(key) for hash tables better or worse than for the binary search?
    6. (4 pts) If we use hash tables instead, what is the average (expected) case big-O time for lookup(key). (Just state it.)
    7. (3 pts) Is the average (expected) case for lookup(key) for hash tables better or worse than the binary search approach?