Unit 10: Lower Bound Theory - Practice Quiz

1 What does an internal node represent in a comparison tree?

2 What does a leaf represent in a comparison tree for sorting?

3 How many branches usually leave a node representing a binary comparison?

4 What does the height of a comparison tree measure in worst-case analysis?

5 For sorting distinct elements, how many possible input orderings must a comparison tree distinguish?

6 What lower bound does the comparison-tree model establish for comparison-based sorting?

7 Which algorithm is naturally analyzed using a comparison tree?

8 In algorithm analysis, what is an oracle?

9 How does an algorithm obtain information from an oracle?

10 In an oracle model, what resource is commonly counted to prove a lower bound?

11 Why are oracles useful in lower-bound theory?

12 What is hidden from an algorithm interacting with a black-box oracle?

13 If each oracle query has two possible answers, what can one query provide at most?

14 Which statement best describes an oracle-based lower bound?

15 What is the main purpose of an adversary argument?

16 How does an adversary typically answer an algorithm's queries?

17 What must be true of the answers supplied by a valid adversary?

18 In an adversary argument, when can an algorithm safely stop?

19 An adversary argument usually focuses on which type of algorithm behavior?

20 In the problem of finding the maximum among elements, what does each non-maximum element need to experience?

21 A comparison-based sorting algorithm is applied to 5 distinct elements. What minimum worst-case number of comparisons follows from the comparison-tree leaf-count argument?

22 A binary comparison tree has height 12. What is the largest number of distinct input cases it can distinguish?

23 After several comparisons, the resulting partial order is consistent with different total orders. What information-theoretic lower bound applies to the number of additional binary comparisons required?

24 Using only the leaf-count argument, what lower bound is obtained for sorting 6 distinct elements?

25 Two sorted lists contain 3 and 5 distinct elements. Their merged order can correspond to any interleaving that preserves each list's internal order. What lower bound follows from counting these interleavings?

26 A comparison-based algorithm must identify the largest among 32 distinct elements. Which lower bound applies to its worst-case number of comparisons?

27 Under a uniform distribution over all input permutations, which expression is an information-theoretic lower bound on the average number of comparisons needed for sorting?

28 A hidden object is one of 100 possibilities, and every oracle query returns one bit. What is the minimum number of queries required in the worst case?

29 An oracle reveals any requested bit of an unknown -bit string. How many queries are required in the worst case to compute the parity of the entire string exactly?

30 Exactly one of positions is marked. A query asks whether a chosen position is marked. What is the deterministic worst-case number of queries needed to identify the marked position?

31 An unsorted array has positions and may contain no marked position. A query tests one chosen position. How many deterministic queries are necessary in the worst case to decide whether a mark exists?

32 Exactly one of 64 items is defective. An oracle accepts any subset and reports whether that subset contains the defective item. What is the optimal worst-case number of queries?

33 A value oracle returns the exact value stored at a requested array index. The values are arbitrary and unrelated. How many value queries are necessary to find the minimum in the worst case?

34 An algorithm makes oracle calls, and each oracle call can be simulated using at most comparisons. What comparison upper bound does the simulation provide?

35 In a lower-bound proof for finding the maximum, an adversary declares one compared element smaller while keeping the other as a possible maximum. How many candidates can one comparison eliminate?

36 For even , what worst-case comparison lower bound can an adversary establish for finding both the minimum and maximum?

37 For 16 distinct elements, what lower bound does the tournament adversary give for finding the second-largest element?

38 To prove a lower bound for unsuccessful search in an unsorted array, an adversary answers "not present here" whenever a new position is queried. Why can it continue doing so through all positions?

39 In a comparison-sorting adversary proof, what strategy most directly supports the lower bound?

40 An adversary has maintained a set of inputs consistent with every answer so far. What condition must hold whenever it gives the next answer?

41 A deterministic comparison sort operates on distinct keys. What is the tightest integer lower bound obtained solely by counting leaves in its binary comparison tree?

42 There are labeled records whose ordered key values have known multiplicities , where . If each comparison has outcomes less than, equal to, or greater than, what information-theoretic height bound follows for determining the complete weak order?

43 For distinct elements, what is the exact worst-case number of comparisons needed to find both the largest and the second-largest elements?

44 When is odd, what is the optimal worst-case number of comparisons required to find both the minimum and maximum of distinct elements?

45 A comparator can return less than, equal to, or greater than. Why does sorting distinct keys still have the leaf-counting lower bound rather than ?

46 Two sorted sequences have lengths and , and all keys are distinct. What is the strongest direct lower bound obtained by counting all possible interleavings in a binary comparison tree?

47 A randomized comparison sort is correct on every input. If input permutations are uniformly distributed, which lower bound applies to its expected number of comparisons, averaged over both inputs and internal randomness?

48 Suppose permutation occurs with probability . For any correct binary comparison tree, which quantity lower-bounds the expected number of comparisons?

49 A Boolean oracle hides a string promised to be either all zeros or to contain exactly one . How many queries are necessary in the deterministic worst case to decide which case holds?

50 For the same promise problem—an all-zero string versus exactly one —what is the bounded-error randomized query complexity when every valid input must be answered correctly with probability at least ?

51 An oracle exposes individual bits of an unknown string . What is the deterministic query complexity of computing the parity ?

52 Problem has a lower bound of queries in oracle model . Every query to oracle can be simulated using at most queries to oracle . What lower bound follows for solving in model ?

53 For the Boolean OR function, a -input can have a one-bit certificate, while the all-zero input needs an -bit certificate. What deterministic worst-case oracle-query lower bound follows?

54 An oracle query has at most possible answers, and every valid hidden object among candidates must be uniquely identified. What general deterministic query lower bound follows?

55 In an adversary proof for finding the maximum, each element initially forms a separate candidate component. A comparison eliminates at most one candidate for maximum. What lower bound results?

56 For simultaneously finding the minimum and maximum, an adversary initially labels every element as eligible for both roles. Which worst-case lower bound can be forced by making comparisons between two unclassified elements remove only one minimum candidate and one maximum candidate?

57 A target is promised not to equal any of the keys in a sorted array. An adversary keeps every feasible insertion gap consistent with the answers. What comparison lower bound follows?

58 In finding the largest and second-largest among arbitrary distinct elements, a weighted adversary ensures that the final maximum has defeated at least elements directly. What total lower bound does this establish?

59 Why can an adversary prove an comparison lower bound for deciding whether real numbers are all distinct, despite the problem having only two possible outputs?

60 Two nonempty sorted lists of lengths and must be merged. An adversary answers cross-list comparisons so that neither list can be certified exhausted prematurely. What exact worst-case lower bound can it force?