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.