How do you define optimal solution? Does greedy algorithm always guarantee optimal solution? Huffman Tree Construction

---

Part A: Definition of Optimal Solution

An optimal solution is the best possible solution to a problem that maximizes or minimizes the objective function while satisfying all given constraints.

• It is the solution with the lowest cost, shortest path, maximum profit, or best outcome depending on the problem.
• Among all feasible solutions, the optimal solution is the one that gives the most efficient result.

---

Part B: Does Greedy Algorithm Always Guarantee Optimal Solution?

No, a greedy algorithm does not always guarantee an optimal solution.

• A greedy algorithm makes locally optimal choices at each step, hoping to reach a globally optimal solution.
• It works optimally only for problems that exhibit:
  • Greedy Choice Property — a locally optimal choice leads to a globally optimal solution
  • Optimal Substructure — an optimal solution contains optimal solutions to subproblems

Cases where greedy gives optimal solution:

• Huffman Coding
• Fractional Knapsack
• Minimum Spanning Tree (Kruskal's, Prim's)
• Activity Selection Problem

Cases where greedy FAILS to give optimal solution:

• 0/1 Knapsack Problem
• Travelling Salesman Problem

---

Part C: Huffman Tree for "SUPER DUPER CSIT"

Step i: Calculate Frequency of each character

String: S U P E R D U P E R C S I T

Character	Frequency
S	2
U	2
P	2
E	2
R	2
(space)	2
D	1
C	1
I	1
T	1

Total characters = 16

Step ii: Build the Huffman Tree using Greedy approach

The greedy strategy is: always pick two nodes with the smallest frequencies and merge them.

a. Pick D(1) and C(1) → merge → new node DC(2)

b. Pick I(1) and T(1) → merge → new node IT(2)

c. Now all nodes have frequency 2: S(2), U(2), P(2), E(2), R(2), Space(2), DC(2), IT(2)

d. Pick S(2) and U(2) → merge → SU(4)

e. Pick P(2) and E(2) → merge → PE(4)

f. Pick R(2) and Space(2) → merge → R_(4)

g. Pick DC(2) and IT(2) → merge → DCIT(4)

h. Pick SU(4) and PE(4) → merge → SUPE(8)

i. Pick R_(4) and DCIT(4) → merge → R_DCIT(8)

j. Pick SUPE(8) and R_DCIT(8) → merge → Root(16)

Step iii: Final Huffman Tree Structure

Step iv: Assign Huffman Codes (Left = 0, Right = 1)

Character	Code	Bits
S	000	3
U	001	3
P	010	3
E	011	3
R	100	3
Space	101	3
D	1100	4
C	1101	4
I	1110	4
T	1111	4

Step v: Calculate Total Bits

$$\text{Total bits} = (2+2+2+2+2+2) \times 3 + (1+1+1+1) \times 4 = 12 \times 3 + 4 \times 4 = 36 + 16 = 52 \text{ bits}$$

---

Conclusion

The Huffman coding algorithm is a perfect example where the greedy approach guarantees an optimal solution — it produces the minimum weighted path length (prefix-free code) for data compression. However, greedy algorithms do not guarantee optimality for all problems.