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

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

How unit 2 is examined

A greedy algorithm builds the answer by taking the locally best choice at each step; the marks sit in Huffman coding, minimum spanning trees, knapsack, job sequencing and Dijkstra, each with a numerical.

Study of Greedy strategy

<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>A greedy algorithm builds a solution step by step, always taking the choice that looks best at that moment and never revisiting it.</mark>

Key points.

  1. Greedy works only when the problem has the greedy-choice property (a locally best choice can be part of some global optimum) and optimal substructure.
  2. The general method selects an element from the candidate set, checks that it is feasible, adds it to the solution, and repeats until the candidates run out.
  3. Greedy is usually simple and fast, typically $O(n \log n)$ because of the sort, but it can fail: greedy 0/1 knapsack is not optimal.
  4. Classic greedy problems are Huffman coding, spanning trees, fractional knapsack, job sequencing and Dijkstra.
Step 1: solution = empty
Step 2: while candidates remain: x = select(candidates)
Step 3: if feasible(solution + x) then solution = solution + x
Step 4: return solution

Graph colouring by greedy. Order the vertices 0..n-1; give each vertex the smallest colour not used by an already coloured neighbour. Example (edges 0-1, 0-2, 1-2, 1-3, 2-4, 3-4, 3-5, 4-5): 0 gets 1; 1 gets 2; 2 gets 3; 3 gets 1 (neighbour 1 has 2); 4 gets 2 (neighbours 2 and 3 have 3 and 1); 5 gets 3. Colours used = 3. The count depends on the vertex order.

Scheduling n jobs on k processors (LPT). Sort jobs by time descending; keep a min-heap of processor finish times; give each job to the processor that becomes free first and add $t_i$ to it. The last finish time is the makespan. Complexity $O(n \log n + n \log k)$. This greedy is a good approximation, not always exact.

Answer frame. Open with the definition; write the general pseudocode; apply it to the question's problem step by step; close with the result and complexity.

Asked: [7 marks] (Jun 2025) n jobs, k parallel processors, job i takes time $t_i$: write an algorithm that assigns jobs to processors and orders them so the finish time of the last job is minimised. Asked: [7 marks] (Jun 2026) What is "Greedy Algorithm"? Write its pseudocode. Apply Greedy algorithm on colouring the vertices of a given graph.

Optimal merge patterns

<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">Not asked since 2022</span>

Definition. Optimal merge pattern finds the order of merging n sorted files pairwise so that the total number of record moves is minimum.

Key points.

  1. Merging files of sizes $a$ and $b$ costs $a+b$, so the order of merges changes the total cost.
  2. Greedy rule: always merge the two smallest files currently available and put the result back.
  3. The merge tree is a Huffman tree, and total cost $=\sum d_i q_i$ (depth times size of each file), which equals the sum of all internal node values.
  4. Example 5, 10, 20, 30, 30: 15, then 35, then 60, then 95 gives cost $15+35+60+95=205$. Complexity is $O(n \log n)$ with a min-heap.

Huffman coding

<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>Huffman coding is a greedy method that builds an optimal prefix code by repeatedly merging the two lowest-frequency symbols, so frequent symbols get short codes.</mark>

Diagram. Decode tree for M1..M7 with frequencies 4, 5, 7, 8, 10, 12, 20 (internal nodes show merged weight; left edge 0, right edge 1).

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-01" viewBox="0 0 949 326" width="949" height="326" role="img" aria-label="Huffman decode tree for M1-M7, left edge 0, right edge 1"><style>#dsfig-u2-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-01 .t{fill:#16181D;font-weight:500}#dsfig-u2-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-01 .dot{fill:#16181D}#dsfig-u2-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-01 .ah{fill:#454C5A}#dsfig-u2-01 .ah.hi{fill:#2340B8}#dsfig-u2-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-01 .e{stroke:#B1B7C3}html.dark #dsfig-u2-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-01 .t{fill:#E6E8ED}html.dark #dsfig-u2-01 .t.inv{fill:#0F1115}html.dark #dsfig-u2-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-01 .dot{fill:#E6E8ED}html.dark #dsfig-u2-01 .ann{fill:#8FA3FF}html.dark #dsfig-u2-01 .lbl{fill:#858D9C}html.dark #dsfig-u2-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-01 .ah{fill:#B1B7C3}html.dark #dsfig-u2-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah3" 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="ahh3" 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="393.5" y1="39" x2="117.5" y2="103"/><line class="e" x1="393.5" y1="39" x2="807.5" y2="103"/><line class="e" x1="117.5" y1="103" x2="48.5" y2="167"/><line class="e" x1="117.5" y1="103" x2="255.5" y2="167"/><line class="e" x1="255.5" y1="167" x2="186.5" y2="231"/><line class="e" x1="255.5" y1="167" x2="324.5" y2="231"/><line class="e" x1="807.5" y1="103" x2="669.5" y2="167"/><line class="e" x1="807.5" y1="103" x2="876.5" y2="167"/><line class="e" x1="669.5" y1="167" x2="531.5" y2="231"/><line class="e" x1="669.5" y1="167" x2="738.5" y2="231"/><line class="e" x1="531.5" y1="231" x2="462.5" y2="295"/><line class="e" x1="531.5" y1="231" x2="600.5" y2="295"/><circle class="n" cx="393.5" cy="39" r="17"/><text class="t" x="393.5" y="39" dy=".35em" text-anchor="middle">66</text><circle class="n" cx="117.5" cy="103" r="17"/><text class="t" x="117.5" y="103" dy=".35em" text-anchor="middle">27</text><rect class="n" x="19" y="152" width="59" height="30" rx="8"/><text class="t" x="48.5" y="167" dy=".35em" text-anchor="middle">M6 12</text><circle class="n" cx="255.5" cy="167" r="17"/><text class="t" x="255.5" y="167" dy=".35em" text-anchor="middle">15</text><rect class="n" x="160.5" y="216" width="52" height="30" rx="8"/><text class="t" x="186.5" y="231" dy=".35em" text-anchor="middle">M3 7</text><rect class="n" x="298.5" y="216" width="52" height="30" rx="8"/><text class="t" x="324.5" y="231" dy=".35em" text-anchor="middle">M4 8</text><circle class="n" cx="807.5" cy="103" r="17"/><text class="t" x="807.5" y="103" dy=".35em" text-anchor="middle">39</text><circle class="n" cx="669.5" cy="167" r="17"/><text class="t" x="669.5" y="167" dy=".35em" text-anchor="middle">19</text><circle class="n" cx="531.5" cy="231" r="17"/><text class="t" x="531.5" y="231" dy=".35em" text-anchor="middle">9</text><rect class="n" x="436.5" y="280" width="52" height="30" rx="8"/><text class="t" x="462.5" y="295" dy=".35em" text-anchor="middle">M1 4</text><rect class="n" x="574.5" y="280" width="52" height="30" rx="8"/><text class="t" x="600.5" y="295" dy=".35em" text-anchor="middle">M2 5</text><rect class="n" x="709" y="216" width="59" height="30" rx="8"/><text class="t" x="738.5" y="231" dy=".35em" text-anchor="middle">M5 10</text><rect class="n" x="847" y="152" width="59" height="30" rx="8"/><text class="t" x="876.5" y="167" dy=".35em" text-anchor="middle">M7 20</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Huffman decode tree for M1-M7, left edge 0, right edge 1</figcaption></figure>

Key points.

  1. A prefix code means no codeword is the prefix of another, so a bit string decodes uniquely without separators.
  2. Fixed-length codes waste bits; Huffman gives variable-length codes that minimise the average length.
  3. Build with a min-heap: pick the two smallest weights, join them under a new node with their sum, and repeat until one node (the root) remains.
  4. Label left edges 0 and right edges 1; the codeword of a leaf is the edge labels from root to leaf.
  5. Average length $L=\sum p_i l_i$; for frequencies, total bits $=\sum f_i l_i$.
  6. Complexity is $O(n \log n)$. Ties give different but equally optimal codes.

Steps. Merges for (4, 5, 7, 8, 10, 12, 20): 4+5=9; 7+8=15; 9+10=19; 12+15=27; 19+20=39; 27+39=66. Codes: M6=00, M3=010, M4=011, M1=1000, M2=1001, M5=101, M7=11. Total bits $=175$.

Example. Jun 2022 (A .4, B .1, C .2, D .15, E .15): B .1 + D .15 = .25; E .15 + C .2 = .35; .25 + .35 = .6; A .4 + .6 = 1.0. Codes A=0, B=100, D=101, E=110, C=111. $L=0.4(1)+0.1(3)+0.15(3)+0.15(3)+0.2(3)=2.2$. Decode 100 0 101 110 0 101 0 gives BADEADA.

Example. Nov 2019 (a .11, b .40, c .16, d .09, e .24): d+a=.20; c+.20=.36; e+.36=.60; b+.60=1. Codes b=0, e=10, c=110, d=1110, a=1111. $L = 0.4+0.48+0.48+0.36+0.44 = 2.16$ bits.

Example. (a 3, b 8, c 15, d 22, e 33, f 46): 11, 26, 48, 79, 127. Codes f=11, e=10, d=00, c=011, a=0100, b=0101.

Applications. File compression (ZIP, GZIP), JPEG and MP3/MPEG coding, text and fax transmission.

Answer frame. Open with the definition; draw the Huffman tree with 0/1 on edges; list merges, then the code table, then $L$; close with the applications.

Pitfall: Always re-sort after each merge so the two smallest are picked, and keep the same 0/1 convention throughout one tree.

Asked: [7 marks] (Dec 2024, Jun 2025) Construct a Huffman coding for the given data (a to f: 3, 8, 15, 22, 33, 46; also M1..M7 with 4, 5, 7, 8, 10, 12, 20 with decode tree). Write the applications of Huffman coding. Asked: [7 marks] (Nov 2019) Text of a, b, c, d, e with probabilities 0.11, 0.40, 0.16, 0.09, 0.24: average length of optimal Huffman code. Asked: [7 marks] (Jun 2022) Construct a Huffman code for A 0.4, B 0.1, C 0.2, D 0.15, E 0.15. Decode the text ending 100010111001010.

Minimum spanning trees

<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 spanning tree of a connected graph is a subtree containing all $n$ vertices with $n-1$ edges and no cycle; <mark>a minimum spanning tree (MST) is the spanning tree whose total edge weight is least.</mark>

Diagram. Jun 2019/Dec 2020 graph; MST edges highlighted (cost 99).

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-02" viewBox="0 0 510 338" width="510" height="338" role="img" aria-label="7-vertex graph, MST edges bold, cost 99"><style>#dsfig-u2-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-02 .t{fill:#16181D;font-weight:500}#dsfig-u2-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-02 .dot{fill:#16181D}#dsfig-u2-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-02 .ah{fill:#454C5A}#dsfig-u2-02 .ah.hi{fill:#2340B8}#dsfig-u2-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-02 .e{stroke:#B1B7C3}html.dark #dsfig-u2-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-02 .t{fill:#E6E8ED}html.dark #dsfig-u2-02 .t.inv{fill:#0F1115}html.dark #dsfig-u2-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-02 .dot{fill:#E6E8ED}html.dark #dsfig-u2-02 .ann{fill:#8FA3FF}html.dark #dsfig-u2-02 .lbl{fill:#858D9C}html.dark #dsfig-u2-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-02 .ah{fill:#B1B7C3}html.dark #dsfig-u2-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah4" 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="ahh4" 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 hi" d="M50.5,184.8 L115.5,282.2"/><path class="e" d="M55.2,157.6 L196.8,51.4"/><path class="e hi" d="M222.5,55.8 L287.5,153.2"/><path class="e hi" d="M231,40 L365,40"/><path class="e hi" d="M394.5,55.8 L459.5,153.2"/><path class="e" d="M451,169 L317,169"/><path class="e" d="M373.5,282.2 L308.5,184.8"/><path class="e hi" d="M459.5,184.8 L394.5,282.2"/><path class="e hi" d="M365,298 L145,298"/><g class="wl hi"><rect x="69.8" y="224.5" width="26.4" height="18" rx="9"/><text class="t" x="83" y="233.5" dy=".35em" text-anchor="middle">10</text></g><g class="wl"><rect x="112.8" y="95.5" width="26.4" height="18" rx="9"/><text class="t" x="126" y="104.5" dy=".35em" text-anchor="middle">28</text></g><g class="wl hi"><rect x="241.8" y="95.5" width="26.4" height="18" rx="9"/><text class="t" x="255" y="104.5" dy=".35em" text-anchor="middle">14</text></g><g class="wl hi"><rect x="284.8" y="31" width="26.4" height="18" rx="9"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">16</text></g><g class="wl hi"><rect x="413.8" y="95.5" width="26.4" height="18" rx="9"/><text class="t" x="427" y="104.5" dy=".35em" text-anchor="middle">12</text></g><g class="wl"><rect x="370.8" y="160" width="26.4" height="18" rx="9"/><text class="t" x="384" y="169" dy=".35em" text-anchor="middle">18</text></g><g class="wl"><rect x="327.8" y="224.5" width="26.4" height="18" rx="9"/><text class="t" x="341" y="233.5" dy=".35em" text-anchor="middle">24</text></g><g class="wl hi"><rect x="413.8" y="224.5" width="26.4" height="18" rx="9"/><text class="t" x="427" y="233.5" dy=".35em" text-anchor="middle">22</text></g><g class="wl hi"><rect x="241.8" y="289" width="26.4" height="18" rx="9"/><text class="t" x="255" y="298" dy=".35em" text-anchor="middle">25</text></g><circle class="n" cx="40" cy="169" r="18"/><text class="t" x="40" y="169" dy=".35em" text-anchor="middle">1</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">2</text><circle class="n" cx="384" cy="40" r="18"/><text class="t" x="384" y="40" dy=".35em" text-anchor="middle">3</text><circle class="n" cx="470" cy="169" r="18"/><text class="t" x="470" y="169" dy=".35em" text-anchor="middle">4</text><circle class="n" cx="384" cy="298" r="18"/><text class="t" x="384" y="298" dy=".35em" text-anchor="middle">5</text><circle class="n" cx="126" cy="298" r="18"/><text class="t" x="126" y="298" dy=".35em" text-anchor="middle">6</text><circle class="n" cx="298" cy="169" r="18"/><text class="t" x="298" y="169" dy=".35em" text-anchor="middle">7</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">7-vertex graph, MST edges bold, cost 99</figcaption></figure>

Key points.

  1. An MST has $n-1$ edges, is connected and acyclic; it is not unique when equal weights exist, though its cost is.
  2. Cut property: the lightest edge crossing any cut belongs to some MST; both algorithms rest on it.
  3. Kruskal sorts all edges and adds the next smallest edge if it forms no cycle (checked with union-find).
  4. Prim grows one tree from a start vertex, each time adding the cheapest edge joining the tree to a new vertex.
  5. Kruskal is $O(E\log E)=O(E\log V)$; Prim is $O(E\log V)$ with a heap, $O(V^2)$ with a matrix.
  6. Uses: network and road design, clustering, circuit wiring.

Example. Kruskal (sorted 10, 12, 14, 16, 18, 22, 24, 25, 28): take 1-6, 3-4, 2-7, 2-3; reject 4-7 (cycle); take 4-5; reject 5-7; take 5-6. Cost $=10+12+14+16+22+25=99$. Prim from 1: 1-6 (10), 6-5 (25), 5-4 (22), 4-3 (12), 3-2 (16), 2-7 (14). Cost $=99$.

Example. Jun 2024 6-vertex graph. Prim from 1: 1-3 (1), 3-6 (4), 6-4 (2), 3-2 (5), 2-5 (3). Cost $=15$; Kruskal picks the same weights: 1, 2, 3, 4, 5.

Proof (unique cycle). $t$ is connected, so the endpoints $u,v$ of $q$ already have a path $P$ in $t$; adding $q$ closes $P$ into a cycle, so a cycle exists. If a second, different cycle existed, then $t$ would have two distinct $u$-$v$ paths, and their union would contain a cycle inside $t$, contradicting that $t$ is a tree. Hence the cycle is unique.

Basis Kruskal Prim
Approach Picks the globally smallest edge, forest merges Grows a single tree from a start vertex
Data structure Sorted edge list and union-find Priority queue or matrix
Edge choice Any edge that forms no cycle Cheapest edge leaving the tree
Intermediate result May be a forest Always a connected tree
Time $O(E\log E)$ $O(E\log V)$ or $O(V^2)$
Best for Sparse graphs Dense graphs

Answer frame. Open with the definition of spanning tree and MST; draw the graph and highlight the MST; sort/list the steps; close with cost and complexity. For the comparison, give the table and end with sparse-versus-dense suitability.

Pitfall: In Kruskal, adding an edge that closes a cycle (like 4-7 above) loses the marks; check both endpoints' components.

Asked: [7 marks] (Nov 2019, Dec 2020) Tabulate the differences between Kruskal's and Prim's algorithm. Asked: [7 marks] (May 2019, Dec 2020) Apply Kruskal's and Prim's algorithm to the following graph; write their time complexities; find the minimum cost in each case. Asked: [7 marks] (Jun 2022, Jun 2024) Explain Prim's algorithm with example. Asked: [7 marks] (Nov 2023) Show that adding an edge $q \in E(G)$, $q \notin E(t)$, to a spanning tree $t$ of $G$ creates a unique cycle. Asked: [7 marks] (Jun 2023) Discuss briefly about the minimum spanning tree. Asked: [7 marks] (Jun 2024) Define spanning tree. Construct a minimal spanning tree for the given graph using Prim's algorithm. Asked: [7 marks] (Jun 2026) Explain Kruskal's algorithm with the help of suitable example.

Knapsack problem

<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. Given $n$ items with profits $p_i$ and weights $w_i$ and a bag of capacity $m$, <mark>choose fractions $x_i$ to maximise $\sum p_i x_i$ subject to $\sum w_i x_i \le m$.</mark>

Key points.

  1. In the fractional knapsack $0 \le x_i \le 1$; in the 0/1 knapsack each item is taken whole or not at all.
  2. Greedy by highest profit alone or by lowest weight alone can fail; the correct criterion is the largest ratio $p_i/w_i$.
  3. Sort items by ratio descending, take whole items while they fit, then take a fraction of the next item to fill the bag exactly.
  4. Fractional greedy is optimal; complexity is $O(n\log n)$ for the sort.
  5. Greedy is not optimal for 0/1 knapsack, which needs dynamic programming.
Step 1: compute p[i]/w[i]; sort items in descending order
Step 2: x[i] = 0 for all i; room = m
Step 3: for each item i in order: if w[i] <= room then x[i] = 1, room = room - w[i]
Step 4: else x[i] = room / w[i]; stop
Step 5: profit = sum of p[i]*x[i]

Example. $m=20$, $p=(25,24,15)$, $w=(18,15,10)$. Ratios $1.39, 1.6, 1.5$. Take item 2 (weight 15, room 5), then $5/10$ of item 3. $x=(0,1,\tfrac12)$. Profit $=24+7.5=31.5$.

Example. Same weights, $p=(30,21,18)$: ratios $1.67, 1.4, 1.8$. Item 3 whole (room 10), then $10/18$ of item 1. $x=(\tfrac59,0,1)$. Profit $=18+16.67=34.67$.

Example. $n=7$, $m=15$, $p=(10,5,15,7,6,18,3)$ (the printed "515" is 5, 15), $w=(2,3,5,7,1,4,1)$. Ratios $5, 1.67, 3, 1, 6, 4.5, 3$. Order: 5, 1, 6, 3, 7, 2, 4. Weights used 1, 2, 4, 5, 1 = 13; then $2/3$ of item 2. $x=(1,\tfrac23,1,0,1,1,1)$. Profit $=6+10+18+15+3+3.33=55.33$.

0/1 greedy. For $m=20$, $p=(25,24,15)$: by ratio take item 2 (15), item 3 does not fit (10 > 5), item 1 does not fit. Profit 24 with $x=(0,1,0)$; the true optimum is item 1 alone, 25, so greedy fails here.

Answer frame. Open by defining fractional and 0/1 knapsack; state the ratio rule; write the algorithm; do the ratio table and fill; close with the solution vector, profit, $O(n\log n)$ and the 0/1 limitation.

Pitfall: Do not take a fraction in 0/1 knapsack, and do not sort by profit alone.

Asked: [7 marks] (Nov 2019, Jun 2024, Jun 2026) Find an optimal solution to the knapsack instance $n=3$, $m=20$, $p=(25,24,15)$, $w=(18,15,10)$ (also the table with $W=(18,15,10)$, $P=(30,21,18)$). Asked: [7 marks] (May 2019, Dec 2020, Jun 2023) What is Knapsack problem? How can we solve using Greedy approach? Asked: [7 marks] (Jun 2020) Write a greedy knapsack algorithm; solve $n=7$, $m=15$, $p=(10,5,15,7,6,18,3)$, $w=(2,3,5,7,1,4,1)$. Asked: [7 marks] (Jun 2024) Apply the greedy method to the 0/1 knapsack, $n=3$, $m=20$, $w=(18,15,10)$, $p=(25,24,15)$.

Job sequencing with deadlines

<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. Each job $i$ has a profit $p_i$ and deadline $d_i$ and takes one unit of time; <mark>job sequencing selects a feasible subset of jobs, each finished by its deadline, so that total profit is maximum.</mark>

Key points.

  1. A subset is feasible if its jobs can be ordered so that every job finishes by its deadline; only one job runs per time slot.
  2. Greedy rule: consider jobs in decreasing order of profit.
  3. Place each job in the latest free slot at or before its deadline; if no such slot is free, reject it.
  4. The answer lists the selected jobs in slot order and their total profit.
  5. Complexity is $O(n^2)$ with the simple slot search, or $O(n\log n)$ with union-find.
Step 1: sort jobs by profit descending
Step 2: for each job i: find the latest free slot t <= d[i]
Step 3: if found, put job i in slot t; else reject i
Step 4: profit = sum of profits of scheduled jobs

Example. $n=5$, $p=(5,20,10,15,1)$, $d=(3,2,1,2,3)$. Order by profit: J2, J4, J3, J1, J5.

Job Profit Deadline Action
J2 20 2 slot 2
J4 15 2 slot 2 taken, slot 1
J3 10 1 slot 1 taken, reject
J1 5 3 slot 3
J5 1 3 all slots full, reject

Schedule J4, J2, J1. Maximum profit $=15+20+5=40$.

Example. $n=7$, $p=(3,5,20,18,1,6,30)$, $d=(1,3,4,3,2,1,2)$. Order: J7 (30, d2) slot 2; J3 (20, d4) slot 4; J4 (18, d3) slot 3; J6 (6, d1) slot 1; J2 (5, d3) no slot left, reject; J1 and J5 reject. Sequence J6, J7, J4, J3. Profit $=6+30+18+20=74$.

Example. $n=4$, $p=(100,10,15,27)$, $d=(2,1,2,1)$: J1 slot 2, J4 slot 1, rest rejected. Sequence J4, J1, profit 127.

Answer frame. Open with the problem definition; state the profit-first rule; show the sorted table and slot filling; close with sequence and profit.

Asked: [7 marks] (Nov 2023, Jun 2024, Dec 2024) What is the solution generated by the function JS when $n=7$, $p=(3,5,20,18,1,6,30)$, $d=(1,3,4,3,2,1,2)$? Asked: [7 marks] (Nov 2019, Jun 2022) Discuss job sequencing problem by an example. Asked: [14 marks] (Jun 2024, Dec 2024) Solve job sequencing with deadlines using the greedy method: $n=5$, $p=(5,20,10,15,1)$, $d=(3,2,1,2,3)$; also $n=4$, $p=(100,10,15,27)$, $d=(2,1,2,1)$.

Single source shortest path 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 single source shortest path problem finds the minimum-weight paths from one source vertex to every other vertex; Dijkstra's greedy algorithm solves it for non-negative edge weights.</mark>

Diagram. Jun 2020/2022/2025 instance with source a; shortest-path tree highlighted.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-03" viewBox="0 0 510 338" width="510" height="338" role="img" aria-label="Weighted graph; shortest distances a=0, b=3, d=5, c=7, e=9"><style>#dsfig-u2-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-03 .t{fill:#16181D;font-weight:500}#dsfig-u2-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-03 .dot{fill:#16181D}#dsfig-u2-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-03 .ah{fill:#454C5A}#dsfig-u2-03 .ah.hi{fill:#2340B8}#dsfig-u2-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-03 .e{stroke:#B1B7C3}html.dark #dsfig-u2-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-03 .t{fill:#E6E8ED}html.dark #dsfig-u2-03 .t.inv{fill:#0F1115}html.dark #dsfig-u2-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-03 .dot{fill:#E6E8ED}html.dark #dsfig-u2-03 .ann{fill:#8FA3FF}html.dark #dsfig-u2-03 .lbl{fill:#858D9C}html.dark #dsfig-u2-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-03 .ah{fill:#B1B7C3}html.dark #dsfig-u2-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah5" 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="ahh5" 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 hi" d="M55.2,157.6 L196.8,51.4"/><path class="e" d="M55.2,180.4 L196.8,286.6"/><path class="e hi" d="M231,40 L365,40"/><path class="e hi" d="M212,59 L212,279"/><path class="e" d="M373.5,55.8 L222.5,282.2"/><path class="e" d="M394.5,55.8 L459.5,153.2"/><path class="e hi" d="M229,289.5 L453,177.5"/><g class="wl hi"><rect x="116.4" y="95.5" width="19.2" height="18" rx="9"/><text class="t" x="126" y="104.5" dy=".35em" text-anchor="middle">3</text></g><g class="wl"><rect x="116.4" y="224.5" width="19.2" height="18" rx="9"/><text class="t" x="126" y="233.5" dy=".35em" text-anchor="middle">7</text></g><g class="wl hi"><rect x="288.4" y="31" width="19.2" height="18" rx="9"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">4</text></g><g class="wl hi"><rect x="202.4" y="160" width="19.2" height="18" rx="9"/><text class="t" x="212" y="169" dy=".35em" text-anchor="middle">2</text></g><g class="wl"><rect x="288.4" y="160" width="19.2" height="18" rx="9"/><text class="t" x="298" y="169" dy=".35em" text-anchor="middle">5</text></g><g class="wl"><rect x="417.4" y="95.5" width="19.2" height="18" rx="9"/><text class="t" x="427" y="104.5" dy=".35em" text-anchor="middle">6</text></g><g class="wl hi"><rect x="331.4" y="224.5" width="19.2" height="18" rx="9"/><text class="t" x="341" y="233.5" dy=".35em" text-anchor="middle">4</text></g><circle class="n" cx="40" cy="169" r="18"/><text class="t" x="40" y="169" dy=".35em" text-anchor="middle">a</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">b</text><circle class="n" cx="212" cy="298" r="18"/><text class="t" x="212" y="298" dy=".35em" text-anchor="middle">d</text><circle class="n" cx="384" cy="40" r="18"/><text class="t" x="384" y="40" dy=".35em" text-anchor="middle">c</text><circle class="n" cx="470" cy="169" r="18"/><text class="t" x="470" y="169" dy=".35em" text-anchor="middle">e</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Weighted graph; shortest distances a=0, b=3, d=5, c=7, e=9</figcaption></figure>

Key points.

  1. Keep a distance $d[v]$, set $d[\text{source}]=0$ and all others $\infty$.
  2. Repeatedly pick the unvisited vertex $u$ with the smallest $d[u]$ and mark it final.
  3. Relax every edge $(u,v)$: if $d[u]+w(u,v)<d[v]$, update $d[v]$ and record the parent $u$.
  4. Dijkstra fails with negative edges; use Bellman-Ford, $O(VE)$, for those.
  5. Complexity is $O(V^2)$ with an array, and $O((V+E)\log V)$ with a min-heap.
  6. Shortest vertices come out in non-decreasing order of distance, which is how the digraph question is answered.
Step 1: d[s] = 0; d[v] = infinity for all other v; S = empty
Step 2: repeat V times: u = unvisited vertex with least d[u]; add u to S
Step 3: for each neighbour v of u: if d[u] + w(u,v) < d[v] then d[v] = d[u] + w(u,v)

Example. Source a: pick a (0): b=3, d=7. Pick b (3): c=7, d=5. Pick d (5): e=9. Pick c (7): e stays 9. Pick e (9). Distances b=3, d=5, c=7, e=9; paths a-b, a-b-d, a-b-c, a-b-d-e.

Example. A to D on the Jun 2022 graph: A 0, B 2, E 4, G 5, F 6, H 8, C 9, D 10. Shortest path A-B-E-F-H-D, length 10. The unlabeled G-H edge does not change this unless its weight is under 3.

For the 1-6 digraph: run the same table from vertex 1 and list the final distances in increasing order.

Answer frame. Open with the problem definition; write the algorithm; draw the graph and a distance table showing each pick; close with the shortest paths and the complexity.

Pitfall: Do not finalise a vertex before it has the smallest tentative distance; and never use Dijkstra with negative weights.

Asked: [7 marks] (May 2019, Dec 2020, Jun 2023) Write algorithm for single source shortest path and find its complexity. Asked: [7 marks] (Jun 2020, Jun 2022, Jun 2025) Using Dijkstra's algorithm find the shortest path from A to D for the following graph (also instance with source a). Asked: [7 marks] (Jun 2025) Use algorithm shortest paths to obtain in non-decreasing order the lengths of the shortest paths from vertex 1 to all remaining vertices in the di-graph.

Last-minute revision

  • Greedy needs the greedy-choice property and optimal substructure.
  • Optimal merge: always merge the two smallest; 5, 10, 20, 30, 30 costs 205.
  • Huffman: merge the two lowest, left 0, right 1; $L=\sum p_il_i$, $O(n\log n)$.
  • Nov 2019 Huffman answer: $L=2.16$; Jun 2022 code has $L=2.2$; decode gives BADEADA.
  • MST has $n-1$ edges; Kruskal $O(E\log E)$, Prim $O(E\log V)$ or $O(V^2)$.
  • 7-vertex MST cost 99; 6-vertex Prim cost 15.
  • Fractional knapsack: sort by $p_i/w_i$; $(25,24,15),(18,15,10)$ gives 31.5.
  • 0/1 knapsack greedy gives 24 and is not optimal; the n=7 instance gives 55.33.
  • Job sequencing: profit descending, latest free slot; n=7 gives 74, n=5 gives 40.
  • Dijkstra: $O(V^2)$ or $O((V+E)\log V)$, no negative edges; A to D is 10.

Memory hooks

  • Huffman: "two smallest join hands", left zero and right one.
  • Kruskal = sort edges, Prim = grow tree; K for edges, P for vertex growth.
  • Knapsack: fill by "profit per kilo".
  • Job sequencing: "rich job first, as late as possible".
  • Dijkstra: pick the nearest unvisited, then relax.

Coverage checklist

  • Study of Greedy strategy: Jun 2025 k-processor scheduling, Jun 2026 greedy and colouring.
  • optimal merge patterns: no past questions, taught with the merge rule and example.
  • Huffman coding: Dec 2024/Jun 2025 a-f and M1-M7, Nov 2019 average length, Jun 2022 code and decode.
  • minimum spanning trees: comparison, Kruskal and Prim numerical, Prim, unique cycle proof, brief MST, Prim on 6 vertices, Kruskal.
  • knapsack problem: 3-item instance (both versions), explain, n=7 instance, 0/1 greedy.
  • job sequencing with deadlines: JS n=7, discuss by example, 14-mark n=5 and n=4.
  • single source shortest path algorithm: algorithm and complexity, A to D, digraph from vertex 1.
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