University of Waterloo
CS240 Spring 2022 Assignment 4
Due Date: Wednesday, July 6 at 5:00pm
The integrity of the grade you receive in this course is very important to you and the University of Waterloo. As part of every assessment in this course you must read and sign an Academic Integrity Declaration before you start working on the assessment and submit it before the deadline of July 6 along with your answers to the assignment; i.e. read, sign and submit A04-AID.txt now or as soon as possible. The agreement will indicate what you must do to ensure the integrity of your grade. If you are having difficulties with the assignment, course staff are there to help (provided it isn’t last minute).
The Academic Integrity Declaration must be signed and submitted on time or the assessment will not be marked.
Please read https://student.cs.uwaterloo.ca/~cs240/s22/assignments.phtml#guidelines for guidelines on submission. Each question must be submitted individually to MarkUs as a PDF with the corresponding file names: a4q1.pdf, … , a4q5.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: Assignments are due at 5:00pm on Wednesday. Students are allowed to submit one late assignment, 2 days after the due date on Friday by 5:00pm. Assignments submitted after Friday at 5:00pm or Wednesday at 5:00pm (if you have already used your one late submission) will not be accepted for grading but may be reviewed (by request) for feedback purposes only. If you want to use your one time late assignment allowance, please send an email to with the title “Using one time late assignment al- lowance”.
Question 1 [6 marks]
Consider a set X = {x1,…,xn } where every xi is a positive integer and xi ≤ nf for some constant f . We represent xi as strings over an alphabet 0, 1, . . . , 2t − 1 (i.e., representing each xi in base 2t) and store all xi from X in a compressed trie T. For every node u of T we keep an array A(u) of size 2t + 1. A(u)[i] contains a pointer to the child ui of u such that the edge from u to ui is marked with i; A(u)[i] = NULL if there is no such ui in T.
Specify all of the following in big-O in terms of f, n, and t (as necessary). What is the maximum height of T? What is the total space usage of T and all A(u)? What time is
Programming Help, Add QQ: 749389476
neededtosearchforakeykinT ?
Question 2 [2+2+2+2+3+4 marks]
(a) Draw the standard trie that is obtained after inserting the following keys into an initially empty trie:
1011$, 001$, 1101$, 10010$, 10$, 11$, 10100$, 1$, 000$, 101$, 00$
(b) Fromyouranswertopart(a),drawthetriethatisobtainedafterremovingthefollowing
10100$, 11$, 1011$
(c) Repeat part (a), except use a compressed trie.
(d) Repeat part (b), but on the compressed tree that is obtained at (c).
(e) Find the exact height of the trie with keys that are binary representations of numbers 0, 1, 2, 3, 4, . . . , 2k − 1 without leading 0s, and inserted into the trie in increasing order. That is, insert 0$, 1$, 10$, 11$, 100$, etc. Justify your answer.
(f) Repeat part (e) using compressed tries. Also, for this part, prove your result, including any structural properties of the compressed tries, using mathematical induction.
Note that in order to obtain full marks for proofs involving mathematical induction, solutions must clearly state:
• what you are doing induction on; • the base case(s);
• the inductive hypothesis;
• the inductive step.
Question 3 [3+3+3+3+1 marks]
Consider a hash table dictionary with universe U = {0, 1, 2, . . . , 25} and size M = 5. If items with keys k = 17, 10, 20, 13 are inserted in that order, draw the resulting hash table if we resolve collisions using:
(a) Chaining with h(k) = (k + 2) mod 5.
(b) Linear probing with h(k) = (k + 2) mod 5
(c) Doublehashingwithh1(k)=(k+2)mod5andh2(k)=1+(kmod4). (d) Cuckoo hashing with h1(k) = (k + 2) mod 5 and h2(k) = ⌊k/5⌋.
(e) Identify a serious problem with the choice of hash functions in part (d). 2
Code Help, Add WeChat: cstutorcs
Question 4 [3+4 marks]
(a) Assume that we have a hash table of size 6 and that our keys are selected uniformly at random from the set A = {1, 2, 3, . . . , 600}. Consider the following two hash functions:
h1(k) = k mod 6, h2(k) = 2k mod 6.
Which hash function is better? Justify your answer.
(b) 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 lim cn/n = 1/e, where e ≈ 2.71828183. n→∞
You can use the fact that lim (1 − 1/n)n = 1/e. We recommend you use indicator n→∞
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 5 [4+4+4 marks]
In this question, we consider a modified version of open-addressing hashing. In this modified version, the insert operation works as follows. To insert a key k, we perform linear probing until we either reach an empty position in the hash table or probe a position that is not empty. Say the nonempty position in the table contains the key k′. Then, if k′ > k, we replace k′ with k at that position and call the insert operation on k′. If k′ ≤ k, continue trying to insert k in the position after k′, as is done in normal linear probing. In this way, the value of the key we are trying to insert into the hash table is strictly increasing.
For each question that follows, we may assume that no key is ever deleted from the hash table.
(a) For a hash table of size M = 10 and the hash function h(x) = x mod 10, run this modified hash algorithm using the insertion sequence {31, 26, 16, 23, 11, 30, 20}. Show the hash table after each insertion is complete; that is, after no more probing is required.
(b) Argue that, regardless of the values of M and h(x), the insertion operation will always terminate after a finite number of probes.
You may assume that there is still space in the hash table upon each insertion and that all probe sequences consist of some permutation of the positions of the hash table.
(c) Argue that the number of probes made during an insert could be Ω(n2). That is, for arbitrarily large values of n, give an example of a hash table with n keys and size M > n such that insertion of a key into the hash table will require at least cn2 probes for some constant c > 0. Justify insertions.
The most straightforward approach would be to use linear probing with the hash function h(x) = x mod M, but you can choose to use another hash function if you want (as long as it can map to all entries of the table).
程序代写 CS代考 加微信: cstutorcs