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[2]: You need a canonical example of a greedy strategy.,You are checking whether a problem fits the greedy-choice property.
  caveats[2]: 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[4]: 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[2]{section,field,type,example}:
    data,algorithm,string,Activity Selection
    data,use_case,string,Select maximum compatible activities given star…
data[11]{algorithm,use_case}:
  Activity Selection,Select maximum compatible activities given start and end times.
  Huffman Coding,Build optimal prefix-free binary encoding for symbols.
  Dijkstra Shortest Path,Find shortest paths from a source in graphs with non-negative weights.
  Kruskal MST,Build minimum spanning tree by adding cheapest edges.
  Fractional Knapsack,Maximize value when items can be broken into fractions.
  Job Sequencing,Schedule jobs with deadlines to maximize profit.
  Prim's MST,Grow a minimum spanning tree by repeatedly adding the cheapest edge that connects a new vertex.
  Boruvka's MST,Build a minimum spanning tree by adding the cheapest outgoing edge of every component in parallel rounds.
  Coin Change (canonical systems),Make change with the fewest coins using the largest coin first; optimal only for canonical coin systems such as US coins.
  Optimal Merge Pattern,Merge sorted files with minimum total cost by always merging the two smallest.
  Greedy Set Cover,Approximate the smallest collection of sets covering all elements by repeatedly picking the set that covers the most uncovered elements.