[SOLVED] CSC263H1, Fall 2019 Problem Set 4

CSC263H1, Fall 2019 Problem Set 4
General instructions
CSC263H1: Problem Set 4
Due Tuesday October 15 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 set4.pdf.
Problem sets must be submitted online through CrowdMark. If you havent used CrowdMark 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 CrowdMark, and make one submission per group. I didnt know how to use CrowdMark 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 CrowdMark.
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 on CrowdMark before you submit your solutions.
Ensure that your last submission before the deadline is the submission you want graded CrowdMark does not allow late resubmissions.
Page 1/2

CSC263H1, Fall 2019 Problem Set 4
1. [10 marks] Open Address 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 keys, a hash function, and a type of probing such that after inserting each key in the sequence into an initially empty hash table, the (n + 1)-th Insert achieves the worst-case running time given in (a).
(c) What is the average-case running time of each Insert in the sequence from (b)? (By average, we mean the total running time of all calls to Insert, divided by number of such calls.)
(d) Change just the hash function so that every Insert from the sequence of insertions in part (b) takes constant time.
Page allowance: Please neatly present your solution using 12 pages. Any additional pages will not be marked.
Page 2/2