Unit 5: More on Dynamic Programming - Practice Quiz

1 What does the all-pairs shortest paths problem compute?

2 Which dynamic programming algorithm commonly solves the all-pairs shortest paths problem?

3 What is the time complexity of the Floyd-Warshall algorithm for vertices?

4 What is normally stored in entry of the final Floyd-Warshall matrix?

5 What is the usual initial distance from a vertex to itself?

6 How is the initial distance from to usually represented when no direct edge exists?

7 Which update rule is used by the Floyd-Warshall algorithm when considering vertex ?

8 Can the Floyd-Warshall algorithm process graphs containing negative edge weights?

9 After Floyd-Warshall finishes, what indicates a negative cycle?

10 Which graph representation is most directly used by the Floyd-Warshall algorithm?

11 What is the main objective of an optimal binary search tree?

12 What information is primarily used to construct an optimal binary search tree?

13 Where are frequently searched keys generally placed in an optimal binary search tree?

14 Which traversal of a binary search tree lists its keys in sorted order?

15 What does the dynamic programming solution test for each key interval?

16 What property must an optimal binary search tree preserve?

17 What do dummy keys represent in the standard optimal binary search tree model?

18 Which technique avoids repeatedly solving the same optimal-BST subproblems?

19 If all keys have equal search probability, which tree shape generally gives a low search cost?

20 What is the usual time complexity of the basic dynamic programming algorithm for an optimal BST with keys?

21 During Floyd–Warshall processing, suppose , , and . What is the updated value of after considering vertex ?

22 A directed graph has edges , , , , and . What is the shortest-path distance from to ?

23 After Floyd–Warshall finishes, which result indicates that a vertex belongs to or can participate in a reachable negative-weight cycle?

24 What are the standard time and space complexities of Floyd–Warshall when its distance table is stored as a matrix?

25 In the Floyd–Warshall recurrence, represents the shortest path from to whose intermediate vertices are restricted to which set?

26 For a sparse directed graph with nonnegative edge weights, which approach usually computes all-pairs shortest paths more efficiently than Floyd–Warshall?

27 A Floyd–Warshall implementation maintains a next-hop matrix. If an update through improves the path from to , how should the next hop for be updated?

28 Using min-plus matrix multiplication, let row of be and column of be . What is the resulting entry ?

29 Suppose all-pairs distances are already known and a new directed edge of weight is added without creating a negative cycle. Which expression correctly tests a path from to that uses the new edge?

30 Johnson's algorithm assigns each edge the reweighted cost . Why does this preserve shortest paths between each source and destination?

31 Two ordered keys have successful-search probabilities and . If only successful searches are considered, which root minimizes the expected number of comparisons?

32 For ordered keys with successful-search frequencies , , and , respectively, which key should be the root of an optimal BST?

33 When only successful-search frequencies are used, which recurrence correctly defines the optimal weighted search cost ?

34 In what order should interval entries generally be computed in the dynamic programming table for an optimal BST?

35 An optimal-BST algorithm stores the selected root index in . After choosing , which intervals must be recursively reconstructed?

36 In an optimal BST that includes unsuccessful-search probabilities, what does conventionally represent?

37 For ordered keys with successful-search frequencies , which root yields the minimum weighted search cost?

38 If every successful- and unsuccessful-search probability is multiplied by the same positive constant, how does the optimal BST change?

39 For four ordered keys with successful-search frequencies , why can choosing the most frequent key as the root be suboptimal?

40 An optimal BST has one key with successful-search probability and unsuccessful-search probabilities and . Counting the root at depth and dummy leaves at depth , what is the expected search cost?

41 In Floyd–Warshall, let denote the value after completing iteration . Which invariant precisely supports the recurrence ?

42 After Floyd–Warshall finishes, suppose . For which ordered pairs is the shortest-path value unbounded below because of this negative cycle?

43 Let be the weighted adjacency matrix, with and unreachable entries equal to . Under min-plus multiplication, what does the entry of represent?

44 Johnson's algorithm computes potentials and defines . If Dijkstra returns in the reweighted graph, which expression recovers the original distance?

45 During Johnson's algorithm, Bellman–Ford finds an edge that can still be relaxed after passes from the added super-source. What is the correct conclusion?

46 Assuming no negative cycles, which loop-order constraint is essential for a correct in-place implementation of Floyd–Warshall?

47 A graph with known APSP distances receives a new directed edge of weight . Assume the old graph and the updated graph have no negative cycles. Which formula gives every updated distance?

48 To compute transitive closure with the Floyd–Warshall structure, which semiring-style replacement is required?

49 Using Fibonacci heaps, what is the asymptotic running time of Johnson's algorithm on a graph with vertices and edges?

50 A Floyd–Warshall implementation stores , the first vertex after on a reconstructed shortest path to . If iteration strictly improves through , how should this entry be updated?

51 For successful probabilities , unsuccessful probabilities , base cases , and interval mass , which is the correct optimal-BST recurrence?

52 For two keys, let , , , , and . Using the standard optimal-BST recurrence, which root and expected cost are optimal?

53 An optimal BST has only successful-search probabilities and charges one comparison at the root. Which root and expected comparison count are optimal?

54 Let store an optimal root for interval . Under the standard assumptions enabling Knuth optimization, which range is sufficient when searching for ?

55 What time and space bounds result when the standard optimal-BST dynamic program uses Knuth's root-monotonicity optimization while retaining its cost and root tables?

56 Define and , with empty prefixes equal to zero. Which expression computes the interval mass in constant time?

57 Why does the term appear once in every candidate of the optimal-BST recurrence, independently of the chosen root?

58 All successful and unsuccessful search weights in an optimal-BST instance are multiplied by the same constant . What necessarily happens?

59 For interval , suppose . The relevant left/right cost pairs for roots are respectively , , , and . Which candidate is optimal?

60 An optimal-root table gives , , , , and . What is the preorder traversal of the reconstructed key tree?