Skip to content

Concepts_Lab.md

Latest commit

 

History

History
765 lines (568 loc) · 26.4 KB

Concepts_Lab.md

File metadata and controls

765 lines (568 loc) · 26.4 KB
Raw

Week 5 Lab — Greedy Algorithms

Repository Guide | English | 한국어

Last Updated: 2026-11-04

Learning Objectives:

  1. Experimentally verify the success and failure conditions of greedy algorithms
  2. Implement fractional knapsack using a greedy value/weight ratio strategy
  3. Build a Huffman coding tree and analyze compression efficiency
  4. Apply greedy strategies to a real scheduling problem

Table of Contents


1. Overview

1.1 Lab Goals

  • Observe when the greedy approach works and when it fails through the coin change problem.
  • Implement Fractional Knapsack and understand why greedy is optimal when items can be split.
  • Build a Huffman coding tree and measure compression efficiency.
  • Apply Activity Selection (greedy by end time) to a meeting room scheduling problem.

1.2 Lab Structure

Section Topic
A-1 Coin Change (greedy success/failure)
A-2 Fractional Knapsack
A-3 Huffman Coding
B-1 Meeting Room Reservation System

Table 1. Topic of each lab section

1.3 Environment

The Type A code uses only the standard library, so no external packages are required; Flask is needed only for B-1.


2. Type A: Algorithm Implementation

2.1 A-1: Coin Change

Observe when the greedy approach works and when it fails by comparing it with an optimal DP solution.

2.1.1 Problem

Goal: Apply the same greedy rule to two coin sets and compare the results with the optimal solution.

Case 1: Greedy succeeds

Coins: [500, 100, 50, 10]    Amount: 1260

Greedy strategy: always pick the largest coin possible
  500 -> 500 -> 100 -> 100 -> 50 -> 10
  = 6 coins  (this IS optimal)

Case 2: Greedy fails

Coins: [1, 3, 4]    Amount: 6

Greedy: pick largest first
  4 -> 1 -> 1 = 3 coins

Optimal (DP):
  3 -> 3     = 2 coins  <-- fewer coins!

Why does greedy fail? This coin set does not form a divisor relationship (4 is not a multiple of 3), and picking the locally best coin 4 blocks the globally better combination 3 + 3.

2.1.2 Greedy Code

def coin_change_greedy(amount, coins):
    """
    Calculate change using the greedy approach.

    Algorithm: Use the largest coin as much as possible first
    Time complexity: O(k * amount/min_coin) (k = number of coin types)
    Space complexity: O(amount/min_coin) (result list)
    """
    # Sort coins in descending order (key to greedy selection)
    coins_sorted = sorted(coins, reverse=True)
    result = []
    remaining = amount
    # For each coin, use it as many times as possible
    for coin in coins_sorted:
        while remaining >= coin:
            result.append(coin)
            remaining -= coin
    # Success if remaining is 0, failure otherwise
    return result if remaining == 0 else None

2.1.3 DP Comparison

def coin_change_dp(amount, coins):
    """
    Calculate minimum number of coins using DP (always guarantees optimal solution).

    Algorithm: dp[i] = minimum number of coins to make amount i
    Recurrence: dp[i] = min(dp[i - c] + 1) (for all coins c)
    Time complexity: O(k * amount)
    Space complexity: O(amount)
    """
    # dp[i]: minimum number of coins to make amount i (initial value: infinity)
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # Base case: amount 0 requires 0 coins
    parent = [-1] * (amount + 1)  # For backtracking: last coin used at each amount
    # Try all coins for every amount
    for i in range(1, amount + 1):
        for c in coins:
            # If coin c can be used and results in fewer coins
            if c <= i and dp[i - c] + 1 < dp[i]:
                dp[i] = dp[i - c] + 1
                parent[i] = c  # Record the coin used for backtracking
    # If the amount cannot be made
    if dp[amount] == float('inf'):
        return None
    # Backtrack: recover the coins used by following the parent array
    result = []
    cur = amount
    while cur > 0:
        result.append(parent[cur])
        cur -= parent[cur]
    return result

Key takeaway:

Coin set Greedy DP Same?
[500, 100, 50, 10] Optimal Optimal Yes
[1, 3, 4] 3 coins 2 coins No

Table 2. Greedy and DP results for each coin set

Greedy is always optimal when coins have the divisor property (each coin divides the next larger one). This property is sufficient but not necessary: as with the US coins in Section 2.1.4, greedy can be optimal for some coin sets without it.

2.1.4 Extended Test Cases

The file a1_coin_change_greedy.py provides a detailed comparison across multiple coin sets:

Success cases (greedy = optimal):

Label Coins Amount Greedy Optimal
Korean standard [500, 100, 50, 10] 770 Optimal Optimal
US standard [25, 10, 5, 1] 63 Optimal Optimal

Table 3. Coin sets for which greedy is optimal

Failure cases (greedy > optimal):

Label Coins Amount Greedy Optimal
Failure 1 [7, 5, 1] 10 7+1+1+1 = 4 coins 5+5 = 2 coins
Failure 2 [6, 4, 1] 8 6+1+1 = 3 coins 4+4 = 2 coins
Failure 3 [12, 9, 1] 18 12+1x6 = 7 coins 9+9 = 2 coins

Table 4. Coin sets for which greedy is not optimal

When greedy is optimal:

  • Greedy is optimal when each coin is a multiple of smaller coins (e.g., 500, 100, 50, 10).
  • In this case, the greedy choice property holds.

When greedy fails:

  • Greedy can fail when the divisibility relationship between coins does not hold. However, as with the US standard [25, 10, 5, 1], greedy can be optimal even without it.
  • In this case, DP must be used to guarantee the optimal solution.
  • Time complexity: Greedy O(k) (when the count of each coin is computed by division), DP O(k * amount) (k = number of coin types).

2.2 A-2: Fractional Knapsack

2.2.1 Problem

Problem: Given items with weights and values, maximize total value in a knapsack of limited capacity. Items can be split.

Knapsack capacity: 50kg

Item    Weight   Value   Value/kg
----------------------------------
A        10kg      60      6.0
B        20kg     100      5.0
C        30kg     120      4.0

Greedy strategy: Sort by value-per-weight ratio (descending), then fill greedily.

Step 1: Take all of A  (10 kg, value 60)   remaining: 40 kg
Step 2: Take all of B  (20 kg, value 100)  remaining: 20 kg
Step 3: Take 2/3 of C  (20 kg, value 80)   remaining: 0 kg
                                   Total value: 240

2.2.2 Solution

def fractional_knapsack(capacity, items):
    """
    Solve the fractional knapsack problem using a greedy approach.

    Args:
        capacity: Maximum weight of the knapsack
        items: [(name, weight, value), ...] list

    Returns:
        (maximum value, list of selected items)
        Selected items: [(name, weight added, value added, ratio, was_split), ...]
    """
    # Sort by value/weight ratio in descending order
    sorted_items = sorted(items, key=lambda x: x[2] / x[1], reverse=True)
    total_value = 0.0
    remaining_capacity = capacity
    selected = []

    for name, weight, value in sorted_items:
        if remaining_capacity <= 0:
            break

        ratio = value / weight

        if weight <= remaining_capacity:
            # Can fit the entire item
            selected.append((name, weight, value, ratio, False))
            total_value += value
            remaining_capacity -= weight
        else:
            # Split the item
            fraction = remaining_capacity / weight
            partial_value = value * fraction
            selected.append((name, remaining_capacity, partial_value, ratio, True))
            total_value += partial_value
            remaining_capacity = 0

    return total_value, selected

2.2.3 Extended Example

Applying the same algorithm to a 5-item knapsack with capacity 40kg gives the following.

Knapsack capacity: 40 kg

Name       Weight   Value    Ratio
------------------------------------
Jewels      5.0kg     300    60.0/kg
Gold       10.0kg     600    60.0/kg
Silver     20.0kg     500    25.0/kg
Ceramics   15.0kg     200    13.3/kg
Copper     30.0kg     400    13.3/kg

Greedy selection process:

  1. Jewels: added full 5.0 kg (value 300, remaining 35.0kg)
  2. Gold: added full 10.0 kg (value 600, remaining 25.0kg)
  3. Silver: added full 20.0 kg (value 500, remaining 5.0kg)
  4. Ceramics: 33.3% (5.0 kg) added (value 67, remaining 0.0kg). This item is split.

Maximum value: 1467

2.2.4 Fractional vs 0-1 Knapsack

For comparison, the following code solves the 0-1 knapsack problem by brute force.

def knapsack_01_bruteforce(capacity, items):
    """
    Solve the 0-1 knapsack problem using brute force (for comparison).
    Time complexity: O(2^n * n) -- checks all subsets
    """
    n = len(items)
    best_value = 0
    best_selection = []

    for mask in range(1 << n):
        total_weight = 0
        total_value = 0
        selection = []
        for i in range(n):
            if mask & (1 << i):
                name, weight, value = items[i]
                total_weight += weight
                total_value += value
                selection.append(i)
        if total_weight <= capacity and total_value > best_value:
            best_value = total_value
            best_selection = selection

    return best_value, best_selection
     Fractional             0-1 Knapsack
    (can split)           (all or nothing)
+-----------------+     +-----------------+
| Greedy works!   |     | Greedy FAILS    |
| O(n log n)      |     | Need DP: O(nW)  |
+-----------------+     +-----------------+
         value: 240              value: 220

Why the difference?
  Fractional: "How much to take?" -> continuous choice
         0-1: "Take or skip?"     -> discrete choice

Figure 1. Comparison of fractional and 0-1 knapsack

Key insight: Fractional knapsack can always achieve value >= 0-1 knapsack.

Why greedy is optimal for fractional knapsack:

  • Prioritizing items with the highest value per unit weight maintains optimal selection for the remaining capacity.
  • Since items can be split, the problem is to decide how much of each item to include rather than whether to include it.
  • Time complexity: O(n log n), dominated by sorting.

2.3 A-3: Huffman Coding

2.3.1 Problem

Problem: Given character frequencies, build an optimal binary prefix code.

Text: "abracadabra"

Character frequencies:
  'a': 5    'b': 2    'r': 2    'c': 1    'd': 1

Greedy strategy: Repeatedly merge the two lowest-frequency nodes.

Step 1: Merge 'c'(1) + 'd'(1) = [2]
Step 2: Merge 'b'(2) + 'r'(2) = [4]
Step 3: Merge [2]   + [4]     = [6]
Step 4: Merge 'a'(5) + [6]    = [11]

Key property: It is a prefix code. No codeword is a prefix of another, so decoding is unambiguous without delimiters.

2.3.2 Huffman Tree

graph TD
    r["[11]"] -->|"0"| a["'a'(5)"]
    r -->|"1"| n6["[6]"]
    n6 -->|"0"| n2["[2]"]
    n6 -->|"1"| n4["[4]"]
    n2 -->|"0"| c["'c'(1)"]
    n2 -->|"1"| d["'d'(1)"]
    n4 -->|"0"| b["'b'(2)"]
    n4 -->|"1"| rr["'r'(2)"]
Loading

Figure 2. Huffman tree for "abracadabra"

Resulting codes:

Char Freq Code Bits
a 5 0 1
b 2 110 3
r 2 111 3
c 1 100 3
d 1 101 3

Table 5. Code for each character from the Huffman tree

High-frequency characters get short codes, and low-frequency characters get long codes.

2.3.3 Core Code

import heapq
from collections import Counter

class HuffmanNode:
    # A node in the Huffman tree.
    def __init__(self, char=None, freq=0, left=None, right=None):
        self.char, self.freq = char, freq
        self.left, self.right = left, right
    def __lt__(self, other):
        return self.freq < other.freq
    def is_leaf(self):
        return self.left is None and self.right is None

def build_frequency_table(text):
    # Calculate the character frequency of the text
    return dict(Counter(text).most_common())

def build_huffman_tree(freq_table):
    # Build a Huffman tree from the frequency table.
    # Greedy choice: Merge the two nodes with the lowest frequency at each step.
    heap = []
    for char, freq in freq_table.items():
        heapq.heappush(heap, HuffmanNode(char=char, freq=freq))

    # Handle case with only one unique character
    if len(heap) == 1:
        node = heapq.heappop(heap)
        return HuffmanNode(freq=node.freq, left=node)

    # Merge the two smallest nodes until only one remains
    while len(heap) > 1:
        left = heapq.heappop(heap)       # lowest freq
        right = heapq.heappop(heap)      # 2nd lowest
        merged = HuffmanNode(
            freq=left.freq + right.freq,
            left=left, right=right)
        heapq.heappush(heap, merged)

    return heapq.heappop(heap)

def generate_codes(root, prefix="", codes=None):
    # Traverse the Huffman tree to generate the code for each character.
    # Left edge = '0', Right edge = '1'
    if codes is None:
        codes = {}
    if root is None:
        return codes
    if root.is_leaf():
        codes[root.char] = prefix if prefix else "0"
        return codes
    generate_codes(root.left, prefix + "0", codes)
    generate_codes(root.right, prefix + "1", codes)
    return codes

2.3.4 Encoding and Decoding

The functions that encode and decode text with the Huffman codes are as follows.

def encode(text, codes):
    # Encode the text using Huffman codes.
    return "".join(codes[char] for char in text)

def decode(encoded_text, root):
    # Decode an encoded bit string using the Huffman tree.
    decoded = []
    current = root
    for bit in encoded_text:
        if bit == "0":
            current = current.left
        else:
            current = current.right
        if current.is_leaf():
            decoded.append(current.char)
            current = root
    return "".join(decoded)

Encoding example:

Text:    "abracadabra"
Encoded: "01101110100010101101110"    (23 bits)
Decoded: "abracadabra"                (matches original: PASS)

Prefix code verification: No Huffman code is a prefix of another, which ensures unambiguous decoding without delimiters.

2.3.5 Compression Results

Text: "abracadabra" (11 chars)

                           Bits     Bits/char
----------------------------------------------
ASCII (8-bit):              88       8.000
Fixed-length (3b):          33       3.000
Huffman:                    23       2.091
Theoretical lower bound:    22.4     2.040

Results on other texts:

Text Huffman bits/char Entropy Savings vs ASCII
"abracadabra" 2.091 2.040 73.9%
"the quick brown fox..." 4.023 3.944 49.7%
"aaaaaaaabbbbccdd" 1.750 1.750 78.1%

Table 6. Huffman compression results for each text

Why is Huffman greedy?

  • At each step, merge the two least frequent nodes.
  • This locally optimal choice leads to a globally optimal prefix code.
  • It is proven optimal among all prefix codes.

Time complexity: O(n log n), where n is the number of distinct characters; each heap operation is O(log n), and n-1 merges are performed.


3. Type B: Web Code Analysis

3.1 B-1: Meeting Room Reservation System

3.1.1 Problem

Install dependencies first with pip install flask, then run the Flask app and open http://localhost:5000.

Problem: Given a list of meeting requests with start/end times, find the maximum number of non-overlapping meetings that can be scheduled.

Meeting requests:
  A: [1, 4)    B: [3, 5)    C: [0, 6)
  D: [5, 7)    E: [3, 9)    F: [5, 9)
  G: [6, 8)    H: [8, 11)   I: [8, 12)

Timeline:
  A: |===|
  B:   |==|
  C:|======|
  D:     |==|
  E:   |======|
  F:     |====|
  G:      |==|
  H:        |===|
  I:        |====|

Figure 3. Time intervals of meeting requests A-I

Which meetings should we select to maximize the count?

3.1.2 Solution

Greedy strategy: Sort by end time, then greedily pick non-overlapping activities.

Sorted by end time:
  A: [1,4)  B: [3,5)  C: [0,6)  D: [5,7)  G: [6,8)
  E: [3,9)  F: [5,9)  H: [8,11)  I: [8,12)

Selection process:
  Pick A [1,4)    last_end = 4
  Skip B [3,5)    3 < 4, overlaps
  Skip C [0,6)    0 < 4, overlaps
  Pick D [5,7)    5 >= 4, OK!  last_end = 7
  Skip G [6,8)    6 < 7, overlaps
  Skip E [3,9)    3 < 7, overlaps
  Skip F [5,9)    5 < 7, overlaps
  Pick H [8,11)   8 >= 7, OK!  last_end = 11
  Skip I [8,12)   8 < 11, overlaps

Result: {A, D, H} = 3 meetings

3.1.3 Greedy Code

def greedy_schedule(meetings):
    """
    Select the maximum number of meetings using greedy.

    Activity Selection: Sort by end time in ascending order,
    then select meetings that do not overlap with the previously selected one.

    Time complexity: O(n log n) -- sorting dominates

    Args:
        meetings: [{"id": int, "name": str, "start": float, "end": float}, ...]

    Returns:
        List of selected meeting ids
    """
    sorted_meetings = sorted(meetings, key=lambda m: m["end"])
    selected = []
    last_end = -1

    for meeting in sorted_meetings:
        if meeting["start"] >= last_end:
            selected.append(meeting["id"])
            last_end = meeting["end"]

    return selected

Why sorting by end time works:

  • Choosing the meeting that finishes earliest leaves the most room for future meetings.
  • This greedy choice is provably optimal.
  • Time complexity: O(n log n) for sorting.

3.1.4 Brute Force Comparison

The web app also provides a brute force algorithm for comparison (limited to N <= 20):

def bruteforce_schedule(meetings):
    """
    Select the maximum number of meetings using brute force.
    Checks all subsets to find the maximum number of non-overlapping meetings.
    Time complexity: O(2^n * n) -- checks all subsets
    """
    n = len(meetings)
    if n > 20:
        return None  # Prevent timeout

    def is_compatible(subset):
        sorted_sub = sorted(subset, key=lambda m: m["start"])
        for i in range(1, len(sorted_sub)):
            if sorted_sub[i]["start"] < sorted_sub[i - 1]["end"]:
                return False
        return True

    best_selection = []
    for size in range(n, 0, -1):
        for combo in combinations(meetings, size):
            if is_compatible(combo):
                return [m["id"] for m in combo]

    return best_selection

Web UI features:

  • Load sample meeting data (8, 12, or 15 meetings)
  • Add custom meetings with name, start time, and end time
  • Visual timeline showing selected (green) and rejected (red) meetings
  • Run Greedy, Brute Force, or both algorithms side-by-side
  • Verify that greedy always matches the optimal brute force result

4. When Does Greedy Work?

For greedy to guarantee an optimal solution, the following two conditions must hold.

  1. Greedy Choice Property: A locally optimal choice is part of a globally optimal solution.
  2. Optimal Substructure: After making a greedy choice, the remaining subproblem is also optimally solvable.

Summary

Concept Key Summary
Coin change Greedy gives the optimal solution for standard denominations but can fail for arbitrary coin sets.
Fractional knapsack When items can be split, greedy by value/weight ratio is optimal.
Huffman coding Greedily merging the two lowest-frequency nodes produces an optimal prefix code.
Activity selection Sorting by end time and greedily picking non-overlapping activities gives a maximum non-overlapping set.
Conditions for greedy The greedy choice property and optimal substructure must both hold.

Self-Check Questions

  1. Greedy Coin Change Failure: Why does the greedy coin change algorithm fail for coins [1, 3, 4] with amount 6? What property of coin denominations guarantees that greedy always works?

    Answer

    Greedy picks the largest coin first: 4 → 1 → 1 = 3 coins, but optimal is 3 + 3 = 2 coins. The greedy choice of 4 strands a remainder of 2 that cannot be made with one coin, while picking the smaller 3 aligns perfectly with the remaining amount. If the denominations have the divisor property (each coin is a multiple of the next smaller one, as in {1, 10, 50, 100, 500}), greedy is always optimal. This structure guarantees that committing to the biggest coin never blocks a globally better combination. The divisor property is sufficient but not necessary: in {1, 5, 10, 25}, 25 is not a multiple of 10, yet greedy is still always optimal.

  2. 0-1 Knapsack and Greedy: If items cannot be split (0-1 knapsack), why does the greedy value/weight ratio strategy fail? Give a concrete example.

    Answer

    In 0-1 knapsack a high-ratio item can strand capacity that cannot be filled with a fraction of another item. With the items A(10kg, 60), B(20kg, 100), C(30kg, 120) of Section 2.2.1 and capacity 50kg, greedy picks A then B for a value of 160 with 20kg left empty. The 0-1 optimum is B + C = 220, which gives up the best ratio item to use the capacity fully. The greedy-choice property fails because choosing only whether to include each item is a discrete choice; you cannot top off the leftover with 2/3 of C as you would in the fractional case.

  3. Huffman Coding and Entropy: In the Huffman coding example, how close is the average bits per character to the theoretical entropy lower bound? What does this gap tell us?

    Answer

    For "abracadabra", Huffman achieves 2.091 bits/char, while the entropy lower bound computed from the character frequencies is about 2.040 bits/char, a gap of about 0.051 bits/char (about 2.5%). The gap exists because Huffman codes must use integer bit lengths for each symbol, while Shannon entropy assumes fractional bit allocations. Huffman is provably optimal among prefix codes, but to approach entropy you need techniques like arithmetic coding that effectively encode fractional bits. The gap shrinks as the probabilities approach negative powers of two (for "aaaaaaaabbbbccdd" it is zero), and it can grow when one symbol is very likely. Coding blocks of several symbols together reduces the gap.

  4. Sorting Key for Activity Selection: In activity selection, what would happen if you sorted by start time instead of end time? Would the greedy algorithm still produce an optimal solution?

    Answer

    No. Sorting by start time can pick a long-running activity that blocks many shorter, compatible ones. Counterexample: activities [0, 10), [1, 2), [3, 4), [5, 6). Earliest-start-first picks [0, 10), after which nothing else fits, so it gets only 1 activity. Earliest-finish-first picks [1, 2), [3, 4), [5, 6), which gives 3 activities. The earliest-finish heuristic works because finishing early leaves maximum remaining time for future picks; earliest-start gives no such guarantee since the chosen activity may run arbitrarily long.

  5. Worst Coin Set: For coin set {12, 9, 1} with amount 18, greedy uses 7 coins while optimal uses 2. Explain why this is the worst ratio among the test cases, and what makes this coin set particularly bad for greedy.

    Answer

    Greedy takes 12 first, leaving 6, but 9 no longer fits, so it falls back to six 1s for 7 coins. The optimum is 9 + 9 = 2 coins, so greedy is exactly 3.5× worse. This is the worst ratio because the gap between 12 and 9 is small (taking 12 reduces the amount by only 3 more than taking 9), so the greedy gain is tiny, but picking 12 destroys the ability to use 9 at all for the remainder. The denominations are pairwise close yet non-divisible: there is no fallback coin between 9 and 1, so any stranded remainder collapses into a long tail of pennies.

  6. Brute Force vs Greedy: The brute force knapsack and meeting scheduler both examine all subsets. Why is brute force limited to small N, and how does greedy avoid this?

    Answer

    Brute force enumerates all $2^n$ subsets: at N=20 that is about $10^6$ (manageable), at N=30 about $10^9$ (seconds to minutes), and at N=50 about $10^{15}$ (intractable). The exponential blowup makes brute force infeasible for real-world inputs. Greedy runs in O(n log n) (dominated by sorting) and makes exactly one pass over the items, never enumerating subsets. It avoids the explosion by committing to a single locally optimal choice at each step rather than exploring alternatives. This trades the guaranteed correctness of exhaustive search for dramatic speed, which is justified when the greedy-choice property holds.