Project 13: Greedy Algorithms Collection

Build a set of greedy solutions and compare them with optimal results.

Quick Reference

Attribute Value
Difficulty Level 3: Advanced
Time Estimate 2 weeks
Language Python (Alternatives: C++, Java, Go)
Prerequisites Projects 9 and 10, sorting and heaps
Key Topics Greedy, proofs, optimization

1. Learning Objectives

By completing this project, you will:

  1. Implement classic greedy algorithms.
  2. Identify when greedy is valid and when it fails.
  3. Prove correctness using exchange arguments.
  4. Compare greedy solutions to DP or brute force.

2. Theoretical Foundation

2.1 Core Concepts

  • Greedy choice: Make the locally optimal choice at each step.
  • Exchange argument: Show that a greedy choice can be transformed into an optimal solution.
  • Matroid structure: Explains when greedy works.
  • Counterexamples: Understanding failure cases is crucial.

2.2 Why This Matters

Greedy algorithms are fast and elegant, but only work when the problem structure allows it. This project builds intuition for that structure.

2.3 Historical Context / Background

Greedy methods power classic solutions like Huffman coding and interval scheduling, which show optimality under specific properties.

2.4 Common Misconceptions

  • Misconception: Greedy is always good enough. Reality: Some problems require DP.
  • Misconception: Greedy correctness is obvious. Reality: It needs proof.

3. Project Specification

3.1 What You Will Build

A collection of greedy algorithms with optional optimal comparisons and proofs, including interval scheduling, Huffman coding, and MST.

3.2 Functional Requirements

  1. Interval scheduling: Select max number of non-overlapping intervals.
  2. Huffman coding: Build optimal prefix codes.
  3. Activity selection: Similar to interval scheduling with weights.
  4. Coin change: Show greedy success/failure on different coin sets.
  5. Comparison: Optional DP check for optimality.

3.3 Non-Functional Requirements

  • Reliability: All algorithms pass tests on standard inputs.
  • Usability: CLI to run each problem with sample data.
  • Explainability: Output includes rationale or proof outline.

3.4 Example Usage / Output

$ ./greedy --intervals intervals.txt
Selected: (1,3) (4,6) (7,9)

$ ./greedy --huffman text.txt
Total bits: 812

3.5 Real World Outcome

You will be able to run greedy solutions and see where they succeed or fail, along with an explanation of the greedy choice.

4. Solution Architecture

4.1 High-Level Design

┌───────────┐     ┌──────────────┐     ┌─────────────┐
│ CLI Input │────▶│ Greedy Core  │────▶│ Reporter    │
└───────────┘     └──────┬───────┘     └─────────────┘
                            │
                      ┌─────▼─────┐
                      │ Proof Notes│
                      └───────────┘

4.2 Key Components

Component Responsibility Key Decisions
greedy.py Algorithm implementations Common input formats
proofs.py Correctness notes Exchange argument templates
compare.py Optional DP comparison Small input sizes only

4.3 Data Structures

# Example for interval scheduling
intervals = [(1, 3), (2, 5), (4, 6)]

4.4 Algorithm Overview

Key Algorithm: Interval Scheduling

  1. Sort by end time.
  2. Pick earliest finishing interval.
  3. Repeat with remaining intervals.

Complexity Analysis:

  • Time: O(n log n)
  • Space: O(1)

5. Implementation Guide

5.1 Development Environment Setup

python3 -m venv .venv
. .venv/bin/activate

5.2 Project Structure

greedy-toolkit/
├── src/
│   ├── greedy.py
│   ├── proofs.py
│   ├── compare.py
│   └── cli.py
├── data/
└── tests/

5.3 The Core Question You’re Answering

“When does a locally optimal choice produce a globally optimal result?”

5.4 Concepts You Must Understand First

Stop and research these before coding:

  1. Exchange arguments
  2. Matroid intuition
  3. Proof by contradiction

5.5 Questions to Guide Your Design

  1. How will you show greedy failures clearly?
  2. Which problems will you compare with DP?
  3. How will you present proof outlines in output?

5.6 Thinking Exercise

Given coin set [1, 3, 4], test greedy for amount 6. Compare with optimal.

5.7 The Interview Questions They’ll Ask

  1. Prove interval scheduling correctness.
  2. Explain why Huffman coding is optimal.
  3. Give an example where greedy fails.

5.8 Hints in Layers

Hint 1: Use sorted inputs Sorting is usually the first greedy step.

Hint 2: Add a DP verifier Small inputs can confirm greedy optimality.

Hint 3: Show counterexamples Use coin sets where greedy fails.

5.9 Books That Will Help

Topic Book Chapter
Greedy method “Algorithms Illuminated (Part 3)” Ch. 13-15
Huffman coding “Introduction to Algorithms” Ch. 16
Proof techniques “Algorithm Design” Ch. 4

5.10 Implementation Phases

Phase 1: Foundation (4-5 days)

Goals:

  • Implement interval scheduling
  • Add proofs in docs

Tasks:

  1. Sort intervals by end time.
  2. Add proof outline output.

Checkpoint: Selected intervals are optimal.

Phase 2: Huffman and Coin Change (5-6 days)

Goals:

  • Implement Huffman coding
  • Add coin change examples

Tasks:

  1. Build Huffman tree with heap.
  2. Compare greedy vs optimal coin change.

Checkpoint: Huffman code lengths match expectations.

Phase 3: Compare and Polish (3-4 days)

Goals:

  • Add DP comparisons
  • Add CLI summaries

Tasks:

  1. Add optional DP for small inputs.
  2. Output differences when greedy fails.

Checkpoint: CLI shows success/failure cases.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Proof display text, markdown text Simple CLI
DP comparison optional yes Demonstrates correctness
Huffman structure tree nodes struct nodes Clear traversal

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests Greedy correctness Interval sets
Integration Tests CLI runs Huffman on sample text
Edge Case Tests Small inputs Single interval

6.2 Critical Test Cases

  1. Interval scheduling with overlapping intervals.
  2. Coin set where greedy fails.
  3. Huffman coding on uniform distribution.

6.3 Test Data

intervals: [(1,3), (2,4), (3,5)]
coins: [1, 3, 4] amount=6

7. Common Pitfalls and Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Wrong sort key Non-optimal result Sort by finish time
Missing base cases Infinite recursion Validate input
Wrong priority in Huffman Non-optimal codes Use min-heap

7.2 Debugging Strategies

  • Compare greedy results with brute force on small inputs.
  • Print Huffman tree structure and verify prefix property.

7.3 Performance Traps

Exponential brute-force comparison should be used only for small input sizes.

8. Extensions and Challenges

8.1 Beginner Extensions

  • Add job sequencing with deadlines.
  • Add fractional knapsack.

8.2 Intermediate Extensions

  • Add matroid intersection example.
  • Add scheduling with weights.

8.3 Advanced Extensions

  • Implement approximation algorithms for NP-hard problems.
  • Add proof checker output for greedy steps.

9. Real-World Connections

9.1 Industry Applications

  • Compression (Huffman coding)
  • Scheduling and resource allocation
  • libhuffman: Huffman coding libraries.
  • OR-Tools: Scheduling optimizers.

9.3 Interview Relevance

Greedy vs DP decisions and Huffman coding appear in interviews and competitions.

10. Resources

10.1 Essential Reading

  • “Algorithms Illuminated (Part 3)” by Roughgarden - Ch. 13-15
  • “Introduction to Algorithms” - Ch. 16

10.2 Video Resources

  • Greedy algorithm tutorials and proofs

10.3 Tools and Documentation

  • Python heapq for Huffman

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain why interval scheduling greedy works.
  • I can show a counterexample where greedy fails.
  • I can justify Huffman optimality.

11.2 Implementation

  • Algorithms pass tests.
  • CLI clearly explains results.

11.3 Growth

  • I can decide between greedy and DP for a new problem.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Interval scheduling and Huffman coding
  • CLI outputs results

Full Completion:

  • Coin change failure example
  • Proof outline output

Excellence (Going Above and Beyond):

  • Approximation algorithm examples
  • Greedy proof checker

This guide was generated from LEARN_ALGORITHMS_DEEP_DIVE.md. For the complete learning path, see the parent directory.