Skip to content
CampusPrep
CS-402 · Analysis Design of Algorithm/Quick Revision Short Notes

Analysis Design of Algorithm (CS-402) - Unit 3 Short Notes

How unit 3 is examined

This unit covers the DP method and four classic DP problems; 0/1 knapsack, Floyd-Warshall and the multistage graph carry the marks, with the DP concept, its comparison with other methods, and reliability design after them.

Concept of dynamic programming

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>Dynamic programming solves a problem by breaking it into overlapping subproblems, solving each subproblem once, storing its answer in a table, and combining stored answers, and it is valid only when the principle of optimality holds.</mark>

Key points.

  1. The principle of optimality says that whatever the first decision, the remaining decisions must be optimal for the state that decision leaves.
  2. The problem must have optimal substructure and overlapping subproblems, so the same subproblem is reused instead of recomputed.
  3. The forward approach (bottom-up, tabulation) fills the table from the smallest subproblems upward with a loop and has no recursion overhead.
  4. The backward approach (top-down, memoization) starts from the target, recurses into subproblems and caches each result; it is more intuitive but pays recursion overhead.
  5. In graph problems, forward means the cost is measured from a node to the target, and backward means the cost is measured from the source to a node.
  6. DP gives an exact optimum, often in polynomial time where brute force is exponential.
Basis Divide and conquer Greedy Dynamic programming
Subproblems Independent One choice, one subproblem Overlapping, solved once and stored
Decision Combine after solving Locally best choice, never revised Tries all choices, keeps the best
Optimality Not the aim Not guaranteed unless greedy-choice property Always optimal (principle of optimality)
Approach Top-down recursion Top-down, one pass Bottom-up table or memoized recursion
Examples Merge sort, quick sort Huffman, Prim, fractional knapsack 0/1 knapsack, Floyd-Warshall, OBST

OBST (Jun 2024). Work in units of $1/20$: $p=(1,4,2,1)$, $q=(4,2,4,1,1)$ ($q(3)=1/20$ is not printed in the paper; the standard value is used). Use $w(i,j)=w(i,j-1)+p(j)+q(j)$ and $c(i,j)=w(i,j)+\min_{i<k\le j}[c(i,k-1)+c(k,j)]$, and $r(i,j)$ is the best $k$.

$(i,j)$ 01 12 23 34 02 13 24 03 14 04
$w$ 7 10 7 3 15 13 9 18 15 20
$c$ 7 10 7 3 22 20 12 32 27 39
$r$ 1 2 3 4 2 2 3 2 2 2

Diagram. $r(0,4)=2$ makes float the root, $r(0,1)=1$ puts char on its left, $r(2,4)=3$ puts while on its right with else below it; cost $c(0,4)=39/20$. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-01" viewBox="0 0 328 194" width="328" height="194" role="img" aria-label="Optimal binary search tree from r(i,j); cost 39/20"><style>#dsfig-u3-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-01 .t{fill:#16181D;font-weight:500}#dsfig-u3-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-01 .dot{fill:#16181D}#dsfig-u3-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-01 .ah{fill:#454C5A}#dsfig-u3-01 .ah.hi{fill:#2340B8}#dsfig-u3-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-01 .e{stroke:#B1B7C3}html.dark #dsfig-u3-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-01 .t{fill:#E6E8ED}html.dark #dsfig-u3-01 .t.inv{fill:#0F1115}html.dark #dsfig-u3-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-01 .dot{fill:#E6E8ED}html.dark #dsfig-u3-01 .ann{fill:#8FA3FF}html.dark #dsfig-u3-01 .lbl{fill:#858D9C}html.dark #dsfig-u3-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-01 .ah{fill:#B1B7C3}html.dark #dsfig-u3-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah6" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh6" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="117.5" y1="37" x2="48.5" y2="101"/><line class="e" x1="117.5" y1="37" x2="186.5" y2="101"/><line class="e" x1="186.5" y1="101" x2="255.5" y2="165"/><rect class="n" x="88" y="22" width="59" height="30" rx="8"/><text class="t" x="117.5" y="37" dy=".35em" text-anchor="middle">float</text><rect class="n" x="22.5" y="86" width="52" height="30" rx="8"/><text class="t" x="48.5" y="101" dy=".35em" text-anchor="middle">char</text><rect class="n" x="157" y="86" width="59" height="30" rx="8"/><text class="t" x="186.5" y="101" dy=".35em" text-anchor="middle">while</text><rect class="n" x="229.5" y="150" width="52" height="30" rx="8"/><text class="t" x="255.5" y="165" dy=".35em" text-anchor="middle">else</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Optimal binary search tree from r(i,j); cost 39/20</figcaption></figure>

Answer frame. Open with the definition and the principle of optimality; for forward/backward give points 3-5 as a two-column contrast; for the comparison draw the table above and close with when each method applies; for OBST tabulate $w,c,r$ then draw the tree.

Asked: [7 marks] (Jun 2023) What do you mean by forward and backward approach of problem solving in Dynamic Programming? Asked: [7 marks] (Jun 2024) Use the function OBST to compute $w(i,j)$, $r(i,j)$, $c(i,j)$, $0 \le i<j \le 4$ for (char, float, while, else) with $p=(1/20,1/5,1/10,1/20)$, $q(0..2)=(1/5,1/10,1/5)$, $q(4)=1/20$; construct the optimal binary search tree. Asked: [7 marks] (Jun 2026) Compare dynamic programming, greedy method and divide and conquer method in detail.

0/1 knapsack

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>Given $n$ items with weights $w_i$ and profits $p_i$ and capacity $m$, 0/1 knapsack chooses $x_i\in\{0,1\}$ to maximise $\sum p_ix_i$ subject to $\sum w_ix_i\le m$; an item is taken whole or not at all.</mark>

Key points.

  1. Optimal substructure (principle of optimality): if item $n$ is in an optimal solution, the rest is optimal for capacity $m-w_n$ and items $1..n-1$.
  2. Let $f(i,y)$ be the best profit using items $1..i$ with capacity $y$; the choice for item $i$ is exclude or include.
  3. Exclude keeps $f(i-1,y)$; include gives $f(i-1,y-w_i)+p_i$, allowed only if $w_i\le y$.
  4. Start with $f(0,y)=0$ and $f(i,0)=0$, and fill row by row; the answer is $f(n,m)$.
  5. Traceback: from $(n,m)$, if $f(i,y)\ne f(i-1,y)$ then $x_i=1$ and $y\leftarrow y-w_i$, else $x_i=0$.
  6. Time and space are $O(nm)$, which is pseudo-polynomial because $m$ is a number, not an input length.

$$f(i,y)=\max\big(f(i-1,y),\ f(i-1,y-w_i)+p_i\big)$$

Example (n=3, w=(2,3,3), p=(1,2,4), m=6). Rows are items, columns $y=0..6$.

$i$ 0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
1 0 0 1 1 1 1 1
2 0 0 1 2 2 3 3
3 0 0 1 4 4 5 6

Traceback: $f(3,6)=6\ne f(2,6)=3$, so $x_3=1$, $y=3$; $f(2,3)=2\ne f(1,3)=1$, so $x_2=1$, $y=0$; $x_1=0$. Answer: $x=(0,1,1)$, profit 6, weight 6.

Other paper instances (same method): $w=(10,15,6,9),p=(2,5,8,1),M=30$ gives $x=(0,1,1,1)$, profit 14; $w=(2,3,4,5),p=(3,4,5,6),M=5$ gives $x=(1,1,0,0)$, profit 7; $n=4,m=40,w=(2,11,22,15),p=(11,21,31,33)$ gives $x=(1,0,1,1)$, profit 75, weight 39.

Set method ($S^i$). $S^i$ is the set of pairs $(P,W)$ reachable with items $1..i$, with $S^0=\{(0,0)\}$ and $S^i=S^{i-1}\cup\{(P+p_i,W+w_i)\}$; pairs with $W>m$ are dropped, and a pair is purged if another has profit at least as high and weight at most as low. For the $m=40$ instance, $S^4$ ends at $(75,39)$.

Instance with $|S^i|=2^i$. For each $n$ take $p_i=w_i=2^{i-1}$ ($1,2,4,\dots,2^{n-1}$) and $m=2^n-1$. Then the pairs of $S^i$ are $(s,s)$ for every integer $s=0..2^i-1$, all distinct; for $s>t$ the pair $(s,s)$ has more profit but also more weight than $(t,t)$, so nothing is purged and $|S^i|=2^i$, which shows the worst case is exponential.

Answer frame. Open with the definition and $x_i\in\{0,1\}$; write the recurrence and boundary values, then fill the table, trace back, and box the profit and items; close with $O(nm)$. For the recursive-equation question add the principle of optimality and the include/exclude cases.

Pitfall: Do not take items by profit/weight ratio; that is the fractional (greedy) knapsack and can be wrong for 0/1.

Asked: [7 marks] (May 2019) Write the recursive equation for 0/1 Knapsack based on the principle of optimality. Explain its execution strategy. Asked: [7 marks] (Jun 2022, Jun 2023, Nov 2023, Dec 2024, Jun 2025) How is the knapsack problem solved by dynamic programming? Find the optimal solution for $n=3$, $w=(2,3,3)$, $p=(1,2,4)$, $m=6$; for $w=(10,15,6,9)$, $p=(2,5,8,1)$, $M=30$; for $n=4$, $M=5$, $w=(2,3,4,5)$, $p=(3,4,5,6)$. Asked: [7 marks] (Nov 2023, Jun 2025) Give an example of a set of knapsack instances for which $|S^i|=2^i$, $0\le i\le n$, one instance for each $n$. Asked: [7 marks] (Dec 2024, Jun 2025) Solve the 0/1 knapsack problem by dynamic programming with $n=4$, $m=40$, $w=(2,11,22,15)$, $p=(11,21,31,33)$. Asked: [7 marks] (Jun 2025) Give an example of a set of knapsack instances for which $|S^i|=2^i$, $0\le i\le n$. Asked: [7 marks] (Jun 2026) Explain the 0-1 knapsack problem and discuss its solution.

Multistage graph

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. ==A multistage graph is a directed weighted graph whose vertices are split into $k\ge2$ disjoint stages $V_1..V_k$, where every edge goes from a vertex in $V_i$ to a vertex in $V_{i+1}$, and $V_1=\{s\}$ and $V_k=\{t\}$ are the single source and sink.==

Key points.

  1. The vertices are partitioned into stages, and $s$ is alone in the first stage and $t$ alone in the last.
  2. Edges join only consecutive stages, so the graph is a directed acyclic graph with no edge inside a stage.
  3. Every edge $(u,v)$ carries a cost $c(u,v)$, and the aim is the minimum-cost $s$-$t$ path.
  4. Every $s$-$t$ path has exactly one vertex in each stage, so choosing a path is a sequence of $k-2$ decisions.
  5. Forward approach: $cost(i,j)=\min_{l\in V_{i+1},(j,l)\in E}[c(j,l)+cost(i+1,l)]$ with $cost(k,t)=0$, computed from the last stage backwards; store the chosen $l$ as $d(i,j)$.
  6. Backward approach computes $bcost(i,j)=\min[bcost(i-1,l)+c(l,j)]$ from the source. Time is $O(|V|+|E|)$.

Example (Jun 2024, Dec 2024). Stages $S\,|\,A,B,C\,|\,D,E\,|\,T$. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-02" viewBox="0 0 467 338" width="467" height="338" role="img" aria-label="Multistage graph S to T; S is the source and T the sink"><style>#dsfig-u3-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-02 .t{fill:#16181D;font-weight:500}#dsfig-u3-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-02 .dot{fill:#16181D}#dsfig-u3-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-02 .ah{fill:#454C5A}#dsfig-u3-02 .ah.hi{fill:#2340B8}#dsfig-u3-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-02 .e{stroke:#B1B7C3}html.dark #dsfig-u3-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-02 .t{fill:#E6E8ED}html.dark #dsfig-u3-02 .t.inv{fill:#0F1115}html.dark #dsfig-u3-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-02 .dot{fill:#E6E8ED}html.dark #dsfig-u3-02 .ann{fill:#8FA3FF}html.dark #dsfig-u3-02 .lbl{fill:#858D9C}html.dark #dsfig-u3-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-02 .ah{fill:#B1B7C3}html.dark #dsfig-u3-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah7" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh7" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M53.4,155.6 L154.2,54.8" marker-end="url(#ah7)"/><path class="e" d="M59,169 L148,169" marker-end="url(#ah7)"/><path class="e" d="M53.4,182.4 L154.2,283.2" marker-end="url(#ah7)"/><path class="e" d="M187,46 L278.1,76.4" marker-end="url(#ah7)"/><path class="e" d="M178.8,56.3 L287.2,237" marker-end="url(#ah7)"/><path class="e" d="M184.8,158.5 L280.5,94.6" marker-end="url(#ah7)"/><path class="e" d="M184.8,179.5 L280.5,243.4" marker-end="url(#ah7)"/><path class="e" d="M187,292 L278.1,261.6" marker-end="url(#ah7)"/><path class="e" d="M186,289.5 L408.2,178.4" marker-end="url(#ah7)"/><path class="e" d="M313.8,93.5 L409.5,157.4" marker-end="url(#ah7)"/><path class="e" d="M313.8,244.5 L409.5,180.6" marker-end="url(#ah7)"/><g class="wl"><rect x="94.9" y="95.5" width="19.2" height="18" rx="9"/><text class="t" x="104.5" y="104.5" dy=".35em" text-anchor="middle">1</text></g><g class="wl"><rect x="94.9" y="160" width="19.2" height="18" rx="9"/><text class="t" x="104.5" y="169" dy=".35em" text-anchor="middle">2</text></g><g class="wl"><rect x="94.9" y="224.5" width="19.2" height="18" rx="9"/><text class="t" x="104.5" y="233.5" dy=".35em" text-anchor="middle">7</text></g><g class="wl"><rect x="223.9" y="52.5" width="19.2" height="18" rx="9"/><text class="t" x="233.5" y="61.5" dy=".35em" text-anchor="middle">3</text></g><g class="wl"><rect x="223.9" y="138.5" width="19.2" height="18" rx="9"/><text class="t" x="233.5" y="147.5" dy=".35em" text-anchor="middle">6</text></g><g class="wl"><rect x="223.9" y="117" width="19.2" height="18" rx="9"/><text class="t" x="233.5" y="126" dy=".35em" text-anchor="middle">4</text></g><g class="wl"><rect x="220.3" y="203" width="26.4" height="18" rx="9"/><text class="t" x="233.5" y="212" dy=".35em" text-anchor="middle">10</text></g><g class="wl"><rect x="223.9" y="267.5" width="19.2" height="18" rx="9"/><text class="t" x="233.5" y="276.5" dy=".35em" text-anchor="middle">3</text></g><g class="wl"><rect x="284.8" y="224.5" width="26.4" height="18" rx="9"/><text class="t" x="298" y="233.5" dy=".35em" text-anchor="middle">10</text></g><g class="wl"><rect x="352.9" y="117" width="19.2" height="18" rx="9"/><text class="t" x="362.5" y="126" dy=".35em" text-anchor="middle">8</text></g><g class="wl"><rect x="352.9" y="203" width="19.2" height="18" rx="9"/><text class="t" x="362.5" y="212" dy=".35em" text-anchor="middle">2</text></g><circle class="n" cx="40" cy="169" r="18"/><text class="t" x="40" y="169" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="169" cy="169" r="18"/><text class="t" x="169" y="169" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="169" cy="298" r="18"/><text class="t" x="169" y="298" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="298" cy="83" r="18"/><text class="t" x="298" y="83" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="298" cy="255" r="18"/><text class="t" x="298" y="255" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="427" cy="169" r="18"/><text class="t" x="427" y="169" dy=".35em" text-anchor="middle">T</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Multistage graph S to T; S is the source and T the sink</figcaption></figure> $cost(E)=2$, $cost(D)=8$, $cost(C)=\min(3+2,10)=5$, $cost(B)=\min(4+8,10+2)=12$, $cost(A)=\min(3+8,6+2)=8$ via E, $cost(S)=\min(1+8,2+12,7+5)=9$ via A. Answer: path S-A-E-T, minimum cost 9.

Answer frame. For "what is it, properties" write the definition then points 1-4 and one shortest-path use. For the numerical, list stages, apply point 5 from $T$ backwards node by node, then trace the $d$ values from $S$ and box the cost.

Pitfall: Picking the cheapest edge at each step (S-A-D-T = 12) is greedy and not optimal; the paper's "greedy" wording still expects the stage-wise cost recurrence.

Asked: [7 marks] (May 2019, Dec 2020) What is a multistage graph? Write down its properties. Asked: [7 marks] (Jun 2024, Dec 2024) Construct a multistage graph for the given graph using the greedy method and find the minimum cost path from S to T. Asked: [14 marks] (Nov 2019) Write short notes: i) multistage graphs, ii) parallel algorithm, iii) NP complete problem. (Parts ii and iii belong to Units 4 and 5; part i is above.)

Reliability design

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>Reliability design chooses how many copies $m_i$ of each device to place in each of $n$ stages, connected in series, so that the system reliability $\prod_i \Phi_i(m_i)$ is maximum while the total cost $\sum c_im_i$ stays within budget $C$.</mark>

Key points.

  1. Each stage $i$ has a device of reliability $r_i$ and cost $c_i$, and stage $i$ with $m_i$ parallel copies has reliability $\Phi_i(m_i)=1-(1-r_i)^{m_i}$.
  2. The system works only if every stage works, so the overall reliability is the product of the stage reliabilities.
  3. Duplicating devices raises reliability but costs money, so the problem is a constrained maximisation with $m_i\ge1$.
  4. The upper bound on copies is $u_i=\lfloor (C+c_i-\sum_j c_j)/c_i\rfloor$, because every other stage needs at least one copy.
  5. Let $f_i(x)$ be the maximum reliability of stages $1..i$ with cost at most $x$; then the recurrence below holds with $f_0(x)=1$, and the answer is $f_n(C)$.
  6. Solve it as sets $S^i$ of pairs (reliability, cost), built from $S^{i-1}$ for each $m_i$, purging dominated pairs, and trace back the copies from the best pair.

$$f_i(x)=\max_{1\le m_i\le u_i}\big\{\Phi_i(m_i)\,f_{i-1}(x-c_im_i)\big\}$$

Example. $c=(30,15,20)$, $r=(0.9,0.8,0.5)$, $C=105$: $u=(2,3,3)$. The best feasible choice is $m=(1,2,2)$, costing 100 with reliability $0.9\times0.96\times0.75=0.648$. Answer: $m=(1,2,2)$, reliability 0.648.

Answer frame. Open with the series-stage model and the cost constraint; write points 1-2, then the recurrence with $u_i$ and the set method; finish with the example and its traceback.

Asked: [7 marks] (Jun 2023, Nov 2023) How can reliability design be obtained using dynamic programming? How is the reliability of a system determined using dynamic programming?

Floyd-Warshall algorithm

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>The Floyd-Warshall algorithm finds the shortest paths between all pairs of vertices of a weighted directed graph by dynamic programming: $D^{(k)}[i][j]$ is the shortest $i$ to $j$ distance using only vertices $1..k$ as intermediates.</mark>

Key points.

  1. It works on the weight matrix $D^{(0)}$, with $0$ on the diagonal, the edge weight where an edge exists, and $\infty$ otherwise.
  2. For each $k$, a path $i\to j$ either avoids $k$ or passes through $k$ once, splitting into $i\to k$ and $k\to j$.
  3. Row $k$ and column $k$ do not change in iteration $k$, so the update can be done in place on one matrix.
  4. Three nested loops give time $O(n^3)$ and space $O(n^2)$.
  5. It allows negative edges but not negative cycles; a negative diagonal entry reveals one.
  6. Keeping a predecessor matrix, updated when a shorter route is found, lets each path be printed.

$$D^{(k)}[i][j]=\min\big(D^{(k-1)}[i][j],\ D^{(k-1)}[i][k]+D^{(k-1)}[k][j]\big)$$

Step 1: D = W (weight matrix)
Step 2: for k = 1 to n
Step 3:   for i = 1 to n
Step 4:     for j = 1 to n
Step 5:       D[i][j] = min(D[i][j], D[i][k] + D[k][j])
Step 6: return D

Example (Nov 2019 and others). <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-03" viewBox="0 0 338 424" width="338" height="424" role="img" aria-label="Directed graph; edges 1-4:1, 1-2:8, 4-2:2, 3-1:4, 4-3:9, 2-3:1"><style>#dsfig-u3-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-03 .t{fill:#16181D;font-weight:500}#dsfig-u3-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-03 .dot{fill:#16181D}#dsfig-u3-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-03 .ah{fill:#454C5A}#dsfig-u3-03 .ah.hi{fill:#2340B8}#dsfig-u3-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-03 .e{stroke:#B1B7C3}html.dark #dsfig-u3-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-03 .t{fill:#E6E8ED}html.dark #dsfig-u3-03 .t.inv{fill:#0F1115}html.dark #dsfig-u3-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-03 .dot{fill:#E6E8ED}html.dark #dsfig-u3-03 .ann{fill:#8FA3FF}html.dark #dsfig-u3-03 .lbl{fill:#858D9C}html.dark #dsfig-u3-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-03 .ah{fill:#B1B7C3}html.dark #dsfig-u3-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M157.6,55.2 L52.6,195.2" marker-end="url(#ah8)"/><path class="e" d="M180.4,55.2 L285.4,195.2" marker-end="url(#ah8)"/><path class="e" d="M59,212 L277,212" marker-end="url(#ah8)"/><path class="e" d="M169,365 L169,61" marker-end="url(#ah8)"/><path class="e" d="M51.4,227.2 L156.4,367.2" marker-end="url(#ah8)"/><path class="e" d="M286.6,227.2 L181.6,367.2" marker-end="url(#ah8)"/><g class="wl"><rect x="94.9" y="117" width="19.2" height="18" rx="9"/><text class="t" x="104.5" y="126" dy=".35em" text-anchor="middle">1</text></g><g class="wl"><rect x="223.9" y="117" width="19.2" height="18" rx="9"/><text class="t" x="233.5" y="126" dy=".35em" text-anchor="middle">8</text></g><g class="wl"><rect x="159.4" y="203" width="19.2" height="18" rx="9"/><text class="t" x="169" y="212" dy=".35em" text-anchor="middle">2</text></g><g class="wl"><rect x="159.4" y="203" width="19.2" height="18" rx="9"/><text class="t" x="169" y="212" dy=".35em" text-anchor="middle">4</text></g><g class="wl"><rect x="94.9" y="289" width="19.2" height="18" rx="9"/><text class="t" x="104.5" y="298" dy=".35em" text-anchor="middle">9</text></g><g class="wl"><rect x="223.9" y="289" width="19.2" height="18" rx="9"/><text class="t" x="233.5" y="298" dy=".35em" text-anchor="middle">1</text></g><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">1</text><circle class="n" cx="40" cy="212" r="18"/><text class="t" x="40" y="212" dy=".35em" text-anchor="middle">4</text><circle class="n" cx="298" cy="212" r="18"/><text class="t" x="298" y="212" dy=".35em" text-anchor="middle">2</text><circle class="n" cx="169" cy="384" r="18"/><text class="t" x="169" y="384" dy=".35em" text-anchor="middle">3</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Directed graph; edges 1-4:1, 1-2:8, 4-2:2, 3-1:4, 4-3:9, 2-3:1</figcaption></figure> Rows are from 1,2,3,4 and columns to 1,2,3,4.

$D^{(0)}$ $D^{(1)}$ $D^{(2)}$ $D^{(3)}$ $D^{(4)}$
0 8 ∞ 1 0 8 ∞ 1 0 8 9 1 0 8 9 1 0 3 4 1
∞ 0 1 ∞ ∞ 0 1 ∞ ∞ 0 1 ∞ 5 0 1 6 5 0 1 6
4 ∞ 0 ∞ 4 12 0 5 4 12 0 5 4 12 0 5 4 7 0 5
∞ 2 9 0 ∞ 2 9 0 ∞ 2 3 0 7 2 3 0 7 2 3 0

Changes: $k=1$ gives $3\to2=12$, $3\to4=5$; $k=2$ gives $1\to3=9$, $4\to3=3$; $k=3$ gives $2\to1=5$, $2\to4=6$, $4\to1=7$; $k=4$ gives $1\to2=3$, $1\to3=4$, $3\to2=7$. Answer: $D^{(4)}$ above is the all-pairs shortest distance matrix.

Second paper graph (edges $2\to1=4$, $2\to3=3$, $4\to2=-1$, $4\to3=2$, $1\to3=-2$): $D^{(1)}$ sets $2\to3=2$; $D^{(2)}$ sets $4\to1=3$, $4\to3=1$; $k=3$ and $k=4$ change nothing. Final rows: 1: (0, ∞, -2, ∞); 2: (4, 0, 2, ∞); 3: (∞, ∞, 0, ∞); 4: (3, -1, 1, 0).

Answer frame. Open with the all-pairs idea and the recurrence; write the pseudocode, then draw the graph, $D^{(0)}$ and each $D^{(k)}$ listing only changed cells; close with $O(n^3)$ and the final matrix.

Asked: [7 marks] (Nov 2019, Dec 2020, Jun 2024, Dec 2024) Use the Floyd-Warshall algorithm to find the shortest path between all pairs of vertices for the given graph (1->4:1, 1->2:8, 4->2:2, 3->1:4, 4->3:9, 2->3:1). Asked: [7 marks] (May 2019, Jun 2020, Jun 2025, Jun 2026) Write the pseudo code for Floyd-Warshall and apply it on a graph to find all-pair shortest paths; explain it with an example of your choice. Asked: [7 marks] (Jun 2024, Dec 2024, Jun 2025) Explain the Floyd-Warshall algorithm for the given graph (2->1=4, 2->3=3, 4->2=-1, 4->3=2, 1->3=-2), or with a suitable example.

Last-minute revision

  • DP needs optimal substructure and overlapping subproblems; results are stored in a table.
  • Forward = bottom-up tabulation; backward = top-down memoization.
  • 0/1 knapsack: $f(i,y)=\max(f(i-1,y),f(i-1,y-w_i)+p_i)$, time $O(nm)$.
  • Knapsack answers: $(2,3,3)/(1,2,4)/6$ gives 6 with $x=(0,1,1)$; $(10,15,6,9)/(2,5,8,1)/30$ gives 14; $(2,3,4,5)/(3,4,5,6)/5$ gives 7; $m=40$ instance gives 75.
  • $|S^i|=2^i$ instance: $p_i=w_i=2^{i-1}$, $m=2^n-1$.
  • Multistage graph: DAG in stages, edges only between consecutive stages; recurrence $cost(i,j)=\min[c(j,l)+cost(i+1,l)]$.
  • S-A-E-T costs 9 in the paper's multistage graph.
  • Reliability: $\Phi_i(m)=1-(1-r_i)^m$; example $C=105$ gives $m=(1,2,2)$ and 0.648.
  • Floyd-Warshall: $D^{(k)}[i][j]=\min(D^{(k-1)}[i][j],D^{(k-1)}[i][k]+D^{(k-1)}[k][j])$, $O(n^3)$.
  • Floyd final matrix for the 4-vertex paper graph: rows (0,3,4,1), (5,0,1,6), (4,7,0,5), (7,2,3,0).
  • OBST for the Jun 2024 data has root float and cost $39/20$.

Memory hooks

  • Table, then trace back: fill the table forward, read the answer backward.
  • Include or exclude: two branches per item, take the max.
  • Multistage: one vertex per stage, so $k-2$ choices.
  • Floyd: k is the middle stop, and k goes in the outermost loop.
  • DP is greedy that remembers and checks every option.

Coverage checklist

  • Concept of dynamic programming: forward and backward approach (Jun 2023), OBST tables and tree (Jun 2024), comparison of DP, greedy and divide and conquer (Jun 2026).
  • 0/1 knapsack: recursive equation (May 2019), four numerical instances (Jun 2022 to Jun 2025), $|S^i|=2^i$ instance (Nov 2023, Jun 2025), explain 0-1 knapsack (Jun 2026).
  • multistage graph: definition and properties (May 2019, Dec 2020), stage-wise construction (Jun 2024, Dec 2024), short note (Nov 2019).
  • reliability design: DP formulation (Jun 2023, Nov 2023).
  • Floyd-Warshall algorithm: numerical (Nov 2019, Dec 2020, Jun 2024, Dec 2024), pseudocode and example (May 2019, Jun 2020, Jun 2025, Jun 2026), explain for the given graph (Jun 2024, Dec 2024, Jun 2025).
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in