CS240 - Spring 2024

Assignment 4

Due Date: Monday, July 15 at 8am

Please read the following link for guidelines on submission:

https://student.cs.uwaterloo.ca/~cs240/s24/assignments.phtml#guidelines

Each question must be submitted individually to MarkUs as a PDF with the cor- responding file names:  a4q1.pdf, a4q2.pdf, . . . It is a good idea to submit questions as you go so you aren’t trying to create several PDF files at the last minute.

Late Policy: There’s no grace period for this assignment

Question 1 Skip lists [3+3 marks]

Suppose you have a skip list with only three levels. The lower one has n + 2 entries −∞ < a0 < ··· < an−1  < +∞ . The middle one has k + 2 entries, where k is an integer that divides n (so that n = km for some integer m); we assume that (with the exceptions of ±∞), these entries are evenly spread out, so they correspond to −∞ , a0 , am , a2m , . . . , a(k−1)m , +∞ . The top level holds −∞ , +∞ .

1. What is the worst time for a query?  Give a Θ( ) expression involving k and n, and justify your answer.

2.  Given n, how to choose k so as to minimize the Θ( ) bound you just obtained, and what does the worst case become in that case?  Give a Θ( ) expression in terms of n, and justify your answer. You can assume n is a square.

Question 2 Analysis of self-organizing search [4+4+1+4+4 marks]

In this problem, we analyse the move-to-front strategy for linear search.  Suppose we have a linked list with keys x1 , . . . , xn , and that the probability of accessing xi  is pi ; it will be handy later on to assume that pi  > 0 for all i.

We consider the move-to-front heuristic. As input, we suppose we are given a linked list with keys x1 , . . . , xn , but we do not know in which order they are.

1. We do not know the order at the beginning, so let us call Xi(,j(0))  the probability that

initially xi  is before xj .  Show that after one query, the probability that xi  is before xj is

Xi(,j(1))  = pi + (1 − pi − pj )Xi(,j(0))

and the probability that xj  is before xi  is 1 − Xi(,j(1)) .

2.  Show by induction that after N queries, these probabilities are

Xi(,j(N))  = pi (1+(1−pi −pj )+(1−pi −pj )2 +···+(1−pi −pj )N−1)+(1−pi −pj )N Xi(,j(0)) and 1 − Xi(,j(N)) .

3.  Show that the limit probabilities, for N → ∞ , are

pi

pi + pj

and     .

You can use the fact that for 0 ≤ r < 1, 1 + r + r2 + r3 + ··· = . In the rest of the problem, we will assume that N is very large, and work with the limit probabilities.

4.  Show that for N → ∞ the expected position of xi  in the list is

Hint: rewrite the number of xj ’s before xi  as a sum involving indicator variables.  Note: we index positions starting from 1, just as we did in the move-to-front lecture.

5. What is the expected number CMTF  of links visited in a search using this heuristic? (do not try to simplify the expression). Compute this value for the frequencies of the example seen in class:

Question 3 Interpolation search [4+4 marks]

1.  Suppose that we use interpolation search in an array with entries A[i] = αi for i = 0, . . . , n − 1, α positive constant.  What is the worst-case runtime for search?  Give (and justify) a Θ bound.

2.  Suppose that we use interpolation search in  an  array with entries  A[i]  = √i,  for i = 0, . . . , n − 1, and that we search for k = 1. What is the runtime?  Give (and justify) a big-O bound. You can use any result seen in class without reproving them.

Question 4 Tries [3+3 marks]

1.  For n ≥ 1, find the height of the trie that stores the binary representation of all integers in {0, . . . , 2n  − 1} (without unnecessary leading zeros), that is, 0$, 1$, 10$, . . . .

2. What is the height of the compressed trie storing these words?

Question 5 Hashing [2+4 marks]

1.  Consider a hash table dictionary with universe U = {0, 1, 2, . . . , 24} and size M = 5. If items with keys k = 21, 3, 16, 1 are inserted in that order, draw the resulting hash table if we resolve collisions using:

• Linear probing with h(k) = (k + 1)  mod 5

•  Cuckoo hashing with h1 (k) = k   mod 5 and h2 (k) =  ⌊k/5⌋  (use two arrays of size 5)

2.  Let S be a set of n keys mapped to a hash table also of size n using chaining.  We make the uniform hashing assumption, and we call cn  the expected number of empty slots. Prove that cn  = n/e + o(n), where e is the basis of the natural logarithm.

You can use the fact that limn→∞ (1 − 1/n)n   =  1/e.   Hint:  use indicator variables I0 , . . . , In−1, that take values 0 or 1, depending on whether the corresponding entry in the table is empty or not; then, find the expected value of each Ii.

Question 6    One-sided range search in a heap  [5 marks]

Heaps are suitable for one-sided range queries.  Specifically, assume you are given a max-heap H and an integer x, and you are asked to return all keys in H that fall in the range [x, ∞ ), i.e., all keys that are at least x.

Give an algorithm that answers such a one-sided range query in time that depends only on the number k of keys in the output.  Describe your algorithm, justify why it works, and analyze the runtime.