Unit 3: Dynamic Programming - Practice Quiz

1 Dynamic programming is especially useful when a problem has which property?

2 What are the two common approaches used to implement dynamic programming?

3 What does optimal substructure mean?

4 What is the value of for any nonnegative integer ?

5 Which recurrence is used to compute a binomial coefficient using dynamic programming?

6 What is the main purpose of a memory function?

7 A memory-function implementation of dynamic programming is commonly called what?

8 In the knapsack problem, how many times may each item be selected?

9 What is the objective of the knapsack problem?

10 A knapsack has capacity . Which single item can fit in it?

11 Which statement distinguishes fractional knapsack from knapsack?

12 What does the matrix-chain multiplication problem seek to minimize?

13 When can a matrix of size be multiplied by a matrix of size ?

14 How many scalar multiplications are needed to multiply a matrix by a matrix using the standard method?

15 In a subsequence, must the selected characters be contiguous in the original sequence?

16 What is the length of a longest common subsequence of the strings and ?

17 If the current characters of two sequences match, how is the corresponding LCS table entry commonly computed?

18 What does an optimal binary search tree minimize?

19 Which information is commonly used to construct an optimal binary search tree?

20 In an optimal binary search tree, frequently searched keys are generally placed where?

21 A recursive algorithm repeatedly solves the same smaller instances, and an optimal solution can be formed from optimal solutions to those instances. Which properties make dynamic programming appropriate?

22 A bottom-up Fibonacci algorithm stores only the two most recently computed values. What are its time and auxiliary space complexities for computing ?

23 In a shortest-path problem on a staged graph, why can choosing the minimum-weight outgoing edge at every vertex fail?

24 Using , what is the value of ?

25 A one-dimensional array is used to compute binomial coefficients. For each row , why should entries be updated from larger to smaller ?

26 A memoized LCS algorithm is called for only one pair of string prefixes. When can it evaluate fewer states than a full bottom-up table?

27 A memoized maximization algorithm uses to mean that a state has not been computed, but valid state values may also equal . What is the best correction?

28 A knapsack has capacity . Items have pairs , , , and . What is the maximum obtainable value?

29 Let be the maximum value using the first items with capacity . If item has weight and value , which recurrence represents the knapsack choice?

30 During reconstruction of a knapsack solution, suppose . What action is justified?

31 When implementing knapsack with a one-dimensional array, capacities are processed from down to for each item. What does this ordering prevent?

32 Matrices , , and have dimensions , , and . What is the minimum number of scalar multiplications?

33 A matrix chain has dimension array . What is the minimum number of scalar multiplications needed to multiply all four matrices?

34 For four matrices, the split table contains , , and . Which optimal parenthesization does this describe?

35 What is the length of a longest common subsequence of and ?

36 Let denote the LCS length of prefixes and . If , which recurrence should be used?

37 The strings and have an LCS of length . Using only insertions and deletions, what is the minimum number of operations required to transform into ?

38 Three ordered keys have successful-search probabilities , , and . Ignoring unsuccessful searches and counting the root at depth , which key should be the root of an optimal BST?

39 In the optimal BST recurrence, why is the total probability weight added after selecting a root for keys through ?

40 Why can an optimal binary search tree be structurally unbalanced even when a balanced BST is possible?

41 A table entry depends on , , and , with row and column initialized. Which traversal computes every dependency before it is used?

42 A graph problem asks for a maximum-reward path from a source to a target using at most edges. A proposed DP stores only the maximum reward obtained at each vertex. Why can this state definition violate the principle of optimality?

43 A one-dimensional Pascal-array implementation currently stores the row for as . It incorrectly updates indices from left to right using . What value will it store at index instead of ?

44 Consider a top-down memoized computation of with base cases and . It performs no symmetry reduction. How many distinct non-base states are evaluated when computing ?

45 A top-down LCS implementation initializes every memo entry to and treats an entry as cached only when its value is nonzero. For two length- strings with no common character, what is the resulting asymptotic running time?

46 A memoized recurrence is represented by a directed acyclic state graph. From the initial state, states and dependency edges are reachable. If each state scans all of its outgoing dependencies once when first evaluated, what are the tight time and memo-space bounds?

47 For 0/1 knapsack with capacity , items and are processed using a one-dimensional array, but capacities are scanned increasingly for each item. What value is reported, and what is the true 0/1 optimum?

48 An exact-fill 0/1 knapsack DP initializes every capacity state to rather than setting unreachable positive capacities to . With items and and target capacity , it returns . What has the implementation actually computed?

49 A descending-capacity 1D DP correctly computes the optimal 0/1 knapsack value, but reconstruction using a single mutable predecessor pointer per capacity can repeat an item because earlier information is overwritten. Which method reliably reconstructs a valid optimal subset?

50 When capacity is extremely large but the total item value is moderate, which exact 0/1 knapsack formulation gives a pseudo-polynomial bound independent of ?

51 Four matrices have dimensions , , , and . Which parenthesization minimizes scalar multiplications, and what is its cost?

52 The standard bottom-up matrix-chain algorithm tests every split for every interval . How many candidate splits are examined for a chain of matrices?

53 A chain contains six matrices, each of dimension . Assuming only scalar multiplication count matters, how many distinct parenthesizations are optimal?

54 For and , the LCS length is . Which sequence is not an LCS of the two strings?

55 For strings of lengths and , which statement correctly characterizes Hirschberg's algorithm for reconstructing an LCS?

56 A top-down LCS memory function follows only the diagonal dependency when the current characters match. If and both have length , how many distinct states are evaluated from the initial call ?

57 Two strings have lengths and , and their LCS length is . What is their minimum edit distance when the only permitted operations are insertion and deletion, each with unit cost?

58 An optimal BST has successful-search probabilities , and unsuccessful-search probabilities , , . Using the standard recurrence with , which root is optimal and what is the expected cost?

59 For an optimal BST recurrence satisfying Knuth's monotonicity condition, which interval contains an optimal root , and what time bound follows when only that interval is searched?

60 Four ordered keys have successful-search probabilities , with unsuccessful-search probabilities omitted. Under the recurrence , what are the optimal root and cost?