MCQ drill bank

1. Which search strategy selects from the frontier the path that was added first, and therefore finds a path with the fewest arcs?

1. depth-first search
2. lowest-cost-first search
3. greedy best-first search
4. breadth-first search

2. A heuristic function h is admissible if, for every node n,

1. h(n) is at most the cost of the cheapest path from n to a goal
2. h(n) is at least the cost of the cheapest path from n to a goal
3. h(n) = 0 only at goal nodes
4. h(n) can be computed in constant time

3. You need a search that is guaranteed to find a fewest-arc path but uses memory only linear in the path length. Which one?

1. breadth-first search
2. depth-first search
3. A* search
4. iterative deepening

4. A* search with h(n) = 0 for every node behaves exactly like

1. lowest-cost-first search
2. depth-first search
3. breadth-first search
4. greedy best-first search

5. A* is run with multiple-path pruning (an explored set: a path to an already-reached node is discarded). Which condition on h guarantees it still returns a least-cost path?

1. h overestimates by at most 1
2. h is any non-negative function
3. no condition is needed
4. h is consistent: \(h(n) \le \text{cost}(n, n') + h(n')\)

6. Depth-first branch and bound has already found a solution of cost 10. The current path p has cost(p) = 6 and h(p) = 5, with h admissible. What does it do with p?

1. Prune p, since cost(p) + h(p) = 11 ≥ 10, so no path through p can beat 10
2. Expand p, since 6 < 10
3. Record p as the new best solution
4. Restart the search with bound 11

7. A CSP has 6 variables, each with domain {0, 1, 2}. In the worst case, how many possible worlds does generate-and-test check?

1. 18
2. 216
3. 729
4. 64

8. dom(A) = dom(B) = {1, 2, 3, 4} and the only constraint is \(A \le B - 2\). After arc consistency, the domains are

1. A = {1, 2, 3}, B = {2, 3, 4}
2. A = {1, 2}, B = {1, 2, 3, 4}
3. unchanged
4. A = {1, 2}, B = {3, 4}

9. Which of these constraints is binary?

1. X ≠ Y
2. X > 5
3. X + Y = Z
4. alldifferent(Q1, …, Q8)

10. Variables X, Y, Z each have domain {red, green}, with constraints X ≠ Y, Y ≠ Z, X ≠ Z. GAC deletes nothing. What is true?

1. The CSP has exactly three solutions
2. The CSP has a solution, because every domain is non-empty after GAC
3. GAC was run incorrectly
4. The CSP has no solution, but GAC can't detect it because each arc on its own is consistent

11. During backtracking, after choosing a variable, which value ordering is recommended for finding a first solution quickly?

1. The least constraining value: the one ruling out the fewest values in neighbours' domains
2. The value that appears in the most constraints
3. The value that rules out the most values in neighbours' domains
4. Always the smallest value

12. Simulated annealing accepts a move that worsens h by Δ with probability \(e^{-\Delta/T}\). As the temperature T approaches 0, the algorithm behaves like

1. a random walk
2. random restart
3. breadth-first search
4. greedy descent: only improving (or equal) moves are taken

13. A local-search algorithm solves 50% of runs within k steps (independently each run) and almost never later. You restart it every k steps. What is the probability it has solved the problem within 3k steps?

1. 50%
2. 75%
3. 87.5%
4. 100%

14. Over the atoms p, q, r, how many models does \(p \wedge (q \vee r)\) have?

1. 1
2. 3
3. 4
4. 7

15. Which proposition is valid (true in every interpretation)?

1. \((p \to q) \vee (q \to p)\)
2. \(p \to q\)
3. \(p \wedge \neg p\)
4. \(p \vee q\)

16. Which entailment holds?

1. {p → q, q} ⊨ p
2. {p ∨ q} ⊨ p
3. {p → q} ⊨ q → p
4. {p → q, ¬q} ⊨ ¬p

17. KB: p ← q ∧ r. q ← s. r ← q. s. t ← u. u ← t. Which set does bottom-up (forward chaining) derive?

1. {s, q, r, p}
2. {s}
3. {s, q, r, p, t, u}
4. {p, q, r, s, t}

18. Clauses: \((\neg a \vee b)\), \((\neg b \vee \neg c)\), \((c \vee d)\). DPLL sets a = true. What does unit propagation derive?

1. b = true only
2. b = true, c = true, d = false
3. b = true, c = false, d = true
4. nothing; it must split again

19. You want to use a SAT solver (such as DPLL) to decide whether KB ⊨ g. You should check whether

1. KB ∪ {g} is satisfiable
2. g is valid
3. KB is unsatisfiable
4. KB ∪ {¬g} is unsatisfiable

20. Which of these is a Horn clause but not a definite clause?

1. false ← a ∧ b
2. a ← b ∧ c
3. a.
4. a ∨ b ← c

21. The minimal conflicts are {ok_a, ok_b} and {ok_b, ok_c}. Which is a minimal diagnosis?

1. {ok_a}
2. {ok_a, ok_b}
3. {ok_c}
4. {ok_b}

22. After DFS on a directed graph, for which type of edge (u, v) is post(u) < post(v)?

1. tree edge
2. back edge
3. forward edge
4. cross edge

23. After DFS on a DAG, the vertex with the highest post number is guaranteed to be

1. a source
2. a sink
3. the vertex with the highest pre number
4. on every path

24. DFS on an undirected graph classifies every edge as

1. tree or cross
2. tree, back, forward or cross
3. tree only
4. tree or back

25. DFS on a graph with V vertices stored as an adjacency matrix takes

1. \(O(V + E)\)
2. \(O(V^2)\)
3. \(O(E \log V)\)
4. \(O(VE)\)

26. Dijkstra's algorithm is BFS with the FIFO queue replaced by

1. a stack
2. a hash table
3. a priority queue keyed by tentative distance
4. a list of edges sorted by length

27. Dijkstra implemented with an unsorted array as the priority queue runs in

1. \(O(V + E)\)
2. \(O((V + E)\log V)\)
3. \(O(V^2)\)
4. \(O(VE)\)

28. All edge lengths are positive. You multiply every edge length by 3. What happens to the shortest paths?

1. They change, favouring paths with fewer edges
2. They stay the same: every path's length triples, so the order of paths is preserved
3. They change, favouring paths with more edges
4. Dijkstra no longer applies

29. The running time of Bellman–Ford is

1. \(O(V + E)\)
2. \(O((V + E)\log V)\)
3. \(O(VE)\)
4. \(O(V^2 E)\)

30. A weighted DAG has some negative edges. Which single-source shortest-path method is correct and fastest?

1. Dijkstra
2. Bellman–Ford, \(O(VE)\)
3. BFS
4. Linearize by DFS, then one pass of updates in topological order, \(O(V + E)\)

31. To detect currency arbitrage, where r(u, v) is the exchange rate from u to v, you should

1. set \(\ell(u,v) = -\log r(u,v)\) and look for a negative cycle with Bellman–Ford
2. set \(\ell(u,v) = r(u,v)\) and run Dijkstra
3. set \(\ell(u,v) = 1/r(u,v)\) and run BFS
4. set \(\ell(u,v) = \log r(u,v)\) and run Dijkstra

32. A binary heap is stored in an array at positions 1, …, n. The children of the node at position i are at

1. i + 1 and i + 2
2. 2i − 1 and 2i
3. 2i and 2i + 1
4. \(\lfloor i/2 \rfloor\)

33. Building a binary min-heap from n given keys (Build-Min-Heap, sifting down from the bottom) takes

1. O(1)
2. O(log n)
3. Θ(n)
4. Θ(n log n)

34. With the division method \(h(k) = k \bmod m\), why should m not be a power of 2?

1. Division by a power of 2 is slow
2. The table would be too large
3. It makes open addressing loop forever
4. h(k) is then just the lowest bits of k, so keys that share their low bits all collide

35. Multiplication method \(h(k) = \lfloor m\,(kA \bmod 1) \rfloor\) with m = 16, A = 3/8, k = 11. What is h(k)?

1. 1
2. 2
3. 4
4. 6

36. Open addressing with linear probing, m = 7, \(h(k, i) = (k \bmod 7 + i) \bmod 7\), table initially empty. Insert 10, 17, 24 in that order. Which slot does 24 land in?

1. 3
2. 4
3. 5
4. 6

37. A finite family \(\mathcal{H}\) of hash functions into {0, …, m − 1} is universal if, for every pair of distinct keys k ≠ l,

1. at most \(|\mathcal{H}|/m\) functions in \(\mathcal{H}\) map k and l to the same slot
2. no function in \(\mathcal{H}\) maps k and l to the same slot
3. exactly half of the functions collide them
4. \(\mathcal{H}\) contains exactly m functions

38. With union by rank (no path compression), a find on a structure with n elements takes

1. O(1)
2. O(log n)
3. O(n)
4. \(O(\log^* n)\)

39. Kruskal's algorithm runs on a connected graph with n vertices and m edges. How many successful union operations does it perform?

1. m
2. n
3. m − n + 1
4. n − 1

40. A sorted set (SSet) holds {3, 8, 15, 20}. What does find(10) return?

1. null
2. 15
3. 8
4. 10

41. In terms of deque operations, a FIFO queue uses

1. add-last and remove-last
2. add-first and remove-first
3. add-last and remove-first
4. remove-first only

42. Fractional knapsack with capacity W = 5. Items (weight, value): (2, 10), (3, 9), (4, 16). What is the maximum total value?

1. 19
2. 21
3. 22
4. 25

43. Huffman coding on a text of 8 characters with frequencies a: 4, b: 2, c: 1, d: 1. How many bits does the encoded text take?

1. 12
2. 14
3. 16
4. 18

44. Horn formula: \((\Rightarrow x)\), \((x \Rightarrow y)\), \((y \wedge z \Rightarrow w)\), \((\bar x \vee \bar w)\). What does the greedy Horn-satisfiability algorithm return?

1. all variables true
2. x = T, y = T, z = F, w = F
3. "not satisfiable"
4. x = T, y = F, z = F, w = F

45. Set cover on n elements has an optimal cover with k sets. The greedy algorithm (always take the set covering the most uncovered elements) uses at most

1. k sets
2. 2k sets
3. n/k sets
4. \(k \ln n\) sets

46. A connected undirected graph has distinct edge weights. Edge e is the heaviest edge on some cycle. Then

1. e is in no MST
2. e is in every MST
3. e is in the MST only if it is the lightest edge at one of its endpoints
4. nothing can be concluded

47. What is the length of the longest increasing subsequence of 3, 1, 4, 1, 5, 9, 2, 6?

1. 3
2. 4
3. 5
4. 6

48. Matrices A (10 × 20), B (20 × 5), C (5 × 30). What is the minimum number of scalar multiplications to compute ABC?

1. 1,500
2. 2,500
3. 6,000
4. 9,000

49. Weighted interval scheduling with intervals sorted by finish time; \(p(s_j)\) is the index of the first interval finishing after \(s_j\). Which recurrence is correct?

1. \(\text{OPT}(j) = w_j + \text{OPT}(j-1)\)
2. \(\text{OPT}(j) = \max\{\text{OPT}(j-1),\ w_j + \text{OPT}(j-1)\}\)
3. \(\text{OPT}(j) = \max\{\text{OPT}(j-1),\ w_j + \text{OPT}(p(s_j) - 1)\}\)
4. \(\text{OPT}(j) = \max\{\text{OPT}(j-1),\ w_j + \text{OPT}(p(s_j))\}\)

50. With unit costs for insert, delete and substitute, what is the edit distance between abc and yabd?

1. 1
2. 2
3. 3
4. 4