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] ###

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

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

  3. (3 pts) Solve the recurrence: `T(n) = 3T(n/3) + log n`
    Master theorem

  4. (4 pts) Convert the following array into a binary max-heap:
    [ 5, 10, 3, 1, 6, 2, 4, 8, 7, 9 ]

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

  6. (6 pts) Demonstrate radix sort in base 5 on the following:
    [ 23, 17, 74, 14, 25, 33, 106, 4, 93 ]

  7. (10 pts) Demonstrate inserting the keys [ 10, 22, 31, 4, 15, 28, 17, 88, 59 ] into an open-addressed hash table of size m = 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(m-1))` [22, , 59, 17, 4, 15, 28, 88, , 31, 10]

  8. (5 pts) Demonstrate the following sequence of operations on an empty binary search tree (+X means insert key X, -X means delete key X). Use successor for delete.
    +F +T +D +V +K +M +E -F +L +P -T preorder before ‘-F’: FDETKMV
    Before ‘-T’: KDEMLPV
    End: KDEVML

  9. (5 pts) Pseudocode a function to count the leaves of a binary tree. Many possible solutions, a simple strategy is a modified DFS.

  10. (10 pts) Draw the B-tree 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

  11. (10 pts) Demonstrate the dynamic programming solution for optimal parenthesisation to multiply a list of matrices with dimensions: (2x5), (5x10), (10x4), (4x5), (5x7)

  12. (8 pts) Demonstrate fractional knapsack on items of weight w = [ 30, 40, 50, 60, 80 ] and value v = [ 45, 80, 60, 90, 100 ], with total capacity W = 220. What is an optimal 0-1 knapsack solution? Value-to-weight 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.
    0-1 solution: everything except item of weight 50:
    Total weight 210, total value 315.

  13. (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

  14. (8 pts) Demonstrate finding the strongly-connected components of the following graph:
    SCC Edges between components: (g, af), (af, bde), (g, bde), (bde, c), (c, h), (g, h)

  15. (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.

  16. (4 pts) Consider finding single-source shortest paths in a directed, weighed graph with negative-weight edges. A question was asked in lecture whether Dijkstra’s algorithm with Johnson’s reweighting would be faster than Bellman-Ford, since Dijkstra is faster than B-F 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 Bellman-Ford to determine a reweighting that preserves shortest paths and eliminates negative weights. In the single-source case, if we’re going to do that, we might as well just use Bellman-Ford to solve the whole problem; reweighting would not be better.

  17. (10 pts) Chapter 25: all-pairs shortest paths: Floyd-Warshall, Johnson