api: YAML JSON TOON Database
version: 1.0.0
format: json
dataset:
  slug: greedy-algorithms
  title: Greedy Algorithms
  description: Algorithms that make locally optimal choices at each step.
  summary: "Greedy algorithms and the problems they solve: activity selection, Huffman coding, Dijkstra, Kruskal, fractional knapsack and job sequencing, extended with Prim's and Boruvka's spanning-tree algorithms, canonical coin change, optimal merge patterns and greedy set-cover approximation."
  use_when:
    - You need a canonical example of a greedy strategy.
    - You are checking whether a problem fits the greedy-choice property.
  caveats:
    - Greedy gives optimal answers only for problems with the greedy-choice property; the 0/1 knapsack and general coin change are counterexamples.
    - A greedy algorithm can still be a good approximation when it is not optimal, as for set cover.
  related:
    - dynamic-programming-patterns
    - graph-algorithms
    - graph-traversal-algorithms
    - complexity-classes
  category: Algorithms
  category_slug: algorithms
  tags: algorithms,greedy,optimization
  view_count: 0
  entry_count: 11
  fields:
    - section: data
      field: algorithm
      type: string
      example: Activity Selection
    - section: data
      field: use_case
      type: string
      example: Select maximum compatible activities given star…
data:
  - algorithm: Activity Selection
    use_case: Select maximum compatible activities given start and end times.
  - algorithm: Huffman Coding
    use_case: Build optimal prefix-free binary encoding for symbols.
  - algorithm: Dijkstra Shortest Path
    use_case: Find shortest paths from a source in graphs with non-negative weights.
  - algorithm: Kruskal MST
    use_case: Build minimum spanning tree by adding cheapest edges.
  - algorithm: Fractional Knapsack
    use_case: Maximize value when items can be broken into fractions.
  - algorithm: Job Sequencing
    use_case: Schedule jobs with deadlines to maximize profit.
  - algorithm: Prim's MST
    use_case: Grow a minimum spanning tree by repeatedly adding the cheapest edge that connects a new vertex.
  - algorithm: Boruvka's MST
    use_case: Build a minimum spanning tree by adding the cheapest outgoing edge of every component in parallel rounds.
  - algorithm: Coin Change (canonical systems)
    use_case: Make change with the fewest coins using the largest coin first; optimal only for canonical coin systems such as US coins.
  - algorithm: Optimal Merge Pattern
    use_case: Merge sorted files with minimum total cost by always merging the two smallest.
  - algorithm: Greedy Set Cover
    use_case: Approximate the smallest collection of sets covering all elements by repeatedly picking the set that covers the most uncovered elements.