Algorithms MCQs 1

Algorithms MCQs
================================

1. Tree and Graph Traversals

1) Which traversal guarantees minimum number of edges from a source in an unweighted

graph?
A) DFS
B) BFS
C) Dijkstra
D) Bellman–Ford
2) Which primary data structure underlies a standard BFS?
A) Stack
B) Queue
C) Priority queue
D) Deque
3) Which traversal outputs BST keys in nondecreasing order?
A) Preorder
B) Inorder
C) Postorder
D) Level-order
4) In DFS on a directed graph, presence of which edge implies a cycle?
A) Tree edge
B) Forward edge
C) Back edge
D) Cross edge
5) Time complexity of BFS or DFS on an adjacency list representation is:
A) O(V )
B) O(E)
C) O(V + E)
D) O(V E)
6) Level-order traversal of a tree corresponds to:
A) DFS recursion
B) BFS
C) Inorder
 Algorithms MCQs 2

D) Postorder

7) A valid method to compute a topological order is:

A) Kahn’s algorithm (repeatedly removing indegree-0 vertices)

B) BFS from an arbitrary source

C) Sorting by increasing discovery time

D) Prim’s algorithm

8) In the DFS color scheme, a vertex that has finished is colored:

A) White

B) Gray

C) Black

D) Blue

9) Time complexity of BFS using an adjacency matrix is:

A) O(V + E)

B) O(V log V )

C) O(V 2 )

D) O(E log V )

10) Which traversal is most suitable to delete a tree (free children before parent)?

A) Preorder

B) Inorder

C) Postorder

D) Level-order

11) Counting connected components in an undirected graph by repeated DFS/BFS has com-
plexity:

A) O(V 2 )

B) O(V + E)

C) O(E log V )

D) O(V E)

12) In a DAG, sorting vertices by decreasing DFS finish time yields:

A) A minimum spanning tree

B) An Euler tour

C) A topological order

D) A BFS tree
 Algorithms MCQs 3

2. Connected Components

13) For an undirected forest with V vertices and E edges, the number of components C
satisfies:
A) E = V + C − 1
B) E = V − 1 + C
C) E = V − C
D) E = V + C
14) Which algorithm finds strongly connected components (SCCs)?
A) Kruskal
B) Kahn
C) Kosaraju
D) Dijkstra
15) Tarjan’s SCC algorithm runs in:
A) O(V 2 )
B) O(V + E)
C) O(E log V )
D) O(V E)
16) In undirected graphs, articulation points and bridges can be found using:
A) BFS levels only
B) DFS low-link values
C) Dijkstra
D) Floyd–Warshall
17) Union–Find with union by rank and path compression has amortized time per operation:
A) O(log n)
B) O(α(n))
C) O(1/n)
D) O(n)
18) Adding a single edge between two different connected components reduces the component
count by:
A) 0
B) 1
C) 2
D) V
19) Bipartiteness of an undirected graph can be checked via:
A) DFS timestamps only
 Algorithms MCQs 4

B) BFS 2-coloring
C) Dijkstra
D) Prim
20) The condensation graph of a directed graph (SCC DAG) is always:
A) A tree
B) A DAG
C) Strongly connected
D) Regular
21) For a connected undirected graph with E = V − 1, the graph is:
A) A tree
B) Contains a cycle
C) Not necessarily connected
D) A multigraph
22) In dynamic connectivity, to check if two vertices are in the same component efficiently,
use:
A) Binary indexed tree
B) Disjoint Set Union (Union–Find)
C) Segment tree
D) Stack
23) Counting connected components on an adjacency matrix (naively) costs:
A) O(V 2 )
B) O(V 3 )
C) O(E)
D) O(V log V )
24) Vertices u and v are in the same SCC iff:
A) There exists a path u → v
B) There exists a path v → u
C) Both u → v and v → u
D) Neither direction is needed

3. Spanning Trees

25) An MST is:

A) A spanning subgraph minimizing total edge weight
B) A path covering all vertices
C) Any tree in the graph
 Algorithms MCQs 5

D) A forest with minimal degree

26) Kruskal’s algorithm detects cycles using:
A) A queue
B) Union–Find
C) A stack
D) A heap
27) Prim’s algorithm with a binary heap runs in:
A) O(E log V )
B) O(V 2 )
C) O(V log V + E)
D) O(E + V )
28) With a Fibonacci heap, Prim’s algorithm runs in:
A) O(E log V )
B) O(E + V log V )
C) O(E)
D) O(V 2 )
29) For a connected undirected graph with distinct edge weights, the MST is:
A) Always unique
B) Not unique
C) Non-existent
D) Root-dependent
30) The cut property states:
A) For any cut, the maximum-weight crossing edge is in some MST
B) For any cut, the minimum-weight crossing edge is in every MST
C) For any cycle, the maximum-weight edge is in every MST
D) None of the above
31) The cycle property states:
A) In any cycle, the minimum edge is excluded from all MSTs
B) In any cycle, the maximum edge can be excluded from some MST
C) In any cycle, all edges are in some MST
D) None of the above
32) Any spanning tree on V vertices contains:
A) V edges
B) V − 1 edges
 Algorithms MCQs 6

C) E − V + 1 edges
D) E edges
33) The number of spanning trees of the complete graph Kn is:
A) n!
B) n n−2
C) 2 n−1
D) n n−1
34) Adding any edge to a tree results in:
A) A forest
B) Exactly one cycle
C) Disconnection
D) More components
35) Kruskal’s time is dominated by:
A) Sorting edges O(E log E)
B) DFS O(V + E)
C) BFS O(V + E)
D) Matrix operations
36) To find a maximum spanning tree, one can:
A) Run Prim/Kruskal on negated weights
B) It is not possible
C) Use Dijkstra
D) Use Bellman–Ford

4. Shortest Paths

37) Dijkstra’s algorithm requires edge weights to be:

A) Non-negative
B) Integer
C) Distinct
D) Bounded by 1
38) Bellman–Ford can detect:
A) Negative cycles reachable from the source
B) Only positive cycles
C) Only zero-weight cycles
D) Only self-loops
39) BFS computes shortest paths (in edges) when the graph is:
 Algorithms MCQs 7

A) Weighted with non-negative weights

B) Unweighted
C) Directed only
D) Undirected only
40) A standard all-pairs shortest paths method for dense graphs is:
A) Bellman–Ford repeated V times
B) Floyd–Warshall O(V 3 )
C) Dijkstra with arrays
D) Johnson’s O(V E log V )
41) For a DAG single-source shortest path, use:
A) BFS
B) Topological order DP in O(V + E)
C) Prim
D) Kruskal
42) If a negative cycle is reachable from the source, the shortest-path distance is:
A) Well-defined and finite
B) −∞ (undefined)
C) +∞
D) Always zero
43) With an adjacency matrix and no heap, Dijkstra runs in:
A) O(V 2 )
B) O(V log V + E)
C) O(E log V )
D) O(V E)
44) Johnson’s algorithm reweights edges using potentials computed by:
A) Dijkstra
B) Prim
C) Bellman–Ford
D) Kruskal
45) A* finds optimal paths if the heuristic is:
A) Arbitrary
B) Admissible (and consistent for graph search)
C) Always overestimating
D) Negative
 Algorithms MCQs 8

46) To reconstruct a shortest path after Dijkstra, maintain a:

A) Distance array only
B) Predecessor array
C) Visited set only
D) Degree array
47) With nonnegative weights, Dijkstra using a binary heap runs in:
A) O(V 2 )
B) O(E log V )
C) O(V log V )
D) O(E + V )
48) For graphs with negative weights but no negative cycles, use:
A) Dijkstra
B) Bellman–Ford
C) Prim
D) Kruskal

5. Hashing

49) The load factor α of a hash table is:

A) m/n
B) n/m
C) (n + m)/n
D) n2
50) Under simple uniform hashing with chaining, expected successful search time is:
A) Θ(1 + α)
B) Θ(log n)
C) Θ(α2 )
D) Θ(n)
51) Linear probing primarily suffers from:
A) Secondary clustering
B) Primary clustering
C) No clustering
D) Chain overflow
52) Quadratic probing primarily reduces which effect compared to linear probing?
A) Primary clustering
B) Secondary clustering
 Algorithms MCQs 9

C) Neither
D) Both fully
53) In open addressing, deletion is handled by:
A) Removing and leaving empty
B) Marking tombstones
C) Immediate full rehash
D) Ignoring the slot
54) Universal hashing helps ensure:
A) Worst-case O(1) for all inputs
B) Low expected collisions independent of input distribution
C) Cryptographic security
D) No resizing needed
55) Perfect hashing is most suitable for:
A) Dynamic sets with frequent updates
B) Static sets with fixed keys
C) Cryptographic storage
D) Streaming data
56) Bloom filters may yield:
A) False negatives only
B) False positives only
C) Both equally
D) Neither
57) Rehashing when α exceeds a threshold is to:
A) Reduce memory
B) Decrease collision probability
C) Increase collision probability
D) Disable deletions
58) For chaining, expected unsuccessful search time is:
A) Θ(1)
B) Θ(1 + α)
C) Θ(log n)
D) Θ(α2 )
59) In double hashing, the step size should be:
A) Always 1
 Algorithms MCQs 10

B) Based on a second hash, relatively prime to table size

C) Zero on collisions
D) Random only
60) Cryptographic hash functions are typically:
A) Required for hash tables
B) Overkill; non-crypto hashes preferred for performance
C) Mandatory in open addressing
D) The same as universal hashing

6. Sorting

61) The comparison-based sorting lower bound is:

A) Ω(n)
B) Ω(n log n)
C) Ω(log n)
D) Ω(n2 )
62) Merge sort worst-case time is:
A) O(n log n)
B) O(n2 )
C) O(n)
D) O(log n)
63) Quick sort worst case (naive pivot) is:
A) O(n log n)
B) O(n2 )
C) O(n)
D) O(log n)
64) Heap sort is:
A) Stable and in-place
B) Unstable and in-place
C) Stable and not in-place
D) Unstable and not in-place
65) Counting sort runs in:
A) O(n log n)
B) O(n + k) where k is key range
C) O(k log k)
D) O(n2 )
 Algorithms MCQs 11

66) Radix sort achieves linear time under assumptions by using:

A) Comparison sort per digit
B) Stable counting sort per digit
C) Heapify per digit
D) Quick sort per digit
67) Which is stable by default?
A) Quick sort
B) Merge sort
C) Heap sort
D) Selection sort
68) External sorting for huge datasets commonly uses:
A) Insertion sort
B) Two-phase multiway merge
C) Bubble sort
D) Counting sort
69) Median-of-three in quicksort aims to:
A) Guarantee O(n log n)
B) Reduce likelihood of worst-case partitions
C) Increase swaps
D) Make quicksort stable
70) Classic merge sort:
A) Is in-place stable
B) Uses O(n) extra space and is stable
C) Is unstable
D) Requires heaps
71) Best-case insertion sort comparisons are:
A) Θ(n log n)
B) Θ(n)
C) Θ(1)
D) Θ(n2 )
72) Bucket sort works well when:
A) Data uniformly random in [0, 1)
B) Data adversarially ordered
C) Data have huge discrete range with duplicates
 Algorithms MCQs 12

D) Data are strings only

7. Searching

73) Binary search requires:

A) Sorted array
B) Hash table
C) Linked list
D) Heap
74) Interpolation search expected time on uniform sorted data is:
A) O(n)
B) O(log log n)
C) O(log n)
D) O(1)
75) In a balanced BST (e.g., AVL), worst-case search time is:
A) O(1)
B) O(log n)
C) O(n)
D) O(log log n)
76) Trie search for a key of length L takes:
A) O(log n)
B) O(L)
C) O(1)
D) O(n)
77) Skip list expected search time is:
A) O(1)
B) O(log n)
C) O(n)
D) O(log log n)
78) Exponential search is useful when:
A) Array size is unknown or unbounded
B) Data are unsorted
C) Data are hashed
D) Using a linked list
79) Ternary search on arrays for an exact key is:
A) Asymptotically faster than binary search
 Algorithms MCQs 13

B) The same order as binary search

C) Slower by a polynomial factor
D) Not applicable
80) In an unbalanced BST with sorted inserts, worst-case search is:
A) O(log n)
B) O(n)
C) O(1)
D) O(log log n)
81) Range query [a, b] in a balanced BST costs:
A) O(log n)
B) O(log n + k) where k is output size
C) O(k) always
D) O(n)
82) Hash table search average case is:
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
83) Searching a linked list is:
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)
84) A BST guarantees O(log n) search if:
A) Insert order is random or self-balancing is maintained
B) Keys are strings
C) It has many duplicates
D) It is a heap

8. Design Techniques (Greedy, DP, Divide-and-Conquer)

85) Greedy algorithms are optimal when the problem exhibits:

A) Overlapping subproblems
B) Greedy-choice property (often matroid-like structure)
C) Arbitrary constraints
D) No optimal substructure
 Algorithms MCQs 14

86) Dynamic programming is appropriate when problems have:

A) No overlapping subproblems
B) Overlapping subproblems and optimal substructure
C) No substructure
D) Only divide-and-conquer
87) Divide-and-conquer generally:
A) Is purely iterative
B) Recursively divides, solves, and combines
C) Caches subresults across subproblems
D) Avoids recursion entirely
88) An example where greedy works optimally is:
A) 0/1 Knapsack
B) Fractional Knapsack
C) Coin change for arbitrary coin systems
D) Matrix-chain multiplication
89) Longest Increasing Subsequence can be solved in O(n log n) using:
A) Naive DP only
B) Patience sorting with binary search
C) Floyd–Warshall
D) Greedy on edge weights
90) Bellman–Ford is based on which paradigm?
A) Greedy
B) Dynamic programming (relaxation)
C) Divide-and-conquer
D) Backtracking
91) Merge sort exemplifies:
A) Greedy
B) Divide-and-conquer
C) Dynamic programming
D) Backtracking
92) Huffman coding is:
A) Greedy
B) Dynamic programming
C) Divide-and-conquer
 Algorithms MCQs 15

D) Randomized
93) The Master Theorem applies to recurrences of the form:
A) T (n) = aT (n/b) + f (n)
B) T (n) = T (n − 1) + 1
C) T (n) = T (n) + 1
D) S(n) = S(n2 )
94) When greedy fails for coin change, DP can:
A) Not help
B) Provide optimal change via bottom-up or memoization
C) Increase time exponentially
D) Require sorting only
95) Classic 0/1 knapsack DP time complexity is:
A) O(n log W )
B) O(nW )
C) O(W 2 )
D) O(n2 )
96) A sufficient condition to apply greedy for MST is:
A) Negative weights only
B) Cut and cycle properties hold; Kruskal/Prim are greedy and optimal
C) Graph must be directed
D) Graph must be complete
Algorithms MCQs 16

Answer Key

Q Ans Q Ans Q Ans Q Ans Q Ans

1 B 2 B 3 B 4 C 5 C
6 B 7 A 8 C 9 C 10 C
11 B 12 C 13 C 14 C 15 B
16 B 17 B 18 B 19 B 20 B
21 A 22 B 23 A 24 C 25 A
26 B 27 A 28 B 29 A 30 B
31 B 32 B 33 B 34 B 35 A
36 A 37 A 38 A 39 B 40 B
41 B 42 B 43 A 44 C 45 B
46 B 47 B 48 B 49 B 50 A
51 B 52 A 53 B 54 B 55 B
56 B 57 B 58 B 59 B 60 B
61 B 62 A 63 B 64 B 65 B
66 B 67 B 68 B 69 B 70 A
71 B 72 A 73 A 74 B 75 B
76 B 77 B 78 A 79 B 80 B
81 B 82 A 83 C 84 A 85 B
86 B 87 B 88 B 89 B 90 B
91 B 92 A 93 A 94 B 95 B
96 B
 Algorithms MCQs 17

Explanations

1) BFS explores vertices in increasing distance (edge count) from the source, thus yielding
shortest paths in unweighted graphs.
2) BFS maintains a FIFO queue to visit neighbors level by level, ensuring breadth-first
order.
3) In a BST, inorder traversal visits keys in sorted (nondecreasing) order by construction.
4) In DFS on a directed graph, a back edge to a gray (discovered but not finished) vertex
indicates a cycle.
5) With adjacency lists, both BFS and DFS run in O(V + E) time by visiting each vertex
and edge at most a constant number of times.
6) Level-order traversal visits nodes by depth from the root, which is exactly BFS on a tree.
7) Kahn’s algorithm repeatedly removes indegree-0 vertices, producing a valid topological
order if the graph is a DAG.
8) DFS colors vertices white (unvisited), gray (in progress), then black (finished) to track
traversal state.
9) With an adjacency matrix, scanning all possible neighbors costs O(V ) per vertex, giving
O(V 2 ) overall for BFS.
10) Postorder processes children before the parent, so it ensures a safe bottom-up deletion
of a tree.
11) Repeated BFS/DFS across unvisited vertices enumerates all components in total O(V +
E) time.
12) In a DAG, ordering vertices by decreasing DFS finish times yields a topological ordering.
13) In an undirected forest, edges satisfy E = V − C, where C is the number of connected
components.
14) Kosaraju’s (or Tarjan’s) algorithm computes strongly connected components (SCCs) in
directed graphs.
15) Tarjan’s SCC algorithm runs in linear time O(V + E) via a single DFS and low-link
values.
16) DFS low-link values identify articulation points and bridges in undirected graphs by
tracking earliest reachable ancestors.
17) Union–Find (Disjoint Set Union) with path compression and union by rank gives near-
constant time O(α(n)) per operation.
18) Adding one edge between two distinct components merges them, reducing the component
count by one.
19) An undirected graph is bipartite iff it is 2-colorable, which can be checked via BFS
coloring.
20) The SCC condensation graph is always a DAG because each SCC is contracted to a single
node and cycles would contradict maximality.
21) A connected undirected graph with E = V − 1 must be a tree (connected and acyclic).
22) Union–Find supports efficient same-component queries in near-constant time.
 Algorithms MCQs 18

23) On an adjacency matrix, each traversal step scans all vertices, leading to O(V 2 ) to visit
a component.
24) Two vertices are in the same SCC iff each can reach the other (paths u → v and v → u).
25) A minimum spanning tree (MST) is a spanning tree with the minimum total edge weight
among all spanning trees.
26) Kruskal’s algorithm uses Union–Find to detect cycles when adding edges in increasing
weight order.
27) With a binary heap (priority queue), Prim’s algorithm runs in O(E log V ) time.
28) With a Fibonacci heap, Prim’s runtime improves to O(E + V log V ) due to cheaper
decrease-key operations.
29) If all edge weights are distinct, the MST is unique by cut and cycle properties.
30) The cut property: for any cut, the minimum-weight crossing edge belongs to every MST.
31) The cycle property: in any cycle, the maximum-weight edge does not belong to at least
one MST (can be excluded).
32) Any spanning tree on V vertices has exactly V − 1 edges, reflecting connectivity without
cycles.
33) Cayley’s formula states that the complete graph Kn has n n−2 distinct spanning trees.
34) Adding any edge to a tree creates exactly one cycle because trees are minimally connected.
35) Kruskal’s complexity is dominated by sorting E edges, costing O(E log E).
36) A maximum spanning tree can be found by negating weights (or reversing comparisons)
and running Kruskal/Prim.
37) Dijkstra’s algorithm requires nonnegative edge weights to ensure greedy choices remain
optimal.
38) Bellman–Ford can detect reachable negative cycles by an extra relaxation that still re-
duces some distance.
39) BFS yields shortest paths by edge count in unweighted graphs (all edges weight 1).
40) Floyd–Warshall computes all-pairs shortest paths in O(V 3 ), efficient on dense graphs.
41) In DAGs, shortest paths are computed in O(V + E) by relaxing edges in topological
order.
42) If a negative cycle is reachable from the source, shortest-path distances are unbounded
below (−∞), hence undefined.
43) Using an adjacency matrix and no heap, Dijkstra runs in O(V 2 ) by repeatedly selecting
the nearest unvisited vertex.
44) Johnson’s algorithm uses Bellman–Ford to compute vertex potentials for reweighting,
enabling nonnegative edges for Dijkstra.
45) A* is optimal if the heuristic is admissible (never overestimates) and, for graph search,
consistent (monotone).
46) A predecessor (parent) array recorded during relaxations reconstructs the shortest path
on completion.
 Algorithms MCQs 19

47) With nonnegative weights, Dijkstra plus a binary heap runs in O(E log V ).
48) Bellman–Ford handles graphs with negative edges (but no negative cycles) in O(V E).
n
49) The hash table load factor is α = m, where n is keys and m is buckets.
50) With chaining and simple uniform hashing, the expected successful search takes Θ(1+α).
51) Linear probing suffers from primary clustering: long runs grow and attract more inser-
tions.
52) Quadratic probing reduces primary clustering versus linear probing, though secondary
clustering may persist.
53) In open addressing, deletions use tombstones to preserve probe sequences for future
searches.
54) Universal hashing chooses a hash function at random from a family to bound expected
collisions regardless of input.
55) Perfect hashing is ideal for static key sets, enabling O(1) worst-case lookups.
56) Bloom filters can yield false positives but never false negatives for membership queries.
57) Rehashing when α grows too large reduces collision probability and restores expected
O(1) operations.
58) For chaining, expected unsuccessful search also costs Θ(1 + α).
59) Double hashing uses a second hash for the step size, typically chosen to be relatively
prime to the table size to probe all slots.
60) Cryptographic hashes are generally too slow for hash tables; fast non-crypto hashes (e.g.,
Murmur, xxHash) are preferred unless security is required.
61) Any comparison-based sort has a lower bound of Ω(n log n) comparisons in the worst
case.
62) Merge sort runs in O(n log n) time for all cases due to its balanced divide-and-conquer
structure.
63) Quicksort’s naive pivot can degenerate to O(n2 ) on adversarial or sorted inputs without
precautions.
64) Heapsort is in-place and generally unstable because equal keys may be reordered by heap
operations.
65) Counting sort runs in O(n + k) time when the key range k is not too large relative to n.
66) Radix sort achieves linear time by applying a stable counting sort per digit from least to
most significant.
67) Merge sort is stable by default, preserving the relative order of equal keys.
68) External sorting typically uses multiway merges (e.g., two-phase multiway merge) to
minimize I/O.
69) Median-of-three pivot selection reduces the chance of worst-case partitions but does not
guarantee O(n log n).
70) Classic merge sort uses O(n) extra space and is stable; it is not in-place in the strict
sense.
 Algorithms MCQs 20

71) In the best case (already sorted), insertion sort performs Θ(n) comparisons.
72) Bucket sort excels when inputs are drawn uniformly from [0, 1), yielding linear expected
time after bucketing.
73) Binary search requires a sorted array to achieve O(log n) time.
74) On uniformly distributed sorted data, interpolation search runs in expected O(log log n)
time.
75) Balanced BSTs (e.g., AVL/Red–Black) guarantee O(log n) worst-case search via height
balancing.
76) Trie (prefix tree) search for a key of length L runs in O(L) time, independent of the
number of keys.
77) Skip lists achieve expected O(log n) search by randomized level promotion.
78) Exponential search is efficient when the array size is unknown: find a range by doubling,
then binary search.
79) Ternary search on discrete arrays is not asymptotically faster than binary search; both
are Θ(log n).
80) An unbalanced BST under sorted insertions becomes a degenerate chain with O(n) worst-
case search.
81) Reporting a range [a, b] in a balanced BST costs O(log n + k), where k is the number of
reported keys.
82) Average-case hash table lookup is O(1) with appropriate load factor and hashing.
83) Searching a singly linked list is O(n) because random access is unavailable.
84) A BST has O(log n) search if insertion orders are random on average, or if it is self-
balancing.
85) Greedy is optimal when the greedy-choice property holds (often tied to matroid structure)
and optimal substructure exists.
86) Dynamic programming applies when problems have overlapping subproblems and optimal
substructure to reuse solutions.
87) Divide-and-conquer solves a problem by recursively dividing into subproblems, solving,
and combining results.
88) Fractional knapsack admits an optimal greedy solution by taking items in decreasing
value density.
89) The O(n log n) LIS algorithm uses patience sorting with binary search to maintain min-
imal tails.
90) Bellman–Ford uses DP-style relaxation over edges across iterations to propagate shortest-
path estimates.
91) Merge sort is a canonical divide-and-conquer algorithm with a balanced split and linear-
time merge.
92) Huffman coding is greedy: it repeatedly merges the two least frequent symbols to build
an optimal prefix code.
 Algorithms MCQs 21

93) The Master Theorem analyzes recurrences of the form T (n) = aT (n/b) + f (n) to derive
asymptotic bounds.
94) When greedy coin change fails (noncanonical systems), DP (bottom-up or memoized)
finds optimal solutions.
95) Classic 0/1 knapsack DP runs in O(nW ), where W is capacity, via a table over items
and weight.
96) MST algorithms (Kruskal/Prim) are greedy and correct due to the cut and cycle prop-
erties.