Cmput 204 Final Exam Solved 2023/2024 Graded A+ Best For Revision.

CMPUT204: Introduction to Algorithms Final Exam • This exam has 5 problems, each is worth 25pts. • You may answer all 5 problems, but your grade will be composed of the best 4 answers. • Closed books. • You may use a scientific calculator. • Collaborations of any kind are strictly forbidden. • Note: All logarithms are in base 2 unless specified otherwise. • You can use the fact that H(n) = Σn i=1 1 = ln n + O(1) without proving it. lOMoAR cPSD| 3 Problem 1. (25 pts) Describe the QuickSort algorithm for sorting n elements given in an array A. Prove its correctness, and analyze its runtime in both the best-case and the worst-case. You may assume that you are given a Partition function that operates deterministically in the following fashion. Its input is an array A and two indices p r. It permutes A and returns an index s such that when it halts all elements in A[p, ..., s − 1] are ≤ A[s]; and all elements in A[s + 1, ..., r] are A[s]. Moreover, this A[s], which we refer to as the pivot, was originally the last elements in A[p, ..., r]. You may assume Partition is correct, makes no more than r − p key comparisons and operates in time Θ(r − p) without proving it. Answer. See answers to the midterm. lOMoAR cPSD| 4 Problem 2. (25 pts) The Max-Bottleneck Paths Problem: Given a weighted undirected graph with nonnegative weights, suppose the weights represents the max-capacity of a message sent along an edge. (Alternatively, the edges are roads and the weights are the heights of the bridges above these roads.) Thus, the bottleneck along a path v0, v1, ..., vk is min1≤i≤k{w(vi−1, vi)}. A max-bottleneck path between u and v is a path whose bottleneck is the largest among all paths connecting u and v. (i) (15 pts) Suppose we revise init’() and relax’() to the following functions. init’(s) foreach v ∈ V (G) do v.b ← 0 s.b ← ∞ relax’(u,v) if (v.b min{u.b, w(u, v)}) then v.b ← min{u.b, w(u, v)} Show that any algorithm that only accesses the bottle-neck estimation b via init’() and relax’() always uses lower bounds on the bottleneck. That is, show that for every vertex u, at any point of the algorithm it must hold u.b ≤bottleneck(s, u). Deduce that once such an algorithm sets u.b =bottleneck(s, u) then u.b is never changed from that point on. (ii) (10 pts) Given a start vertex s, adjust Dijkstra’s algorithm to find the max-bottleneck path from s to any other node in V (G). (Use the adjusted init’() and relax’() functions.) Argue the correctness of your algorithm. What’s the runtime of your algorithm? Answer. See answers to HW5 when published.