CSC263H1, Summer 2020 Problem Set 3
General instructions
CSC263H1: Problem Set 3
Due Friday July 17 before 10pm
Please read the following instructions carefully before starting the problem set. They contain important information about general problem set expectations, problem set submission instructions, and reminders of course policies.
• Your problem sets are graded on both correctness and clarity of communication. Solutions that are technically correct but poorly written will not receive full marks. Please read over your solutions carefully before submitting them.
• Each problem set may be completed in groups of up to three. If you are working in a group for this problem set, please consult the articles on collaboration and plagiarism on posted on quercus.
• Solutions must be typeset electronically, and submitted as a PDF with the correct filename. Hand- written submissions will receive a grade of ZERO.
The required filename for this problem set is problem set3.pdf.
• Problem sets must be submitted online through MarkUs. If you haven’t used MarkUs before, give yourself plenty of time to figure it out, and ask for help if you need it! If you are working with a partner, you must form a group on MarkUs, and make one submission per group. “I didn’t know how to use MarkUs” is not a valid excuse for submitting late work.
• Your submitted file(s) should not be larger than 9MB. You might exceed this limit if you use a word processor like Microsoft Word to create a PDF; if it does, you should look into PDF compression tools to make your PDF smaller, although please make sure that your PDF is still legible before submitting!
• Submissions must be made before the due date on MarkUs.
• The work you submit must be that of your group; you may not use or copy from the work of other
groups, or external sources like websites or textbooks.
Additional instructions
• If you are working in a group, remember to form your group before you hand in the problem set.
• Ensure that your last submission before the deadline is the submission you want graded – CrowdMark
does not allow for late resubmissions.
• Please limit the length of your pseudocode to 2 pages.
Page 1/4
CSC263H1, Summer 2020 Problem Set 3
1. [10 marks] Hashing.
(a) What is the worst-case running time for Insert in an open-addressing hash table with n items and m slots (m > n)? Give an exact expression in terms of the number of slots of the array that are visited.
(b) Specify a sequence of n+1 items, a hash function and a type of probing that achieves this worst-case. That is Inserting the n + 1-th item should take the amount of time given in part (a).
(c) What is the amortized cost of each Insert in the sequence from (b)?
(d) Change just the hash function so that every Insert from the sequence in part (b) takes constant time.
Page 2/4
CSC263H1, Summer 2020 Problem Set 3
2. [20 marks] Ternary counter. A ternary counter is a string of k “trits” tk−1, tk, · · · , t0, each of which can be 0, 1, or 2. As with a binary counter, we can perform the operation Increment on a ternary counter. If we start with every trit equal to 0, then after n Increments, the counter holds the number nwritteninbase3. Forexample,ifk=4andn=6,wehave
t3 t2 t1 t0 0000 0001 0002 0010 0011 0012 0020
The cost of each Increment is the number of trits that change. We are interested in the worst-case sequence complexity, WCSC(n), of performing n Increments starting from all 0’s.
∞
(a) Compute WCSC(n) using the aggregate method. You may use the fact that 1/3i = 3/2. i=0
(b) Compute WCSC(n) using the accounting method. Make sure to specify the charge for each Incre- ment and the credit invariant.
Page 3/4
CSC263H1, Summer 2020 Problem Set 3
3. [15 marks] Heaps. Consider the HEAP data structure. Recall that it supports INSERT and EX- TRACTMAX in O(log n) worst case time, where n is the number of elements in the PRIORITY QUEUE.
(a) Give a potential function Φ such that the amortized cost of INSERT is O(log n) and the amortized cost of EXTRACTMAX is O(1) with respect to Φ. Justify your answer.
(b) Prove that for any constant c, the potential function Φ(H) = c × size(H) is not a solution to (a).
(c) Consider a sequence of n EXTRACTMAX operations performed on a heap H that initially contains n elements. Does the fact that the amortized cost of each EXTRACTMAX operation is O(1) mean that the entire sequence can be processed in O(n) time? Justify your answer.
Page 4/4