Submitting:

  • All homeworks should be turned in electronically to myCourses.
  • Paper submissions may be scanned in if legible.
  • If you take a photo of your paper solution, please take the photo outside or close to a bright window, for legibility.

Due dates:

  • Homeworks are due by 10pm on the due date (Thu).
  • No late submissions are accepted.
  • If there are extenuating circumstances, contact the instructor as soon as possible to make arrangements.

References:

  • If you find a resource helpful (from internet search, blog post, Stack Overflow, online courses, our lecture notes, etc), be sure to cite it. Citation format doesn’t matter, but make it easy for the TA to find the source: e.g., a clickable link.
  • Code / pseudocode should be your own work. If you find code online, understand how it works, then go write up your solution on your own.
  • The basic machine model was discussed in Lecture 1. Don’t use library functions which obviate the bulk of a question. E.g., if you’re asked to implement a sort, don’t use Python’s sorted().

HW4 (20pts) (solutions)

Let A = [ 84, 22, 16, 35, 95, 57, 19, 30 ].

  1. (a) (2pts) Demonstrate counting sort on A, sorting on only the first digit of each number.
    • (b) (1pt) How does your result demonstrate that counting sort is a stable sort?

  2. (3pts) Demonstrate radix sort on A, using r=3-bit digits (i.e., base 8)

  3. (3pts) Demonstrate bucket sort on A, with each number divided by 100 to get it into the range [0,1).

  4. Let K = [ 5, 12, 3, 15, 7, 1, 4 ] be a sequence of keys.
    Demonstrate (show as much work as you can) inserting these keys in order into a hash table of size 7, if the hash table uses:
    • (a) (3pts) Chaining, with multiplication hash and A=0.3
    • (b) (4pts) Open addressing, with double-hash: `h_1` is division hash, and `h_2` is multiplication hash with A=0.3
  5. (4pts) Consider a small hash table of size m = 4, and key space U = `bbb Z_m` = {0, 1, 2, 3}.
    Let H = `{h_i}_(i=1)^4` be a pool of hash functions: `h_i(k) = ((i*k) mod 5) mod 4`.
    Does the pool H satisfy the universal hash property?