Professor's deck questions

1. T(n) = 2T(n/2) + O(n) solves to O(n log n).

2. T(n) = T(n/2) + O(1) solves to O(n).

3. Karatsuba's algorithm multiplies two n-digit numbers in O(n²) time, the same as the grade-school method.

4. Any comparison-based sort needs Ω(n log n) comparisons in the worst case.

5. You must explore a maze of rooms and corridors, visit every reachable room, and get back out. You carry a piece of chalk and a ball of string. What is each one for?

6. A road network has about 10⁷ intersections, each with about 3 roads. Your algorithm asks "is there a road from u to v?" a few times, but mostly "what are u's neighbours?". Which representation?

7. You call explore(G, v) once, on a fresh graph. Which vertices get marked visited?

8. In the widget, how many times did dfs's outer loop call explore, and what does that count?

9. In an undirected graph, DFS classifies every edge as a tree edge or a back edge. Why can't an undirected edge be a "cross edge" between two separate branches?

10. After DFS, u = [2, 11] and v = [5, 8]. What do you know?

11. In a directed graph, DFS gives u = [6, 9] and v = [10, 13]. Can (u, v) be an edge?

12. A directed graph has a cycle if and only if DFS finds…

13. Another way to sort a DAG: repeatedly output a source and delete it. Why does a nonempty DAG always have a source?

14. After DFS on a DAG, which vertex is guaranteed to be a sink?

15. Why is the meta-graph of SCCs always acyclic?

16. A DAG has V vertices. How many strongly connected components does it have?

17. What goes wrong if you skip the reversal and explore G starting from the vertex with the highest post in G?

18. What is the total running time of the SCC algorithm with adjacency lists?

19. u = [1, 10], v = [2, 5]

20. u = [3, 4], v = [1, 8]

21. u = [6, 7], v = [2, 3]

22. u = [2, 5], v = [7, 8]

23. u = [2, 6], v = [4, 9]

24. u = [1, 16], v = [9, 10], and v isn't u's child

25. Your recursive Python DFS crashes with RecursionError on a dependency graph with a chain of 50,000 packages. What's the right fix?

26. A spreadsheet engine must recalculate cells after an edit, and report every cell involved in a circular reference (not just one cycle). Which tool fits?

27. A directed graph has a cycle exactly when DFS finds a back edge.

28. In a DAG, sorting vertices by decreasing post number gives a topological order.

29. DFS from s discovers vertices in order of their distance from s.

30. A DAG has exactly one topological order.

31. A chess knight starts in one corner, a1. What is the fewest number of moves to reach the opposite corner, h8?

32. A shortest path from s to t passes through u. Which statement must be true?

33. During BFS, the queue holds vertices at distance d followed by vertices at distance d + 1. Which property guarantees that?

34. BFS on a graph with V = 10⁶ vertices and E = 5 × 10⁶ edges, stored as an adjacency matrix. About how many steps?

35. The split-into-unit-edges version of BFS runs in time proportional to V + Σ_e ℓ(e). Why is that a bad algorithm?

36. Dijkstra takes u = the vertex outside R with the smallest tentative distance d. Why can't some other path to u be shorter than d?

37. During one run of Dijkstra, how many times can vertex v's tentative distance go down?

38. Run Dijkstra on a graph where every edge has length 1. What does it do?

39. Take a connected undirected graph with positive weights. Is Dijkstra's shortest-path tree from s the same as a minimum spanning tree?

40. A dense graph has V = 5,000 and E ≈ V²/2. Which implementation is asymptotically faster for Dijkstra?

41. A binary heap holds 1,000,000 keys. In the worst case, how many swaps does one decreasekey make?

42. On that graph, what does Dijkstra report as dist(A), and what is the true distance?

43. Fix: add 2 to every edge so all lengths are ≥ 0, run Dijkstra, and subtract later. Does that work?

44. Bellman–Ford calls update(u, v) in an arbitrary order, many times. Why can that never make dist(v) smaller than the true distance?

45. Why are V − 1 rounds always enough when there is no negative cycle?

46. Bellman–Ford finished V − 1 rounds. In round V, dist(C) still decreased. What can you conclude?

47. In the widget, the lucky order settled after 1 round and the unlucky order needed 5. What made the lucky order lucky?

48. Why does a DAG need only one pass of updates instead of Bellman–Ford's V − 1 rounds?

49. "Longest path" is NP-hard in general graphs, yet the scheduler computes it in linear time. Why?

50. Why use ℓ = −log r as the edge length, rather than ℓ = r or ℓ = 1/r?

51. Fewest hops between two users in a social network

52. Driving time between cities

53. Some negative edges and some cycles, but no negative cycle

54. Earliest finish time for a project with task prerequisites

55. Detect whether a set of exchange rates allows arbitrage

56. Weighted DAG with some negative edges

57. A routing service answers one query at a time: fastest route from s to a single destination t, on a road network with about 10⁷ intersections. What's the simplest big win over running Dijkstra to completion?

58. A teammate's trip planner runs Dijkstra on a graph where a few edges are negative (cashback offers). "It passed all our tests." The graph has cycles. What do you recommend?

59. A cashier owes you 68¢ using U.S. coins {25, 10, 5, 1}. What is the fewest number of coins?

60. Now the coin system is {4, 3, 1} and you owe 6. What happens with "largest coin that fits"?

61. Coin change with {4, 3, 1} fails for greedy. Which ingredient is missing?

62. Which greedy rule always produces a maximum set of compatible activities?

63. In step 1, which fact makes the swap of o₁ for g₁ safe?

64. Now there are unlimited rooms, and you must schedule every class using as few rooms as possible. With intervals sorted by start time, the minimum number of rooms equals…

65. One machine. Jobs have a length t_j and a deadline d_j. Run all jobs back-to-back to minimize the maximum lateness. Which order?

66. In the fractional version with W = 50, greedy by value-per-unit-weight earns how much?

67. Why does the value-per-weight rule fail for 0/1 knapsack but succeed for fractional?

68. In some optimal prefix-code tree, the two least frequent characters are always…

69. Using the Huffman code you just built, how many bits does the 100,000-character file take?

70. Dijkstra's algorithm is also greedy: it finalizes the closest unvisited vertex. What happens if some edge weights are negative (but there are no negative cycles)?

71. U.S. coins {25, 10, 5, 1}, largest coin first

72. Weighted interval scheduling, earliest finish first

73. Prim's algorithm for minimum spanning tree

74. Longest simple path, always take the heaviest outgoing edge

75. Minimize total waiting time: shortest job first

76. Set cover, always take the set covering the most uncovered items

77. You proposed a greedy rule and found no counterexample on 20 random inputs. What should you do next?

78. Sorting by value per unit weight is optimal for fractional knapsack.

79. Sorting by value per unit weight is optimal for 0/1 knapsack.

80. Earliest finish first maximizes total weight in weighted interval scheduling.

81. A greedy proof usually swaps the greedy choice into some optimal solution.

82. The textbook recursion fib(n) = fib(n−1) + fib(n−2), with fib(0) = 0 and fib(1) = 1, computes fib(30). About how many calls does it make in total?

83. Bottom-up Fibonacci runs in O(n) time. If you only need F(n), not the whole table, how much extra memory do you need?

84. You want longest paths from S in the same DAG. What has to change in the algorithm?

85. Longest simple path in a general graph is NP-hard, yet in a DAG it takes linear time. What breaks in a general graph?

86. What is the length of the longest increasing subsequence of 5, 2, 8, 6, 3, 6, 9, 7?

87. Why define L(j) as the longest increasing subsequence ending exactly at a_j, instead of the longest one among the first j elements?

88. The LIS DAG on n numbers can have up to how many edges, and what does that say about the running time?

89. What is the edit distance between kitten and sitting?

90. Each entry E(i, j) reads the cells above, to the left, and diagonally up-left. Which fill orders are valid?

91. You need only the distance between two DNA reads of 100,000 characters each, not the alignment. How much memory does the DP need?

92. With unlimited copies of each item and W = 10, what is the best total value?

93. Why does the 0/1 version need the second index j, when the version with repetition gets by with K(w) alone?

94. The 0/1 knapsack DP runs in O(nW). 0/1 knapsack is NP-hard. How can both be true?

95. Which parenthesization of A × B × C × D is cheapest?

96. A greedy rule: always multiply the adjacent pair with the cheapest product first. What does it cost on A, B, C, D?

97. How many different ways are there to fully parenthesize a chain of 10 matrices?

98. In the table, C(i, j) reads C(i, k) (same row, to its left) and C(k+1, j) (same column, below). Which fill order is invalid?

99. All weights equal 1. True or false: some maximum independent set of a tree contains every leaf.

100. How long does the tree DP take on a tree with n vertices?

101. Why can't we run the same in/out recurrence on a general graph?

102. Longest increasing subsequence

103. Edit distance

104. Chain matrix multiplication

105. Max-weight independent set in a tree

106. Longest palindromic subsequence of a string

107. Longest common subsequence of two strings

108. Knapsack with repetition, W = 10⁹, and only three item weights: 300,000,000; 400,000,000; and 500,000,000. Top-down memo or a bottom-up table?

109. A search box must split "thecatsat" into dictionary words, minimizing a cost per word. Which subproblem gives a correct, efficient DP for a string of length n?

110. fib1, the plain recursive Fibonacci, makes a linear number of calls.

111. A DP needs simple subproblems, subproblem optimality and subproblem overlap.

112. In the 1-D knapsack array, the inner loop over w runs downward so each item is used at most once.

113. The O(nW) knapsack algorithm is polynomial in the input size.

114. You may insert, delete or substitute one letter at a time. What is the fewest number of edits that turns SNOWY into SUNNY?

115. The last column of an optimal alignment of s[1..i] and t[1..j] has s[i] above a gap. What must the rest of the alignment be?

116. A first draft initializes the boundary to ∞: Opt[0, j] = ∞ and Opt[i, 0] = ∞ for i, j ≥ 1, with Opt[0, 0] = 0. With unit costs, what does it return for s = AB, t = B? (The true edit distance is 1: delete A.)

117. Keep α = β = 1 but make substitution expensive: γ = 3. What is the edit distance from SNOWY to SUNNY now?

118. Which order of filling the table does not work?

119. What is the length of an LCS of SNOWY and SUNNY?

120. In the cut-and-paste step, why is w ‖ z[k] a common subsequence of x[1..i] and y[1..j]?

121. x[i] ≠ y[j]. Which statement about an LCS z of x[1..i] and y[1..j] is guaranteed?

122. You keep only two rows of the LCS table to save space. What can you still output?

123. Allow only insertions and deletions (cost 1 each, no substitutions). For strings of lengths m and n with LCS length L, what is the edit distance?

124. Plain recursion on Pascal’s rule (no table) computes C(30, 15) = 155,117,520. About how many calls does it make?

125. With a single array C[0..k], you update row i in place. In which direction must j run?

126. In the “ℓ_n ∈ S” case, the swapped-in schedule T is optimal on I − conflicts(ℓ_n). Why is T ∪ {ℓ_n} still a valid (non-overlapping) schedule?

127. In the figure’s instance (sorted by finish: ℓ₁ = (0, 3), ℓ₂ = (1, 5), ℓ₃ = (4, 7), ℓ₄ = (3, 8), …), what is p(s₄), with s₄ = 3?

128. You skip the binary search and find p(s_i) by scanning from ℓ₁ each time. What is the running time now?

129. A teammate sorts the intervals by start time instead of finish time, keeps OPT(n) = max{OPT(n−1), w_n + OPT(p(s_n) − 1)}, and says “it’s just a different order.” What goes wrong?

130. A* with an admissible heuristic returns an optimal path (finite branching, arc costs bounded above zero).

131. Breadth-first search needs memory linear in the depth of the solution.

132. Iterative deepening wastes most of its time re-searching shallow levels.

133. If every solution is at the same known depth, depth-first search is a natural choice.

134. A hard Sudoku has about 55 blank cells, each with 9 possible digits: 9⁵⁵ ≈ 10⁵² ways to fill them. A good solver finishes in milliseconds. What does it mostly do?

135. A model has three Boolean variables and two variables with domain {low, mid, high}. How many possible worlds are there?

136. Activity b can't happen at time 3: B ≠ 3

137. Activities a and d happen at the same time: A = D

138. In a Sudoku row, all nine cells differ: alldifferent(X₁, …, X₉)

139. A crossword slot: the 3 letters L₁ L₂ L₃ must spell a dictionary word

140. A timetable has 20 variables, each with 10 values. Generate-and-test checks 10⁹ worlds per second. Roughly how long is the worst case?

141. Backtracking assigns variables in the order A, B, C, D, E. When is the constraint E < A first checked?

142. On 8-queens, plain backtracking tries 876 values before its first solution, out of 8⁸ ≈ 16.8 million worlds. With forward checking it tries 88. Where does forward checking's saving come from?

143. Mid-search, the remaining domains are A: {1, 2, 3}, C: {4}, D: {2, 4}, F: {1, 2, 3, 4}. Which variable does the most-constrained heuristic pick, and why?

144. Processing <B, B ≠ 3> deletes 3 from dom(B). Which arcs must go back on the to-do list?

145. dom(C) became { }.

146. Every domain has exactly one value.

147. X ≠ Y, Y ≠ Z, X ≠ Z with every domain {red, green}. GAC changes nothing.

148. A ∈ {1, 2}, B ∈ {3}, C ∈ {2, 3, 4}, all arcs consistent.

149. Two students run GAC on the same network. One takes arcs from the to-do list in order; the other picks them at random. What can you say about their final domains?

150. In the widget, once P = red, a single further split (Q = green) lets GAC fix all four remaining regions. Why can one split settle so much?

151. You eliminate X, which shares constraints with k other variables, all with domain size d. In the worst case, how many tuples can the new constraint have?

152. You run local search on a large timetable for an hour. The best assignment it finds still violates 2 constraints. What can you conclude?

153. At temperature T = 2, simulated annealing proposes a move that makes h worse by 2. With what probability is it accepted?

154. An algorithm solves 40% of runs within 50 steps, and almost never later. You restart it every 50 steps. Roughly what fraction of problems is solved within 200 steps?

155. Keep the 10 best neighbours of the current 10 assignments.

156. Make a new assignment from the first half of one assignment and the second half of another.

157. Pick 10 survivors at random, with better ones more likely.

158. Keep the single best neighbour each step.

159. Branch and bound has found a schedule of cost 12. A partial assignment already has cost 9, and every remaining soft constraint costs at least 0. What should it do?

160. Minimize f(x) = (x − 3)² by gradient descent from x = 0 with step size η = 1. What happens?

161. A university schedules 2,000 exams into 40 slots. Hard: no student has two exams at once. Soft: few back-to-back exams. Feasible timetables are easy to find, and a good one is needed overnight. Which approach fits?

162. If GAC (generalized arc consistency) leaves every domain non-empty, the CSP has a solution.

163. Domain splitting with GAC after each split is complete: if the CSP has a solution, it finds one, and if not, every branch ends with an empty domain.

164. If local search runs for a long time without success, no solution exists.

165. A CSP whose variables are all Boolean can be written as a set of clauses.

166. All you know is: "If it rained, the grass is wet." You look outside and the grass is wet. What follows logically?

167. A knowledge base mentions 10 atoms. To decide from a truth table whether the knowledge base is satisfiable, how many interpretations might you have to check?

168. {p ∨ q, ¬p} ⊨ q

169. {p → q, q} ⊨ p

170. {p, ¬p} ⊨ r

171. {p → q} ⊨ q

172. The clauses are (¬a ∨ b), (¬b ∨ c ∨ d), (¬d). DPLL sets a = true. What does unit propagation derive?

173. In the widget, why are random 3-SAT problems with very few or very many clauses per atom both easy for DPLL?

174. lit_l1 ← light_l1 ∧ live_w1 ∧ ok_l1

175. lit_l1 ∨ broken_l1 ← live_w1

176. ok_cb1.

177. false ← dark_l1 ∧ lit_l1

178. With s2 down, bottom-up never derives lit_l2. Does the KB entail ¬lit_l2?

179. A KB has a million clauses about a building. A user asks one question about one room. Which proof procedure fits, and why?

180. KB, in this order: a ← b.  b ← a.  a ← c.  c. Top-down search, depth first, tries clauses in order. What happens on ask a?

181. With both switches up and everything working, the system fails to prove lit_l1, which is true. Debugging reaches live_w1: true in the world, but no clause for it has a body that is all true. What's the bug?

182. The minimal conflicts are {ok_cb1, ok_s1, ok_l1} and {ok_cb1, ok_s2, ok_l2}. Which of these is not a minimal diagnosis?

183. The KB is a ← b.  a ← c ∧ d. and nothing else mentions a. What is the completion for a?

184. A flight database answers "is there a direct flight from Erie to Boise?" with no, because no such fact is stored. When is that answer justified?

185. In the widget, you observe wet_grass and wet_path; the explanations include {rained} and {sprinkler_on, pipe_burst}. Then you also observe dry_roof. What happens?

186. wet_grass ← rained

187. fire ← smoke

188. fever ← flu

189. up_s1 ← lit_l1

190. A building's monitoring system knows the wiring and which parts can fail. It sees both lights in a room dark with their switches up, and must list every minimal set of broken parts that could explain it. Which approach fits?