EXAM 2 DESIGN

Q1. [T/F] In the 0/1 knapsack problem, items can be broken into fractions to maximize profit.

FALSE

Q2. [T/F] Memoization is a top-down approach to dynamic programming that stores results of subproblems.

TRUE

Q3. [T/F] Tabulation converts a recursive solution into an iterative one using a table.

TRUE

Q4. [T/F] The base case for the recursive knapsack(wt[], val[], W, n) function is: if n == 0 or W == 0, return 0.

TRUE

Q5. [T/F] In the subset sum problem, the choice diagram always has exactly two branches: include and exclude.

TRUE

Q6. [T/F] Dynamic programming requires that a problem have both optimal substructure and overlapping subproblems.

TRUE

Q7. [T/F] A recursive function with only one function call is typically a sign of a DP problem.

FALSE

Q8. [T/F] In DP, you should always start by building the table before writing the recursive function.

FALSE

Q9. [T/F] The count of subset sum problem asks for the number of subsets that add up to a given target.

TRUE

Q10. [T/F] Unbounded knapsack allows you to include the same item multiple times.

TRUE

Q11. [MCQ] What is the correct order of steps when solving a DP problem?

B) Recursion→Memoization→Tabulation

In the 0/1 knapsack choice diagram, what happens when the current item's weight > remaining capacity W?

C) If wt[n-1] > W, the item cannot fit, so we must exclude it.

Which of the following is a variation of the 0-1 knapsack problem?

B) Count of Subset Sum is one of the six 0-1 knapsack variations.

Q14. [MCQ] What is the base case for the recursive knapsack function?

C) if n == 0 or W == 0: return

Q15. [MCQ] What distinguishes a DP problem from plain recursion?

B) DP has optimal output and 2+ recursive choices

Q16. [MCQ] In the recursive 0/1 knapsack, if we INCLUDE item n, the recursive call becomes:

C) knapsack(wt,val,W-wt[n-1],n-1)

Q17. [MCQ] In the Count of Subset Sum problem, what are you counting? A) The maximum subset weight B) The number of subsets that sum to a target value C) The minimum number of items needed D) The number of items in the knapsack

B) The number of subsets that sum to a target value

Q18. [T/F] In a complete binary tree array representation (1-indexed), the left child of node i is at index 2i.

TRUE

Q19. [T/F] A full binary tree is one where every node has exactly 0 or 2 children.

TRUE

Q20. [T/F] BFS traversal of a binary tree uses a stack as its underlying data structure.

FALSE

Q21. [T/F] Post-order traversal visits the current node before its left and right children.

FALSE

Q22. [T/F] Pre-order traversal visits nodes in the order: current → left → right.

TRUE

Q23. [T/F] In a max-heap, every parent node is greater than or equal to its children.

TRUE

Q24. [T/F] Heap sort has a worst-case time complexity of O(n log n).

TRUE

Q25. [T/F] Inserting into a heap always requires O(1) time.

FALSE

Q26. [T/F] In a binary heap stored as an array (1-indexed), the parent of node i is at index i // 2.

TRUE

Q27. [T/F] A complete binary tree has all levels fully filled except possibly the last, which is filled left to right.

TRUE

Q28. [MCQ] Pre-order traversal on a tree with root 4, left subtree root 2 (children 1,3), right subtree root 6 (children 5,7)?

B) 4,2,1,3,6,5,7

Q29. [MCQ] Post-order traversal on the same tree (root 4, left: 2→1,3; right: 6→5,7)? A) 4,2,1,3,6,5,7 B) 1,2,3,4,5,6,7 C) 1,3,2,5,7,6,4 D) 4,2,6,1,3,5,7

C) 1,3,2,5,7,6,4

Q30. [MCQ] In the array representation of a binary tree (1-indexed), where is the right child of node at index 5?

B) Index 11

Q31. [MCQ] Which traversal visits nodes level by level from top to bottom?

D) BFS (Level-order)

Q32. [MCQ] When inserting a value into a max-heap, what must happen after placing the new element?

B) Bubble up (swap with parent) until heap property is restored

Q33. [MCQ] What is Heap Sort's time complexity?

B) O(n log n)

Q34. [MCQ] Which correctly describes a min-heap?

B) Every parent is less than or equal to its children

Q35. [MCQ] Which binary tree type allows missing nodes (gaps) at any level?

C) Incomplete binary tree

Q36. [T/F] The in-degree of a node in a directed graph is the number of edges coming into that node.

TRUE

Q37. [T/F] A walk in a graph can repeat vertices and edges.

TRUE

Q38. [T/F] A simple path cannot repeat vertices.

TRUE

Q39. [T/F] A strongly connected graph requires that every vertex is reachable from every other vertex.

TRUE

Q40. [T/F] A weakly connected directed graph becomes connected if you ignore edge directions.

TRUE

Q41. [T/F] Triangle inequality in unweighted graphs states: d(u,v) ≤ d(u,w) + d(w,v) for any intermediate vertex w.

TRUE

Q42. [T/F] An adjacency matrix for a graph with n vertices always has n² entries.

TRUE

Q43. [T/F] Single Source Reachability asks for the shortest path from one source to one specific target.

FALSE

Q44. [T/F] A trail is a walk in which no edge is repeated, but vertices may be repeated.

TRUE

Q45. [T/F] A cycle is a path where the first and last vertex are the same.

TRUE

Q46. [MCQ] In an adjacency matrix, which value indicates NO edge between vertex i and vertex j?

A) 1

Q47. [MCQ] What is the time complexity of BFS/DFS using an adjacency list?

B) O(V+E)

Q48. [MCQ] Which graph problem finds the shortest path from one source to ALL other vertices?

B) SPSP

Q49. [MCQ] Which ordering goes from most permissive to most restrictive?

B) Walk→Trail→Path→Simple Path

Q50. [MCQ] What must metric distance satisfy?

B) Satisfies symmetry, triangle inequality, and d(u,u)=0

Q51. [T/F] Prim's algorithm is vertex-heavy — it grows the spanning tree by adding one vertex at a time.

TRUE

Q52. [T/F] Kruskal's algorithm is edge-heavy — it always selects the minimum weight edge that doesn't form a cycle.

TRUE

Q53. [T/F] Kruskal's algorithm can find a minimum spanning forest for a disconnected graph.

TRUE

Q54. [T/F] Prim's algorithm works correctly on a disconnected graph.

FALSE

Q55. [T/F] Dijkstra's algorithm works correctly on graphs with negative edge weights.

FALSE

Q56. [T/F] A minimum spanning tree of a graph with n vertices will always have exactly n-1 edges.

TRUE

Q57. [T/F] A* uses a heuristic function to guide its search and is generally faster than Dijkstra's when a good heuristic exists.

TRUE

Q58. [T/F] The minimum spanning tree of a graph is always unique.

FALSE

Q59. [T/F] Dijkstra's algorithm solves the Single Source Shortest Path (SSSP) problem.

TRUE

Q60. [T/F] A spanning tree of a graph can contain cycles.

FALSE

Q61. [MCQ] Which algorithm is better suited for a dense graph (many edges)?

B) Prim's

Q62. [MCQ] In Dijkstra's algorithm, which node is processed at each step?

B) Unvisited node with smallest current distance

Q63. [MCQ] What is the time complexity of Dijkstra's algorithm using a binary min-heap?

C) O((V+E) log V)

Q64. [MCQ] When is A* preferred over Dijkstra's?

B) When a good heuristic is available that estimates distance to the goal

Q65. [MCQ] What must be true for a subgraph to be a valid spanning tree? A) Include all edges B) Include all vertices, have n-1 edges, and be acyclic C) Have minimum total weight D) Be directed

B) Include all vertices, have n-1 edges, and be acyclic

Q66. [T/F] Floyd-Warshall computes the shortest path between every pair of vertices.

TRUE

Q67. [T/F] Floyd-Warshall uses DP by iteratively checking if a path through an intermediate vertex k is shorter.

TRUE

Q68. [T/F] Floyd-Warshall has a time complexity of O(V³).

TRUE

Q69. [T/F] In Floyd-Warshall, A0 represents the adjacency matrix of the original graph (direct edges only).

TRUE

Q70. [T/F] The triangle inequality check in Floyd-Warshall is: A[i][j] < A[i][k] + A[k][j] — if true, update A[i][j].

TRUE

Q71. [T/F] Floyd-Warshall can detect negative cycles if a diagonal entry becomes negative.

TRUE

Q72. [T/F] Johnson's algorithm only works on graphs without negative edges.

FALSE

Q73. [T/F] Johnson's algorithm runs faster than Floyd-Warshall on sparse graphs.

TRUE

Q74. [T/F] In Floyd-Warshall, the diagonal entries of every matrix Ak are always 0 (assuming no negative cycles).

TRUE

Q75. [T/F] Running Dijkstra's n times is a valid approach to All-Pairs Shortest Path, though complexity varies by graph density.

TRUE

Q76. [MCQ] What does matrix Ak represent in Floyd-Warshall?

B) Shortest paths using only vertices 1 through k as intermediaries

Q77. [MCQ] In Floyd-Warshall, which cells are NOT updated when processing intermediate vertex k?

A) Cells in the same row or column as k

Q78. [MCQ] What is the Floyd-Warshall recurrence relation?

C) Ak[i][j] = min(Ak-1[i][j], Ak-1[i][k] + Ak-1[k][j])

Q79. [MCQ] What is the big-picture purpose of Johnson's algorithm?

B) Reweight graph to remove negative edges, then run Dijkstra's from each vertex

Q80. [MCQ] What is the time complexity of Bellman-Ford (used inside Johnson's)?

C) O(V·E)

Q81. [MCQ] When is Johnson's algorithm a better choice than Floyd-Warshall?

B) Sparse graph (few edges)

Q82. [MCQ] Time complexity of Dijkstra's SSSP (min-heap) vs Floyd-Warshall APSP? A) Both O(V²) B) SSSP: O((V+E) log V); APSP: O(V³) C) SSSP: O(V·E); APSP: O(V²) D) Both O(V log V)

B) SSSP: O((V+E) log V); APSP: O(V³)