CSDS 310: Algorithms

• Please read all instructions.
• Please make sure that your copy contains 3 pages and 9 questions.
• You may type your answers or handwrite your answers, scan and submit as a pdf file.
• Copying answers from AI Chatbots or other students will be considered cheating and will be reported to the Office of Student Conduct and Community Standards. You are welcome to use the book and use other resources from the internet, however the answer you submit must be written with your own sentences and must reflect what you understand. The instructor will assess whether you understand all your answers during the oral final exam.
• Please write as clearly as possible.
• Justify all your answers.

1) Assume that we are a given a very large array A of size n and we know that, for all i, the ith smallest number in the array lies within the subarray A[i − 100 : i + 100]. Which sorting algorithm would you use to sort this array? What would be the runtime of the algorithm on this array?

2) Provide an example for f(n) and g(n) such that g(n) is an “asymptotic upper bound” for f(n) and but g(n) is not “asymptotically larger” than f(n)?

3) Provide a counter-example to show that f(n) = O(g(n)) does not necessarily imply that 2f(n ) = O(2g(n) ).

4) Master method does not apply to the recurrence T(n) = T(n/2) + T(n/3) + T(n/12) + Θ(n), but we can still use the idea behind Master method to solve this recurrence. Explain which Master method case this recurrence is similar to and use this to solve the recurrence.

15) Consider sorting the array A = [91, 52, 73, 64, 35, 46, 17, 28, 89] using Randomized-QuickSort. What is the probability that 28 and 52 will be compared during the course of the algorithm?

6) We are given that the optimal solution to the maximum non-adjacent sum problem on the array [a1, a2, a3, a4, a5, a6, a7, a8] is [a1, a4, a7]. What is the optimal solution on the array [a1, a2, a3, a4, a5, a6, a7]?

7) Consider the following algorithm that takes as input an array A consisting of n real numbers sorted in ascending order and a real number t.

Require: Array A consisting of n real numbers sorted in ascending order and a real number t.

1: i = 1

2: j = n

3: while i ≤ n and j ≥ 1 do

4: if A[i] + A[j] > t then

5: j = j − 1

6: else if A[i] + A[j] < t then

7: i = i + 1

8: else

9: return (i, j)

10: end if

11: end while

12: return FALSE

State the loop invariant for the while loop and use the Termination peroperty of the loop invariant to identify what the algorithm returns. You do not need to prove the loop invariant..

8) We have an array A of length n, but we do not have access to its elements, i.e., we cannot look into what A[i] is. We know that A is not sorted. We are allowed to append elements to A and we can use QuickSort’s Partition procedure on A as a black box. We are given two values, b and e such that b < e. Explain how you would find the number of elements in A that are between b and e (i.e., the number of is such that b < A[i] < e) in linear time.

9) Consider an instance of the Optimal Binary Search Tree (BST) problem with keys k1 < k2 < k3 < k4 < k5. Assume that the following root table was generated by the dynamic programming algorithm, such that root[i, j] shows the root of the optimal BST for subproblem ki , ..., kj :

root	1	2	3	4	5
1	k1	k2	k3	k4	k5
2		k2	k3	k4	k5
3			k3	k4	k5
4				k4	k5
5					k5

(a) Draw the optimal BST for this instance. Show how you compute the optimal BST from the table.

(b) Although the solution space for the optimal BST problem is exponential (there are an exponential number of BSTs for the given keys), the dynamic programming algorithm explicitly evaluates (computes the expected search cost for) only a subset of these BSTs. Among the following BSTs, which one was explicitly evaluated by the dynamic programming algorithm, which two were eliminated without being considered? Explain why.