There were two quizzes and n students. All students attended the first quiz, and all but one attended the second.
computer science
Description
Q1. Suppose that we use an open-addressed hash table of size m to store n = ↵m items, where ↵ < 1. Assume uniform hashing. Let the random variable Xi denote the number of probes required by the ith insertion, and X = max1in Xi be the maximum number of probes required by any of the n insertions.
Q2. There were two quizzes and n students. All students attended the
first quiz, and all but one attended the second. The teacher kept a single list
containing, not in any particular order, the ID’s of the students attending the
quizzes (where the ID of a student appears twice if (s)he attends both quizzes).
The teacher would like to find the ID of the student who was absent from the
second quiz.
Design three algorithms to solve this problem, with the following complexities, and explain why they have these complexities:
Instruction Files
2021springhw1.pdf
145.0 KB
