MIT6006 Problem Set 3 Solution

Please write your solutions in the L ATEX and Python templates provided. Aim for concise solutions; convoluted and obtuse descriptions might receive low marks, even when they are correct.
Problem 3-1. [5 points] Hash Practice
(a) [2 points] Insert integer keys A = [47, 61, 36, 52, 56, 33, 92] in order into a hash table of size 7 using the hash function h(k) = (10k + 4) mod 7. Each slot of the hash table stores a linked list of the keys hashing to that slot, with later insertions being appended to the end of the list. Draw a picture of the hash table after all keys have been inserted.
(b) [3 points] Suppose the hash function were instead h(k) = ((10k + 4) mod c) mod 7 for some positive integer c. Find the smallest value of c such that no collisions occur when inserting the keys from A.
Problem 3-2. [15 points] Dorm Hashing
MIT wants to assign 2n new students to n rooms, numbered 0 to n − 1, in Pseudorandom Hall. Each MIT student will have an ID: a postive integer less than u, with . No two students can have the same ID, but new students are allowed to choose their own IDs after the start of term.
MIT wants to find students quickly given their IDs, so will assign students to rooms by hashing their IDs to a room number. So as not to appear biased, MIT will publish a family H of hash functions online before the start of term (before new students choose their IDs), and then after students choose IDs, MIT will choose a rooming hash function uniformly at random from H.
New MIT freshmen Rony Stark and Tiri Williams want to be roommates. For each hash family below, show that either:
• Rony and Tiri can choose IDs k1 and k2 so as to guarantee that they’ll be roommates, or
• prove that no such choice is possible and compute the highest probability they could possibly achieve of being roommates.
(a) [5 points] H = {hab(k) = (ak + b) mod n | a, b ∈ {0,...,n − 1} and a 6= 0}

(b) [5 points]
(c) [5 points] H = {hab(k) = ((ak + b) mod p) mod n | a, b ∈ {0,...,p − 1} and a 6= 0} for fixed prime p > u (this is the universal hash family from Lecture 4)
2 Problem Set 3
Problem 3-3. [20 points] The Cold is Not Bothersome Anyway
Ice cores are long cylindrical plugs drilled out of deep glaciers, which are accumulations of snow piled on top of each other and compressed into ice. Scientists can divide an ice core into distinct slices, each representing one year of deposits. For each of the following scenerios, describe an efficient algorithm to sort n slices collected from multiple ice cores. Justify your answers.
(a) [5a string of exactly points] Every ice core is given a unique 16dlog4( √n )e ASCII characters.core identifier 2 Sort the slices by core identifier. for bookkeeping, which is
(b) [5 points] The deepest ice cores in the database are up to 800,000 years old. Sort the slices by their age: the integer number of years since the slice was formed.
(c) [5 points] Variation in the amount of snowfall each year will cause a glacier to accumulate at different rates over time. Sort the slices by thickness, a rational number of centimeters of the form m/n3 between 0 and 4, where m is an integer.
(d) [5 points] Elna of Northendelle has discovered that water has memory, but is unable to quantify the memory of a given slice. Luckily, given two slices, she can distinguish which has more memory in O(1) time using her “two-finger algorithm” (touching the slices with her two index fingers). Sort the slices by memory.
Problem 3-4. [20 points] Pushing Paper
Farryl Dilbin is a forklift operator at Munder Difflin paper company’s central warehouse. She needs to ship exactly r reams of paper to a customer. In the warehouse are n boxes of paper, each one foot in width, lined up side-by-side covering an n-foot wall. Each box contains a known positive integer number of reams, where no two boxes contain the same number of reams. Let B = (b0,...bn−1) be the number of reams per box, where box i located i feet from the left end of the wall contains bi reams of paper, where bi 6= bj for all i 6= j. To minimize her effort, Pharryl wants to know whether there is a close pair (bi,bj ) of boxes, meaning that |i − j| < n/10, that will fulfill order r, meaning that bi + bj = r.
(a) [10 points] Given B and r, describe an expected O(n)-time algorithm to determine whether B contains a close pair that fulfills order r.
(b) [10 points] Now suppose that r < n . Describe a worst-case O(n)-time algorithm to determine whether B contains a close pair that fulfills order r.
Problem Set 3 3
Problem 3-5. [40 points] Anagram Archaeology
String A is an anagram of another string B if A is a permutation of the letters in B; for example,
(indicatory, dictionary) and (brush, shrub) are pairs of words that are anagrams of each other. In this problem, all strings will be ASCII strings containing only the lowercase English letters a to z.
Given two strings A and B, the anagram substring count of B in A is the number of contiguous substrings of A that are anagrams of B. For example, if A = ’esleastealaslatet’ and B = ’tesla’, then, of the 13 contiguous substrings in A of length |B| = 5, exactly 3 of them are anagrams of B, namely (’least’, ’steal’, ’slate’), so the anagram substring count of B in A is 3.
(a) [12 points] Given string A and a positive integer k, describe a data structure that can be built in O(|A|) time, which will then support a single operation: given a different string B with |B| = k, return the anagram substring count of B in A in O(k) time.
(b) [3 points] Given string T and an array of n length-k strings S = ( S0, . . . , S n−1) satisfying 0 < k < |T |, describe an O(|T | + nk)-time algorithm to return an array A
= ( a0, . . . , a n−1) for which ai is the anagram substring count of Si in T for all i ∈ {0, . . . , n − 1}.
(c) [25 points] Write a Python function count anagram substrings(T, S) that implements your algorithm from part (b). Note the built-in Python function ord(c) returns the ASCII integer corresponding to ASCII character c in O(1) time. You can download a code template containing some test cases from the website.
1 def count_anagram_substrings(T, S):
2 ’’’
3 Input: T | String
4 S | Tuple of strings S_i of equal length k < |T| 5 Output: A | Tuple of integers a_i:
6 | the anagram substring count of S_i in T
7 ’’’
8 A = []
9 ##################
10 # YOUR CODE HERE #
11 ################## 12 return tuple(A)
MIT OpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms of Use, visit: https://ocw.mit.edu/terms