CSC263 Winter 2019 Midterm Sample Solutions

Question 1

a. Yes; e.g. for the max-heap [7, 6, 5, 4, 3, 2, 1], the level-order traversal visits the elements from 7 to 1.

b.
Worst-case Omega: we learn that the algorithm is Omega(n^2) in the worst case.
Worst-case O: we learn nothing.
Best-case Omega: we learn nothing.
Best-case O: we learn that the algorithm is O(n^2) in the best case.

c. True. Each insert is guaranteed to succeed. We therefore have m items in a hash table with m buckets, so the load factor is 1.0.

d. 0

e.
The pattern is
1, 1, 1, 4, 1, 1, 7, 1, 1, 10, 1, 1, etc.
= 1, 1, 1, 1+3, 1, 1, 1+6, 1, 1, 1+9, 1, 1, etc.

The sum is
m + \sum_{k=1}^{floor((m-1)/3)} 3k


----------

Question 2

a. 1

b. (1/2)*(1/n) = 1/(2n)

c. Let t be the number of comparisons. t takes on a value between 1 and n+1. We want the expected value of t. The sum is
\sum_{t=1}^n (t * (1/2n)) + (1/2)(n+1)
= (1/2n) \sum_{t=1}^n (t) + (1/2)(n+1)
= (1/2n) * n(n+1)/2 + (1/2)(n+1)
= (n+1)/4 + (n+1)/2
= 3(n+1)/4


----------

Question 3

The pseudocode is:

create an empty hash table
for each item in lst:
  add the item to the hash table
for each item x in lst:
  check whether t-x != x and t-x is in the hash table. If yes, return True
return False

The algorithm is correct because for each item x, another item t-x is required. (There is a special case to make sure that the same item is not allowed to count twice.) Each of these searches is performed by using the hash table.

The algorithm is average-case O(n), because each of the n inserts is O(1), and each of the n searches (assuming Simple Uniform Hashing) is also O(1).