In this article i am gone to share Coursera Course Divide and Conquer, Sorting and Searching, and Randomized Algorithms Week 4 | Final Exam Quiz Answer with you..

Divide and Conquer, Sorting and
Searching, and Randomized Algorithms

visit link:  Problem Set #4 Quiz Answer

Final Exam Quiz Answer

Question 1) Recall the Partition subroutine that we used in both QuickSort and RSelect. Suppose that the following array has just been partitioned around some pivot element: 3, 1, 2, 4, 5, 8, 7, 6,9

Which of these elements could have been the pivot element? (Hint: Check all that apply, there could be more than one possibility!)

• 5
• 9
• 3
• 2
• 4

Question 2) Here is an array of ten integers: 5 3 8 9 1 7 0 2 6 4

Suppose we run Merge Sort on this array. What is the number in the 7th position of the partially sorted array after the outermost two recursive calls have completed (i.e., just before the very last Merge step)? (When we say “7th” position, we’re counting positions starting at 1; for example, the input array has a “0” in its 7th position.)

• 1
• 2
• 3
• 4

Question 3) What is the asymptotic worst-case running time of MergeSort, as a function of the input array length n?

• θ(log n)
• θ(n log n)
• θ(n)
• θ(n2)

Question 4) What is the asymptotic running time of Randomized QuickSort on arrays of length n, in expectation over the choice of random pivots) and in the worst case, respectively?

• Ө(n log n) [expected) and Ө(n log n) [worst case]
• Ө(n2) [expected] and Ө(n2) [worst case] 
• Ө(n) [expected] and Ө(n log n) [worst case] 
• Ө(n log n) [expected] and Ө(n2) [worst case]

Question 5) Let f and g be two increasing functions, defined on the natural numbers, with f(1),g(1) ≥1. Assume that f(n) =O(g(n)). Is 2f(n) ) = 0(29(n)) ? (Multiple answers may be correct, check all that apply.)

• Never
• Maybe, maybe not (depends on the functions f and g).
• Always
• Yes if f(n) ≤ g(n) for all sufficiently large n

Question 6) Let 0 < a <.5 be some constant. Consider running the Partition subroutine on an array with no duplicate elements and with the pivot element chosen uniformly at random (as in QuickSort and RSelect). What is the probability that, after partitioning, both subarrays (elements to the left of the pivot, and elements to the right of the pivot) have size at least a times that of the original array?

• 2 – 2a
• A
• 1 – a
• 1 – 2a

Question 7) Suppose that a randomized algorithm succeeds (e.g., correctly computes the minimum cut of a graph) with probability p (with 0 <p < 1). Let e be a small positive number (less than 1).

How many independent times do you need to run the algorithm to ensure that, with probability at least 1 — ∈, at least one trial succeeds?

Question 8) Suppose you are given k sorted arrays, each with n elements, and you want to combine them into a single array of kn elements. Consider the following approach. Divide the k arrays into k/2 pairs of arrays, and use the Merge subroutine taught in the Merge Sort lectures to combine each pair. Now you are left with k/2 sorted arrays, each with 2n elements. Repeat this approach until you have a single sorted array with kn elements. What is the running time of this procedure, as a function of k and n?

• θ(n log k)
• θ(nk log n)
• θ(nk log k)
• θ(nk2)

Question 9) Running time of Strassen’s matrix multiplication algorithm: Suppose that the running time of an algorithm is governed by the recurrence T(n) = 7✴T(n/2) + n2. What’s the overall asymptotic running time (i.e., the value of T(n))?

• θ(n2 log n)
• θ(nlog2(7))
• θ(n2)
• θ(nlog 2/ log 7)

Question 10) Recall the Master Method and its three parameters a, b, d. Which of the following is the best interpretation of ba, in the context of divide-and-conquer algorithms?

• The rate at which the total work is growing (per level of recursion).
• The rate at which the number of subproblems is growing (per level of recursion).
• The rate at which the work-per-subproblem is shrinking (per level of recursion).
• The rate at which the subproblem size is shrinking (per level of recursion).