Minimum Spanning Trees and Dynamic Programming

This session covers two pieces. First, the minimum spanning tree problem and the two greedy algorithms that solve it — Prim's algorithm and Kruskal's algorithm. Both solve the same problem, but each applies the greedy idea in its own way. Second, the third and last design strategy of the course: dynamic programming. The technique is built up with two main examples — Fibonacci numbers and the 0/1 knapsack problem — and closes with the idea of pseudo-polynomial time, which sets up the next session's discussion of NP problems.

11.1 Graphs — Recap

11.1.1 Where We Left Off — Dijkstra's Algorithm

Where did the course stop last time? Under graphs, we were discussing Dijkstra's algorithm. Let's place it before moving on, because today's two minimum spanning tree algorithms are its direct descendants.

Dijkstra's algorithm solves the single source shortest path problem: its objective is to find the shortest path from a single source vertex to all the other vertices of a weighted graph. It falls under the greedy method, the design strategy that was being discussed — a strategy that works on optimization problems by making the best local choice at every step.

Both the greedy method and Dijkstra's algorithm are the direct background for today's minimum spanning tree algorithms. Prim's algorithm and Kruskal's algorithm both apply the greedy idea, but in two different ways — Prim's grows one tree exactly like Dijkstra's grows a shortest-path tree, while Kruskal's works globally on edges. Knowing Dijkstra's algorithm well makes today's material much easier: the pseudocode, the heap-based analysis, and even the "initialize single source" step all carry over.

11.1.2 What a Graph Is

A graph is a way of modeling connections between things. Formally, a graph is an ordered pair

$$G=(V,E)$$

where $V$ is a set of vertices (also called nodes) and $E$ is a collection of pairs of vertices called edges. The rough everyday definition — "a collection of vertices and edges" — is fine for casual talk, but the conceptual meaning of the ordered-pair definition is what matters. Definitions do not need to be memorized word for word, but the conceptual understanding is very important.

The word "ordered pair" carries a real idea: a graph is not just a pile of parts, it is a structured object whose two components play different roles. $V$ is a set — its elements are distinct and unordered. $E$ is a collection of pairs — each edge is defined by the two vertices it joins, and the edge connects those two vertices. For an edge $\{u,v\}\in E$, the vertices $u$ and $v$ are called its endpoints; two vertices joined by an edge are adjacent; and an edge whose two endpoints are the same vertex is a loop. The number of edges leaving a vertex is its degree. Today's graphs are undirected (an edge is a two-way connection) and weighted (each edge carries a number called its weight).

11.2 Spanning Subgraphs and Spanning Trees

11.2.1 Spanning Subgraph

A spanning subgraph of a graph $G$ is a subgraph of $G$ that contains all the vertices of $G$. What it will not contain, in general, are all the edges of the original graph — a spanning subgraph is a subgraph, not the graph itself.

The name says it: the word "spanning" means it spans (covers) all the vertices, but only some of the edges. Every vertex of $G$ appears, while edges may be dropped. The concept matters because a graph can have many different spanning subgraphs: keep all the vertices, keep different choices of edges, and you get different spanning subgraphs of the same graph.

11.2.2 Spanning Tree

A spanning tree of a graph $G$ is a spanning subgraph that is itself a tree. Here "tree" is used in its precise graph sense: the structure is connected — you can walk from any vertex to any other vertex along edges — and it has no cycles (no loops). Equivalently, there is exactly one path between any two vertices.

Putting the two ideas together, a spanning tree of $G$:

• has all the vertices of $G$ (it spans),
• does not have all the edges of $G$ (only some of them),
• is connected,
• contains no cycles.

A useful counting consequence: any tree on $n$ vertices has exactly $n-1$ edges. So a spanning tree of a graph with $n$ vertices always picks exactly $n-1$ of the graph's edges — enough to connect everything, never more, because an extra edge would close a cycle.

One note on the wording of the original discussion: it was said that the spanning tree "will not be connected." That phrasing is misleading — a tree is by definition connected and acyclic. What the discussion meant is that the tree will not contain every connection of the original graph: some edges are left out, yet the chosen edges still keep the whole structure connected. Connectedness is exactly what makes it a tree rather than a forest.

11.3 Minimum Spanning Trees

11.3.1 Definition and Intuition

The minimum spanning tree (MST) is defined for weighted graphs: every edge carries a number called its weight — a cost, a distance, a price. The total weight of a spanning tree is the sum of its edge weights:

$$W(T)=\sum _{e\in T}w(e)$$

where $T$ is the spanning tree, $e$ ranges over the edges of $T$, and $w(e)$ is the weight of edge $e$. A minimum spanning tree is a spanning tree of a weighted graph with the minimum total edge weight — the minimum-cost spanning tree. The idea in one line: after constructing a spanning tree, if that spanning tree carries the minimum total edge weight, we call it a minimum spanning tree.

11.3.2 Uniqueness of the MST

A graph can have more than one minimum spanning tree. The exception: if all the edge weights are unique — pairwise distinct — then there is only a single minimum spanning tree.

The phrase "pairwise distinct" is the whole catch: every pair of edges in the whole graph must carry different weights. If two edges somewhere in the graph share a weight, the MST can cease to be unique. Two different trees may then achieve the same minimum total weight, and each one is a perfectly valid minimum spanning tree.

11.3.3 Worked Example — Three Spanning Trees of One Graph

Consider a small graph on vertices A, B, C, D, E, with edge weights marked on the edges. The lecture drew three different spanning trees for this same graph and gave their totals. Only the totals were stated in the discussion; the weight assignment below is a consistent one that reproduces exactly those totals, so every step can be checked.

The graph has six edges with these weights:

11.3.4 Worked Example — Two MSTs of Equal Weight

When weights repeat, the MST may be non-unique. The lecture drew two minimum spanning trees, call them MST1 and MST2, for the same weighted graph.

11.3.5 Student Questions and Answers

11.4 Prim's Algorithm

11.4.1 The Greedy Idea

Two algorithms construct a minimum spanning tree from a given graph: Prim's algorithm and Kruskal's algorithm. Both solve the same problem, and both use the greedy strategy, but they apply the greedy idea in two different ways — and both always yield the optimal solution. Greedy strategies apply to optimization problems; the change-making problem and the fractional knapsack problem were the earlier examples, and minimum spanning tree construction is another one.

Steps of Prim's algorithm (high level):

1. Start with the chosen source vertex; the tree contains only this vertex.
2. Look at every edge leaving any vertex already in the tree.
3. Pick the edge with the smallest weight that leads to a vertex not yet in the tree; add both the edge and the vertex to the tree.
4. Repeat steps 2–3 until all $N$ vertices are in the tree.

The algorithm body is the same as Dijkstra's with one difference that matters: Prim's never adds up costs. Each decision uses only the single edge weight at that moment.

11.4.2 Worked Example 1 — Nine-Vertex Graph

Consider the given graph (think of it as a complete routing network) with vertices A, B, C, D, E, F, G, H, I. Start from vertex A.

Two points deserve special attention. First, the cycle rule: even when an unchosen edge is cheap, if it connects two vertices that are already inside the tree, adding it would create a cycle, so it is skipped. At the later stages of this example the edge G–I (weight 6) was available but not picked for exactly that reason; instead C–D was picked. Second, the same logic covers a hypothetical A–H: if A–H were the shortest candidate at that stage (say its weight were 6), we would still not pick it, because we are building a minimum spanning tree, not a minimum spanning subgraph — a tree cannot contain a cycle, and A and H are already connected inside the tree.

11.4.3 Worked Example 2 — Six-Vertex Graph

A second graph on vertices A, B, C, D, E, F was solved live. Start from A.

11.4.4 Prim's Algorithm and Dijkstra's Algorithm

Prim's algorithm closely resembles Dijkstra's algorithm: we start from a source, relax the edges, and pick the next vertex based on the lowest weight — looking at candidate weights 3, 5, 6, we take the 3, then keep exploring from the minimum-distance vertex. The algorithm bodies are nearly identical; the single difference is that Dijkstra adds the accumulated cost as it proceeds, while Prim's does not. Prim's considers only the individual edge weight at one particular time — no accumulated path cost is involved. The rectangular-box procedure shared by both algorithms (the first few statements of the pseudocode) is called initialize single source.

11.4.5 Time Complexity

Since the procedure is the same as Dijkstra's, the time complexity analysis is the same as Dijkstra's:

$$O(E\log V)$$

where $E$ is the number of edges and $V$ is the number of vertices (stated in the session as $O(M\log N)$ with $M$ edges and $N$ vertices). The steps: first construct a heap, then repeatedly extract the minimum from the heap — each extract-min costs $O(\log V)$, and the heap operations over all vertices and edges give $O(E\log V)$. The detailed analysis was covered in the previous session and is not repeated here.

Real-world connection: Prim's algorithm is the classic engine for designing low-cost networks — connecting campuses with cable, linking telephone exchanges, or wiring the pins of a circuit board. In any setting where a designer must connect every point of a network at minimum total cost, the cheapest connected structure is exactly the MST that Prim's produces.

11.5 Kruskal's Algorithm

11.5.1 The Greedy Idea

Kruskal's algorithm does the same job — building a minimum spanning tree — but the greedy application is different. Nobody gives a starting point; there is no source vertex. Instead we start from the edge with the minimum weight in the whole graph, and then keep adding the next shortest edge, with one condition: the added edge must not create a cycle. The only concept: sort the edges in ascending order of weight, pick the lowest-weight edge, and keep adding edges to the MST, until all the vertices have been connected.

Steps of Kruskal's algorithm (high level):

1. Sort all edges of the graph in ascending order of weight.
2. Take the lowest-weight edge. If adding it does not create a cycle, add it to the MST; if it would create a cycle, skip it.
3. Repeat with the next-lowest edge until all vertices are connected (the MST has $N-1$ edges).

The key freedom: during the process, the selected edges need not be connected. They can form a forest — several separate trees growing independently — and only at the end must the result merge into a single tree. In Prim's algorithm the partial result is always a tree; in Kruskal's it can be a forest.

11.5.2 Worked Example 1 — Nine-Vertex Graph

The same nine-vertex graph (A, B, C, D, E, F, G, H, I) is solved with Kruskal's algorithm:

11.5.3 Worked Example 2 — Six-Vertex Graph

The same six-vertex graph (A, B, C, D, E, F) is solved again with Kruskal's:

Prim's and Kruskal's can create two different MSTs for the same graph — different structure, different edge sets — but the minimum total weight is the same, because both algorithms always return the optimal solution.

11.5.4 Time Complexity

The analysis again uses a heap. There are $M$ edges, so the heap construction time is $O(M)$, and each extract-min takes $O(\log M)$; extracting every edge once gives

$$O(M\log M)=O(E\log E)$$

which is the same complexity as

$$O(E\log V)$$

since $\log E$ and $\log V$ differ by at most a constant factor on connected graphs ($E<V^2$, so $\log E=O(\log V)$). The concept difference from Prim's is only that Kruskal works on edges instead of vertices; the analysis pattern is identical to Dijkstra's, so the details from the previous session carry over.

11.5.5 Student Questions and Answers

Real-world connection: Kruskal's is the natural algorithm when edges come pre-priced as a list — leasing telephone lines between city pairs, or selecting transmission links from a tariff sheet. Because it works from the sorted edge list, it also pairs well with database-style sorting and union-find bookkeeping at scale.

11.6 Prim's vs Kruskal's — When to Use Which

11.6.1 Sparse and Dense Graphs

The choice between the two algorithms depends on the graph. Kruskal's algorithm is the right choice when the graph is sparse — when it has few edges — because all of Kruskal's operations are based on edges. Prim's algorithm is the right choice when the graph is very dense — when it has many edges — because Prim's is vertex based. In short: Kruskal's is edge based, Prim's is vertex based.

11.6.2 Side-by-Side Comparison

The rules to remember: Kruskal's selects the shortest edge, then the next shortest edge that does not create a cycle, and repeats until all the vertices have been connected; it begins with a forest and merges into a tree. Prim's selects any vertex, then repeatedly selects the shortest edge connected to that vertex — connected to any vertex already in the tree — and stays a tree the whole time. The common student mistake in Prim's is thinking only about the outgoing edges of the last vertex visited; when a new vertex is added, the old vertices must also be reconsidered for outgoing edges.

11.7 Applications of Minimum Spanning Trees

11.7.1 Communication and Transportation Networks

Real-world: a phone company leases lines to connect cities; the company charges different amounts of money to connect different pairs of cities. We want a set of lines that connects all our offices (all the cities) with minimum total cost — that is exactly an MST. The same idea covers laying communication cables to connect every building within a campus, or connecting telephone networks. In transportation planning, from a common hub city, what is the minimum-distance way to reach several destination cities (for example from Bangalore to Hyderabad, to Chennai, to other places)? An MST gives the cheapest connected structure.

11.7.2 Cluster Analysis

Real-world: the K-means algorithm (the K-clustering problem) can be viewed through MSTs. Clustering groups similar points: we want minimum intra-cluster distance (points inside one cluster should be close) and maximum inter-cluster distance (different clusters should be far apart). One way to do this: find the MST of the points, then delete the $K-1$ most expensive edges. Each deletion splits one cluster into two, and after $K-1$ deletions we have $K$ clusters. If we can define a distance limit, every edge within that limit forms a cluster. Students who already know clustering from machine learning or data mining will appreciate this angle; it requires thinking a little out of the box.

11.7.3 Image Registration and Segmentation

Real-world: image segmentation is the process of partitioning an image into different components, with the purpose of decomposing the image into significant regions. To extract a specific object — say, to find the cat in a picture — we first define properties of the cat, then decompose the image into only the relevant parts, separating significant areas from non-significant areas. We can think of this as connecting dots between the significant areas: all the homogeneous areas get connected inside our spanning tree, and everything else falls outside the tree, so the disconnected parts are segmented out. Image registration uses the same idea: aligning two images of the same scene by matching their significant structures through a spanning tree. This short explanation is only a hint; a full appreciation requires reading about the technique in detail.

11.7.4 Taxonomy and Feature Extraction

Real-world: taxonomy — the science of classification — fits the same picture: related parts get connected, disconnected parts are unrelated, so a taxonomy of organisms or documents can be laid out as a tree of relations. Real-world: feature extraction (the features used in data mining and machine learning) can be seen from the same angle: a minimum spanning tree over feature vectors connects the most similar features and leaves dissimilar ones apart, which supports dimensionality reduction and feature selection. These connections only make full sense to students who already know clustering and feature extraction; they are listed as applications of the MST and can be read in detail when there is time and interest.

11.8 Exam-Style Problem — Which Algorithm Produced This Partial Spanning Tree?

11.8.1 The Question

A practice document contains an exam question from another institution that is very relevant — a different version of the same question appeared in our own exam, because it proves in depth whether both algorithms are understood. The question: each figure below represents a partial spanning tree. Determine whether it could possibly come from a prematurely stopped Prim's algorithm or a prematurely stopped Kruskal's algorithm, both, or neither. There are six or seven graphs, and the answer key is given at the end of the document.

The whole catch is the phrase "prematurely stopped": the algorithm was stopped in the middle of its run, so what you see is an intermediate stage — not the finished MST.

11.8.2 Worked Analysis — Graph 1 (Kruskal's)

11.8.3 Worked Analysis — Graph 2 (Prim's only)

11.8.4 Student Questions and Answers

11.8.5 Practice Guidance

Some of the remaining figures have "both" and "neither" as the correct answers, which is the real catch. When the selected edges could plausibly come from either algorithm at some stage, the answer is "both"; when the edge set could not arise from either algorithm at any stage, the answer is "neither". Notice that a connected partial tree is not automatically Prim's — Kruskal's can be connected at an intermediate stage too — and a disconnected one is not automatically Kruskal's answer territory for "neither", because both algorithms must actually be traceable to that exact stage.

11.9 Dynamic Programming — Foundations

11.9.1 The Name and the History

Dynamic programming is the third (and last) design strategy of the course. It was invented by the mathematician Richard Bellman. The word "programming" in the name of the technique stands for planning — it does not refer to computer programming. Dynamic programming is dynamic planning; the name is a misnomer and should not be confused with writing programs.

11.9.2 Overlapping Subproblems

Dynamic programming is a technique for solving problems with overlapping subproblems — overlapping subproblems, very, very important. A typical problem's solution can be related to the solutions of its smaller subproblems. The difference from divide and conquer: in divide and conquer, we divide a problem of size $n$ into subproblems of size $n/2$, solve the subproblems individually, then combine their solutions into the solution of the original problem. In dynamic programming, the subproblems are not independent — they overlap. So rather than solving the same subproblem again and again, dynamic programming solves each smaller subproblem only once and records the result.

Why is that possible? Because the subproblems overlap: when the same subproblem shows up again during the solution of the main problem, we do not re-solve it — we use the stored solution.

11.9.3 Dynamic Programming vs Divide and Conquer

The contrast with divide and conquer: there, subproblems are solved independently and their solutions combined. Here, since subproblems overlap, the first encounter solves the subproblem and stores the result; the second encounter reuses the stored solution. That single difference — solving each subproblem once and storing it — is the entire idea of dynamic programming.

11.9.4 The Space-Time Trade-off

The moment we say "store the result," there is a space-time trade-off. We save time by not re-solving overlapping subproblems, but storing results costs extra space. These days space is much less of a concern; if we can take advantage of time, the space cost is acceptable. A straightforward application of dynamic programming can be interpreted as a special variety of the space-for-time trade-off — it is an optimization of plain recursion.

11.10 Fibonacci — The First Dynamic Programming Example

11.10.1 The Plain Recursive Version

The simplest example is the Fibonacci numbers. The plain recursive algorithm, written as a recurrence: for $F(n)$, if $n\le 1$, return $n$; otherwise return $F(n-1)+F(n-2)$:

$$F(n)=\{\begin{array}{ll}n& n\le 1\\ F(n-1)+F(n-2)& n>1\end{array}$$

A problem of size $n$ is divided into two subproblems of sizes $n-1$ and $n-2$ — note it is not divided into $n/2$ or $n/3$; the split is by subtraction, not halving. That detail matters: the two subproblems overlap, because $F(n-1)$ itself contains an $F(n-2)$ call.

11.10.2 Overlapping Subproblems in the Recursion Tree

Take $F(5)$, a very small number. The recursion expands as $F(4)+F(3)$; then $F(4)$ expands as $F(3)+F(2)$, and $F(3)$ expands as $F(2)+F(1)$. Already the subproblems repeat: $F(3)$ appears twice, $F(2)$ appears twice, $F(1)$ appears twice. For such a small input, overlapping subproblems are already all over the tree. The recursion stops when $n\le 1$, so $F(1)$ and $F(0)$ do not need recursion. The problem definitely has overlapping subproblems.

11.10.3 Time Complexity of Plain Recursion

The plain recursion solves the same subproblems over and over. A problem of size $n$ splits into size $n-1$ plus size $n-2$; each of those splits further — note that $F(2)$ itself splits into $F(1)$ and $F(0)$ — so the recursion tree is exponential:

$$T(n)=T(n-1)+T(n-2)+O(1)=O(2^n)$$

which we cannot afford. Every level of the tree doubles the number of calls (roughly), so the number of leaf calls grows like $2^n$ — the same function that measures how fast bacteria colonies double.

11.10.4 The Iterative Dynamic Programming Version

The dynamic programming version is the simple iterative Fibonacci that most students have written many times without knowing it is dynamic programming: store $F(i)=F(i-1)+F(i-2)$ in an array that fills from left to right, in increasing order. When $F(i-2)$ is needed again, it is already stored — no recomputation. The time complexity is $O(n)$: linear, down from exponential. Storing the results in a simple array turns $O(2^n)$ into $O(n)$. This is the basic concept of dynamic programming — that is all it is.

11.10.5 Optimal Substructure

The term optimal substructure: a problem can be solved by using the solutions of its subproblems — it has optimal substructure. This term was already studied during the greedy method. In Fibonacci's case, the value $F(n)$ is defined directly in terms of $F(n-1)$ and $F(n-2)$ — the solution of the subproblem is literally part of the original solution. Where the greedy method used optimal substructure to justify the greedy choice, dynamic programming uses it to justify building up from small subproblems.

11.10.6 Student Questions and Answers

11.10.7 Worked Word Problem — Rabbits and the Fibonacci Series

The example used: a man puts a pair of rabbits in a place surrounded by a wall. How many pairs of rabbits will there be in a year, if the initial pair of rabbits are newborn, and all rabbit pairs are not fertile during their first month? (A disclaimer came with the story: the scenario is not realistic — it is a cooked-up question, not one that appeared in the exam, but it shows how Fibonacci gets framed.)

The full solution was written out; anyone who did not follow was asked to read the question again, since the scenario itself is simple.

11.11 The General Dynamic Programming Technique

11.11.1 When Dynamic Programming Applies

Dynamic programming applies to a problem that at first seems to require a lot of time — possibly exponential — provided we have simple subproblems. The requirements:

1. Simple subproblems. The subproblem can be defined in terms of a few variables.
2. Subproblem optimality. The global optimum value can be defined in terms of optimal subproblems. In simple terms: once you solve a subproblem, the solution of that subproblem should help you solve the original problem. It must not be the case that you solve a subproblem and that subproblem's solution is not even present in the solution of the original problem. That will happen in some cases — the knapsack problem shows it.
3. Subproblem overlap. The subproblems are not independent. In divide and conquer, subproblems are independent; in dynamic programming they overlap.
4. Build bottom-up. Solve the smallest subproblem first, then the next, then the next, going up.

11.11.2 Bottom-Up Construction

The construction order is bottom-up: solve the smallest subproblem first, then the next larger one, and so on, until the original problem is solved. Each step reuses the stored solutions of the smaller subproblems. The first algorithm studied under this technique is the 0/1 knapsack problem.

11.12 The 0/1 Knapsack Problem

11.12.1 Problem Statement

We are given a set of $n$ items, where each item $i$ has a weight $w_i$ and a profit $p_i$, and a knapsack of capacity $W$. We must choose items so that the total profit is maximized, subject to the total weight being at most the knapsack's capacity.

11.12.2 0/1 vs Fractional Knapsack

The fractional knapsack problem falls under the greedy method; the 0/1 knapsack problem falls under dynamic programming — the most effective way of solving each problem is with its respective design strategy. The difference: in 0/1 knapsack, each item must be entirely accepted or entirely rejected. Fractional knapsack allowed dividing an object into fractions; that flexibility does not exist here. If you take an object, you take it completely; if you do not, you leave it completely.

11.12.3 Mathematical Formulation

With $x_i\in \{0,1\}$ indicating whether item $i$ is taken, the problem is:

$$\text{maximize}\sum _{i=1}^n{p}_i{x}_i$$

$$\text{subject to}\sum _{i=1}^n{w}_i{x}_i\le W,x_i\in \{0,1\}$$

where $p_i$ is the profit of item $i$, $w_i$ is its weight, and $W$ is the knapsack capacity. The decision variable $x_i$ is always 0 or 1; the total weight must be less than or equal to the capacity. That is the difference between 0/1 and fractional knapsack.

11.12.4 Worked Example — Choosing Items by Hand

Five items are given, each with a weight and a profit. The knapsack can hold 9 kg. The chosen solution: item 5, at 2 kg, gives a profit of 80; item 3, taken completely, is 2 kg and gives a profit of 6; item 4, taken completely, is 4 kg and gives a profit of 20.

11.12.5 Brute Force — 2^n Combinations

For $n$ items, the brute force approach enumerates every possible combination: for each item, either select it or do not. With four items, that is $2^4=16$ combinations, ranging from 0000 (select none) to 1111 (select all) — not $4!$ (four factorial), because the order of selection does not matter and each item is independently in or out. In general there are $2^n$ possibilities.

Not all combinations may be applicable — the weight constraint eliminates some — but in the worst case (for example, if every item's weight is small enough to fit), brute force must consider all $2^n$, which is exponential.

11.12.6 Building the Dynamic Programming Table

The example: capacity $W=8$, and 4 objects with profits 1, 2, 5, 6 and weights 2, 3, 4, 5 respectively:

Build a table $B$ with rows for objects $0\dots n$ and columns for capacities $0\dots W$: since the capacity is 8, there are 9 columns (numbered 0 to 8); since there are 4 objects, there are 5 rows (numbered 0 to 4). We start from zero — that is why there is a plus one on both counts. Whatever the capacity of the knapsack, that plus one is the number of columns; however many objects there are, that plus one is the number of rows. This matters for the algorithm: these counts are the loop bounds.

Fill the first row and the first column with 0 without thinking. In the first column, the assumption is a knapsack of capacity 0 — whatever objects are available, nothing fits, so the maximum profit is 0. In the first row, the assumption is zero objects — however large the capacity, the maximum profit obtainable from no objects is 0.

11.12.7 The B(k, w) Recurrence

The table is not filled by thinking case by case; it is filled by a formula. Let $B(k,w)$ be the maximum profit obtainable from items $1\dots k$ with capacity $w$. The recurrence:

$$B(k,w)=\{\begin{array}{ll}B(k-1,w)& \text{if }{w}_k>w\\ \max (B(k-1,w),B(k-1,w-w_k)+p_k)& \text{otherwise}\end{array}$$

where $w_k$ is the weight of the object under consideration and $p_k$ is its profit.

Case 1: when $w_k>w$, the object under consideration does not even fit, so the maximum value of the knapsack with items $1\dots k$ at capacity $w$ is the same as the maximum value with items $1\dots k-1$ — the recurrence copies the value from the row above. For example, at $B(3,1)$: $w_3=4>1$, so copy $B(2,1)=0$; the same copy happens at $B(3,2)$ and $B(3,3)$.

Case 2: when $w_k\le w$, compare two options: the best value without the object, $B(k-1,w)$, and the best value with it — make room by subtracting the object's weight, look up $B(k-1,w-w_k)$, then add the object's profit $p_k$. Take whichever is larger. The worked cell was $B(3,4)$: here $w_3=4=w$, so compute $\max (B(2,4),B(2,0)+p_3)=\max (2,0+5)=5$.

11.12.8 The Logic Behind the Recurrence

Logical reading of case 1: adding the new object cannot increase the value of the knapsack, because the object will not even fit — the maximum profit does not change, so we copy the previous row's value down.

Logical reading of case 2: when the new item can fit, we check whether including it increases the profit. Suppose object 1 is already in the knapsack. When considering object 2, first check whether its weight exceeds the capacity — if it does, there is no question of including it. If it fits, we must create space for it: subtract its weight from the capacity, look up the best profit for that remaining capacity using only the earlier objects (that is the $k-1,w-w_k$ term — the state of the knapsack without the new object), then add the new object's profit. Between the knapsack without the new object and the knapsack with it, keep whichever gives more profit.

The worked numbers: when the capacity is 6, objects of weight 4 and 2 fit together (profit $5+1=6$); when the capacity is 7, objects 2 and 3 fit together (profit $2+5=7$); when the capacity is 8, the maximum is 8 (object 4 plus object 2: profit $6+2=8$).

11.12.9 Subproblem Optimality — Where Knapsack Breaks the Rule

That is exactly the reason for the subtraction $B(k-1,w-w_k)$: the recurrence looks up the best value for the remaining capacity — a different subproblem than the same-capacity one — which accommodates the dropped object.

11.12.10 Overlapping Subproblems in Knapsack

The knapsack problem does have overlapping subproblems. Consider 3 objects and capacity 2 (assume unit weight and unit profit for every object, for simplicity — other values work the same way). The decision for each object is include or exclude.

From the start — 3 objects, capacity 2 — the "exclude" branch keeps 2 objects at capacity 2, and the "include" branch has 2 objects at capacity 1. Each of those states branches again into include/exclude, and the same states reappear: a state with 1 object at capacity 1 appears in multiple places in the tree. With a small capacity of 2 this is already visible; with a capacity of 100, the tree fills with many repeated subproblems. Exploring every branch fully is exponential for sure — dynamic programming is what avoids the repeated work.

11.12.11 Time Complexity — O(nw) and Pseudo-Polynomial Time

The table method runs in time $O(nw)$: the outer loop runs over the objects (0 to n) and the inner loop over the capacities (0 to w) — we simply fill an $n\times w$ matrix. The algorithm is a line-by-line conversion of the table filling: if $w_i>w$, apply one formula; otherwise apply the other; fill the complete matrix. (Tracking which objects were selected needs a few extra lines of code; the concept is only the table filling.) Brute force took $2^n$ in the worst case; the DP version runs in $nw$.

This type of algorithm is called a pseudo-polynomial time algorithm. Until now, every algorithm's time complexity was expressed in terms of the input size — the number of inputs, $n$. Here another factor $w$ appears, and $w$ is a criterion within the problem statement, not the input size. The running time depends on the magnitude of a number given in the input, not its encoding size. (This connects to a note from the first session: the $n$ in the order of growth is not exactly the input size — it is the number of bits needed to encode the input.)

The next session continues the story: NP — non-deterministic polynomial time algorithms.

11.12.12 Reconstructing the Chosen Objects

The table gives the maximum profit, but which objects produce it? The trick — which may not be in the textbook — is tracing first appearances: the maximum profit sits in the last cell, the bottom-right corner, and profit values first appear in the row where the object that creates them is introduced.

General rule: whenever the last cell's value first appears in row $k$, object $k$ is included; subtract its profit from the remaining amount and repeat.

Exam Guidance Summary

• MST question type: partial spanning tree figures — decide Prim's / Kruskal's / both / neither for a prematurely stopped run. A different version of this question appeared in the actual exam; it proves depth of understanding. Always explain the reasoning — answers without explanation earn zero marks. The word "prematurely stopped" is easy to miss; read the question carefully. Practice all the graphs, including the "both" and "neither" cases.
• MST theory: a graph can have multiple MSTs; uniqueness holds only when all edge weights are pairwise distinct. Both Prim's and Kruskal's always give an optimal solution; the total weight is the same even when the tree structures differ.
• Prim's: starts from any vertex; always a tree; pick the shortest edge connected to any vertex already in the tree (not just the last vertex). Analysis: O(E log V), same as Dijkstra's.
• Kruskal's: starts from the minimum-weight edge; may be a forest during the process; pick the next shortest edge that does not create a cycle; ends as a tree. Analysis: O(E log E) = O(E log V).
• Choice: Kruskal's for sparse graphs (edge based), Prim's for dense graphs (vertex based).
• Dynamic programming: overlapping subproblems solved once each; space-time trade-off; optimal substructure; bottom-up construction.
• Fibonacci: plain recursion is O(2^n); iterative DP is O(n). Recognizing linear complexity from the code should be automatic.
• Word problems: the exam will not necessarily say "Fibonacci" — recognize the pattern behind the story. Rabbit problem: F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5, ..., F(12) = 144 pairs at the end of the year.
• 0/1 knapsack: maximize the sum of p_i x_i with x_i in {0, 1} and total weight at most W; DP table with W+1 columns and n+1 rows; the B(k, w) recurrence; O(nw) time, which is pseudo-polynomial because of the w factor; if w is as large as 2^n, the DP is slower than brute force. Reconstructing the chosen objects: find where each profit value first appears.
• Quiz: released this week (tonight), with five days to complete it; the portions cover everything up to today's session.
• Syllabus: the in-semester syllabus is the complete syllabus — the complete handout. The extra topics covered beyond the live sessions are also examinable; do not skip them.
• Mark split: the question paper is not set by a single person; a panel of faculty sets it, so the 25/75 split mentioned earlier is one possibility, not a hard rule.

Key Industry Applications

• Communication networks: laying cables to connect all buildings within a campus; connecting telephone exchanges; leasing phone lines between cities at minimum total cost (the phone company charges different amounts for different city pairs) — an MST minimizes total cost.
• Transportation networks: from a hub city (Bangalore), find the minimum-distance routes to several destinations (Hyderabad, Chennai, others) — an MST gives the cheapest connected structure.
• Cluster analysis / K-means (K-clustering): find the MST of the data points, then delete the K−1 most expensive edges to get K clusters with small intra-cluster distance and large inter-cluster distance.
• Image registration and segmentation: partition an image into significant regions; connect dots between homogeneous areas with a spanning tree so unrelated, disconnected parts fall outside it (for example, extracting a cat from a picture).
• Taxonomy: the science of classification — related parts connected, unrelated parts disconnected.
• Feature extraction in data mining and machine learning: the same MST view applies to features.
• Dijkstra's algorithm (previous session): single source shortest path, the greedy-method sibling of Prim's algorithm.
• Dynamic programming in practice: the same "solve each subproblem once and store it" pattern underlies shortest-path tables in navigation, sequence alignment in bioinformatics, and resource allocation in operations research.