Exam Policies
 Allowed:
 Paper copy of textbook
 Paper notes, printed or handwritten
 Bring blank 8.5x11” paper
 Not allowed:
 Use of electronics, computers, etc. (all screens off)
 Use of mobile phone (off/mute and in pocket/bag)
 Communication with anyone except invigilator
 If you feel a question is ambiguous, write on your exam sheet your interpretation of the question, and answer accordingly.
 Please label/number your pages clearly and staple them in order when handing in.
Practise Final exam [120 pts] ###

(6 pts) Prove: `n log_2 (n^2) + n^2 = Omega(n^2)`

(7 pts) Given the recurrence: `T(n) = sqrt n T(sqrt n) + n log n`, prove `T(n)=n log n`.

(3 pts) Solve the recurrence: `T(n) = 3T(n/3) + log n`
Master theorem 
(4 pts) Convert the following array into a binary maxheap:
[ 5, 10, 3, 1, 6, 2, 4, 8, 7, 9 ]

(4 pts) The median of n numbers can be found in O(n) time (ch9). What is the worstcase complexity of Quicksort if the median is used for the pivot? O(n lg n)

(6 pts) Demonstrate radix sort in base 5 on the following:
[ 23, 17, 74, 14, 25, 33, 106, 4, 93 ]
 (10 pts) Demonstrate inserting the keys
[ 10, 22, 31, 4, 15, 28, 17, 88, 59 ]
into an openaddressed hash table of sizem = 11
using division hash and (a) linear probing [22, 88, , , 4, 15, 28, 17, 59, 31, 10]
 (b) quadratic probing with `c_1=1, c_2=3` [22, , 88, 17, 4, , 28, 59, 15, 31, 10]
 (c) double hashing with `h_1(k)=k and h_2(k) = 1 + (k mod(m1))` [22, , 59, 17, 4, 15, 28, 88, , 31, 10]

(5 pts) Demonstrate the following sequence of operations on an empty binary search tree (
+X
means insert keyX
,X
means delete keyX
). Use successor for delete.
+F +T +D +V +K +M +E F +L +P T
preorder before ‘F’: FDETKMV
Before ‘T’: KDEMLPV
End: KDEVML 
(5 pts) Pseudocode a function to count the leaves of a binary tree. Many possible solutions, a simple strategy is a modified DFS.

(10 pts) Draw the Btree of t=3 with the following inserted in order. Draw the tree just before and after each insertion which results in a split.
AGFBKDHMJESIRX
t=3 means nodes can have between 2 and 5 keys 
(10 pts) Demonstrate the dynamic programming solution for optimal parenthesisation to multiply a list of matrices with dimensions: (2x5), (5x10), (10x4), (4x5), (5x7)

(8 pts) Demonstrate fractional knapsack on items of weight
w = [ 30, 40, 50, 60, 80 ]
and valuev = [ 45, 80, 60, 90, 100 ]
, with total capacityW = 220
. What is an optimal 01 knapsack solution? Valuetoweight ratios: [ 1.5, 2, 1.2, 1.5, 1.25 ]
Greedy fractional solution: weight = 40 + 30 + 60 + 80 + (1/5)50
Total value: 80 + 45 + 90 + 100 + (1/5)60 = 327.
01 solution: everything except item of weight 50:
Total weight 210, total value 315. 
(5 pts) Assume two lists of length `n_1` and `n_2` can be merged in `c(n_1+n_2)` operations. What is the minimum number of operations in which lists of the following lengths can be merged?
[ 7, 3, 11, 4, 6, 12, 2 ]
((4 + (2 + 3)) + 11) + (12 + (6 + 7))
Total ops: 2(11+12)c + 3(4+6+7)c + 4(2+3)c = 117c 
(8 pts) Demonstrate finding the stronglyconnected components of the following graph:
Edges between components: (g, af), (af, bde), (g, bde), (bde, c), (c, h), (g, h) 
(5 pts) Prove, or demonstrate a counterexample: If T is a minimum spanning tree in a weighted directed graph (V, E, w), then for any vertices u, v the path between them in T is a shortest path in the graph.

(4 pts) Consider finding singlesource shortest paths in a directed, weighed graph with negativeweight edges. A question was asked in lecture whether Dijkstra’s algorithm with Johnson’s reweighting would be faster than BellmanFord, since Dijkstra is faster than BF when we can assume all edge weights are positive. Discuss: would this reweighting be a good idea? As we discussed (briefly) in class, Johnson’s reweighting uses BellmanFord to determine a reweighting that preserves shortest paths and eliminates negative weights. In the singlesource case, if we’re going to do that, we might as well just use BellmanFord to solve the whole problem; reweighting would not be better.
 (10 pts) Chapter 25: allpairs shortest paths: FloydWarshall, Johnson