CSC263 Winter 2017 Midterm Sample Solutions Version: LEC0102 (Larry) Q1: (a): 1, 2 (b): 10 (c): 5 (d): No, counterexample as follows: 5 / \ 3 8 \ 6 (e): False, as in the problem set, quadratic probing may not find a free slot (f): 1.2, each item has 7-2=5 recharge dollars, so each old item needs 0.2 new items to be recharged. (g): Adjacency matrix: Theta(|V|) Adjacency list: Theta(1) Edge list: Theta(|E|) Q2: Best case: 1 comparison; probability: 1/(n-1) Worst case: n-1 comparisons; probability: 1/(n-1) Average case: each of the values from 1 to n-1 has probability 1/(n-1), so the expectation is: E[X] = \sum_{i=1}^(n-1) i*1/(n-1) = 1/(n-1) * \sum_{i=1}^(n-1) i = n/2 Q3: Each node keeps the following attributes: - amount: the amount value, this is the sorting key of the AVL tree - dup: the number of duplicates of the amount - sum: sum of dup values of all nodes in the subtree, this is the augmenting attribute. The value of sum only depends on the node's two children and the node itself, therefore it can be maintained efficiently. INSERT(x) works as follows: first do an AVL-search for x. If a node with amount x exists in the tree, simply increment the node's dup value and update sum attributes accordingly; if x does not exist in the tree, do an AVL-insert of a new node with amount x and dup value 1. Both AVL-search and AVL-insert are O(logn) and the sum attribute can be efficiently maintained, so the runtime is O(logn). RANGE-QUERY(x1, x2) works as follows: Using a similar function as the PartialSum function that we did in the problem set. In this case, PartialSum(x) would sum up the dup values of all nodes with amount <= x. Then the return value of RANGE-QUERY(x1, x2) is simply: PartialSum(x2) - PartialSum(x1) + dup(x1) where dup(x1) is the dup attribute of the node with amount x1. Note: having multiple nodes with the same amount in the tree would not work correctly since the rebalancing rotations would place the duplicate nodes all over the place and they become hard to manage. Keeping the dup value is the simplest working solution.