Unit 2: Divide and Conquer - Practice Quiz

1 What is the first main step in the divide-and-conquer method?

2 Which three steps typically form a divide-and-conquer algorithm?

3 What is a base case in a recursive divide-and-conquer algorithm?

4 In divide and conquer, what does the combine step do?

5 What condition must normally be satisfied before binary search is applied to an array?

6 Which element does binary search examine first?

7 What is the worst-case time complexity of binary search on a sorted array of elements?

8 If the target is smaller than the middle element in an ascending sorted array, where does binary search continue?

9 How does merge sort divide an array?

10 What happens during the merge step of merge sort?

11 What is the worst-case time complexity of merge sort?

12 When does the recursive division in merge sort normally stop?

13 Which special element is selected during quick sort?

14 What is the purpose of partitioning in quick sort?

15 What is the average-case time complexity of quick sort?

16 What is the worst-case time complexity of quick sort?

17 Why may standard fixed-size data types be unsuitable for very large integers?

18 In divide-and-conquer multiplication, how are large integers commonly divided?

19 Which algorithm is known for multiplying large integers using divide and conquer?

20 How many recursive multiplications does the basic Karatsuba method use for each split?

21 A divide-and-conquer algorithm divides a problem of size into two subproblems of size and uses time to combine their solutions. What is its time complexity?

22 What is the asymptotic solution of the recurrence ?

23 Which problem characteristic most directly supports an efficient divide-and-conquer solution?

24 An algorithm solves one subproblem of size and performs additional work. What is the solution of ?

25 In the worst case, how many element comparisons are needed for a successful binary search in a sorted array of distinct elements?

26 Which recurrence best represents the running time of binary search?

27 To find the first occurrence of a target in a sorted array containing duplicates, what should binary search do when it finds the target at index ?

28 A Boolean predicate is false up to some index and true afterward. Using a half-open interval , which update correctly finds the first true index?

29 Which recurrence describes standard merge sort on an array of size ?

30 During merging, which rule preserves the stability of merge sort when the front elements of the two halves have equal keys?

31 While counting inversions during a merge, the next element from the right half is smaller than the next element from the left half. How many inversions should be added?

32 A bottom-up merge sort begins with eight sorted runs of length . How many complete merge passes are required to obtain one sorted run?

33 Lomuto partitioning is applied to using the last element as pivot and the comparison . What array results after partitioning?

34 A naive quick sort uses Lomuto partitioning with the last element as pivot and treats values equal to the pivot as smaller. What is its running time on an array whose elements are all equal?

35 Suppose every quick-sort pivot divides the input into subarrays of sizes approximately and . What is the overall running time?

36 If quick sort selects its pivot uniformly at random from distinct elements, what is the probability that the pivot is either the smallest or the largest element?

37 Let and , where is a power of the number base. Which expression correctly represents ?

38 How does Karatsuba multiplication reduce the number of recursive half-size multiplications compared with the basic divide-and-conquer method?

39 What is the asymptotic running time of Karatsuba multiplication according to ?

40 Ignoring lower-order addition costs, what happens to the recursive multiplication work when the operand length is doubled in schoolbook divide-and-conquer multiplication and in Karatsuba multiplication?

41 Consider the recurrence with constant work at the base case. What is its asymptotic solution?

42 For powers of two, suppose and . Which bound is tight?

43 A divide-and-conquer algorithm satisfies , ignoring rounding. Which asymptotic running time follows?

44 A parallel divide-and-conquer algorithm creates subproblems of size , performs combine work, and has . Subproblems execute concurrently, but the combine operation is sequential. What is the asymptotic parallelism ?

45 A lower-bound search uses the half-open interval and updates when , otherwise setting . Which invariant is sufficient to establish correctness?

46 A sorted array is rotated at an unknown pivot and may contain arbitrarily many duplicate values. What is the tight worst-case complexity of determining whether a target occurs using comparison-based search?

47 Exponential search examines indices until it brackets a present target whose first occurrence is at index , and then performs binary search. What is the tight comparison bound?

48 A lower-bound algorithm must distinguish all possible insertion positions using binary predicates of the form . What is the minimum possible worst-case number of predicate evaluations?

49 For , what is the exact maximum number of element-to-element comparisons performed by standard top-down merge sort?

50 While merging sorted halves and to count strict inversions satisfying and , which rule handles duplicate values correctly?

51 A merge-sort variant always splits an input into fractions and , where , and merging costs . Ignoring rounding, what is the leading term of its comparison recurrence?

52 An array consists of already identified nondecreasing runs. If a balanced merge schedule combines these runs, what is the tight worst-case merge cost, including the case ?

53 For randomized quicksort on distinct keys, where each pivot is chosen uniformly from the current subarray, what is the exact expected number of key comparisons?

54 Quicksort is modified to recurse only on the smaller partition and process the larger partition by iteration. What are its worst-case running time and auxiliary call-stack space?

55 Three-way quicksort partitions elements into regions smaller than, equal to, and greater than the pivot, and does not recurse on the equal region. On an array of identical keys, what behavior results?

56 For randomized quicksort on distinct keys, what is the probability that every nontrivial recursive call chooses an extreme key and therefore produces a maximally unbalanced partition?

57 Karatsuba multiplication replaces four half-size products with three half-size products. Assuming linear-time additions, which recurrence and complexity describe multiplication of two -digit integers?

58 A three-way large-integer multiplication scheme evaluates enough points to use five recursive multiplications on inputs of size , with evaluation and interpolation work. What is its asymptotic complexity?

59 A divide-and-conquer integer multiplication algorithm computes all four products of the high and low halves recursively. Even if its additions are optimized to linear time, what tight bound follows?

60 For a power of two, suppose a Karatsuba-style implementation satisfies and . Which expression solves the recurrence exactly?