844 Fundamental

Greedy Algorithm Patterns

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Greedy Algorithm Patterns" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Greedy algorithms make locally optimal choices at each step, hoping for a global optimum. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Greedy algorithms make locally optimal choices at each step, hoping for a global optimum. Unlike dynamic programming which considers all subproblems, greedy algorithms commit to a choice and never reconsider. When a greedy choice property holds — meaning there always exists an optimal solution that includes the greedy choice — greedy algorithms are correct and typically O(n log n) (dominated by sorting). Classic greedy problems: interval scheduling (schedule maximum activities), fractional knapsack, Huffman coding, Prim's/Kruskal's MST, and coin change (for standard denominations). Recognizing when greedy works (and when it fails) is a key algorithm design skill.

🎯 Learning Outcomes

• Identify the greedy choice property: locally optimal → globally optimal

• Implement interval scheduling maximization: sort by end time, greedily pick non-overlapping intervals

• Implement fractional knapsack: sort by value/weight ratio, greedily fill

• Understand exchange argument proofs: show swapping greedy choice for any other cannot improve

• Recognize when greedy fails: 0/1 knapsack, coin change with non-standard denominations

Code Example

#![allow(clippy::all)]
//! Placeholder

(* Greedy Algorithms: Activity Selection + Huffman Coding in OCaml *)

(* Activity Selection Problem *)
type activity = { id: int; start: int; finish: int }

(* Greedy: sort by finish time, pick non-overlapping activities *)
let activity_selection (activities : activity list) : activity list =
  let sorted = List.sort (fun a b -> compare a.finish b.finish) activities in
  let rec select last_finish = function
    | [] -> []
    | a :: rest ->
      if a.start >= last_finish then
        a :: select a.finish rest
      else
        select last_finish rest
  in
  select 0 sorted

(* Huffman Coding *)
type huffman =
  | Leaf of { symbol: char; freq: int }
  | Node of { freq: int; left: huffman; right: huffman }

let freq_of = function Leaf l -> l.freq | Node n -> n.freq

(* Simple priority queue using sorted list *)
let insert_sorted tree lst =
  let rec ins = function
    | [] -> [tree]
    | h :: t ->
      if freq_of tree <= freq_of h then tree :: h :: t
      else h :: ins t
  in
  ins lst

let huffman_tree (symbols : (char * int) list) : huffman option =
  match symbols with
  | [] -> None
  | _ ->
    let initial = List.sort (fun (_, a) (_, b) -> compare a b)
      (List.map (fun (c, f) -> Leaf { symbol=c; freq=f }) symbols)
    in
    let rec build = function
      | [tree] -> tree
      | a :: b :: rest ->
        let merged = Node { freq = freq_of a + freq_of b; left = a; right = b } in
        build (insert_sorted merged rest)
      | [] -> failwith "empty"
    in
    Some (build initial)

(* Extract code table: symbol -> binary string *)
let huffman_codes (tree : huffman) : (char * string) list =
  let codes = ref [] in
  let rec traverse prefix = function
    | Leaf l -> codes := (l.symbol, if prefix = "" then "0" else prefix) :: !codes
    | Node n ->
      traverse (prefix ^ "0") n.left;
      traverse (prefix ^ "1") n.right
  in
  traverse "" tree;
  List.sort compare !codes

let () =
  (* Activity selection *)
  let acts = [
    {id=1; start=1; finish=4};
    {id=2; start=3; finish=5};
    {id=3; start=0; finish=6};
    {id=4; start=5; finish=7};
    {id=5; start=3; finish=9};
    {id=6; start=5; finish=9};
    {id=7; start=6; finish=10};
    {id=8; start=8; finish=11};
    {id=9; start=8; finish=12};
    {id=10; start=2; finish=14};
  ] in
  let selected = activity_selection acts in
  Printf.printf "Activity selection: %d activities selected (ids: %s)\n"
    (List.length selected)
    (String.concat "," (List.map (fun a -> string_of_int a.id) selected));

  (* Huffman coding *)
  let freqs = [('a', 5); ('b', 2); ('c', 1); ('d', 3); ('e', 4); ('f', 7)] in
  match huffman_tree freqs with
  | None -> ()
  | Some tree ->
    let codes = huffman_codes tree in
    Printf.printf "\nHuffman codes:\n";
    List.iter (fun (c, code) ->
      Printf.printf "  '%c' (freq=%d): %s\n" c
        (List.assoc c freqs) code
    ) codes

Key Differences

Aspect	Rust	OCaml
Sort key	`sort_by_key(\|&(_, end)\| end)`	`List.sort` with comparison fn
Initialization	`i32::MIN`	`Int.min_int`
Accumulation	`mut last_end` + push	`fold_left` with acc tuple
Fractional knapsack	Sort by `v/w` with `f64`	Same with `float`
Correctness proof	Exchange argument	Same mathematical argument
Failure cases	0/1 knapsack example	Same

OCaml Approach

OCaml's interval scheduling uses List.sort (fun (_, e1) (_, e2) -> compare e1 e2) then List.fold_left accumulating selected intervals. The greedy decision is if start >= last_end. OCaml's Int.min_int initializes last_end. The fractional knapsack sorts by ratio using List.sort and fills greedily with List.fold_left. OCaml's pattern destructuring let (start, end_) = interval reads naturally. The Printf module formats activity schedules for verification.

Full Source

#![allow(clippy::all)]
//! Placeholder

(* Greedy Algorithms: Activity Selection + Huffman Coding in OCaml *)

(* Activity Selection Problem *)
type activity = { id: int; start: int; finish: int }

(* Greedy: sort by finish time, pick non-overlapping activities *)
let activity_selection (activities : activity list) : activity list =
  let sorted = List.sort (fun a b -> compare a.finish b.finish) activities in
  let rec select last_finish = function
    | [] -> []
    | a :: rest ->
      if a.start >= last_finish then
        a :: select a.finish rest
      else
        select last_finish rest
  in
  select 0 sorted

(* Huffman Coding *)
type huffman =
  | Leaf of { symbol: char; freq: int }
  | Node of { freq: int; left: huffman; right: huffman }

let freq_of = function Leaf l -> l.freq | Node n -> n.freq

(* Simple priority queue using sorted list *)
let insert_sorted tree lst =
  let rec ins = function
    | [] -> [tree]
    | h :: t ->
      if freq_of tree <= freq_of h then tree :: h :: t
      else h :: ins t
  in
  ins lst

let huffman_tree (symbols : (char * int) list) : huffman option =
  match symbols with
  | [] -> None
  | _ ->
    let initial = List.sort (fun (_, a) (_, b) -> compare a b)
      (List.map (fun (c, f) -> Leaf { symbol=c; freq=f }) symbols)
    in
    let rec build = function
      | [tree] -> tree
      | a :: b :: rest ->
        let merged = Node { freq = freq_of a + freq_of b; left = a; right = b } in
        build (insert_sorted merged rest)
      | [] -> failwith "empty"
    in
    Some (build initial)

(* Extract code table: symbol -> binary string *)
let huffman_codes (tree : huffman) : (char * string) list =
  let codes = ref [] in
  let rec traverse prefix = function
    | Leaf l -> codes := (l.symbol, if prefix = "" then "0" else prefix) :: !codes
    | Node n ->
      traverse (prefix ^ "0") n.left;
      traverse (prefix ^ "1") n.right
  in
  traverse "" tree;
  List.sort compare !codes

let () =
  (* Activity selection *)
  let acts = [
    {id=1; start=1; finish=4};
    {id=2; start=3; finish=5};
    {id=3; start=0; finish=6};
    {id=4; start=5; finish=7};
    {id=5; start=3; finish=9};
    {id=6; start=5; finish=9};
    {id=7; start=6; finish=10};
    {id=8; start=8; finish=11};
    {id=9; start=8; finish=12};
    {id=10; start=2; finish=14};
  ] in
  let selected = activity_selection acts in
  Printf.printf "Activity selection: %d activities selected (ids: %s)\n"
    (List.length selected)
    (String.concat "," (List.map (fun a -> string_of_int a.id) selected));

  (* Huffman coding *)
  let freqs = [('a', 5); ('b', 2); ('c', 1); ('d', 3); ('e', 4); ('f', 7)] in
  match huffman_tree freqs with
  | None -> ()
  | Some tree ->
    let codes = huffman_codes tree in
    Printf.printf "\nHuffman codes:\n";
    List.iter (fun (c, code) ->
      Printf.printf "  '%c' (freq=%d): %s\n" c
        (List.assoc c freqs) code
    ) codes

Deep Comparison

OCaml vs Rust: Greedy Algorithm Patterns

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement a greedy coin change algorithm and show a denomination set where it fails to find the optimal solution.

Implement Huffman coding: build a frequency tree greedily using a min-heap, then assign binary codes.

Verify the interval scheduling result: write a checker that confirms no two selected intervals overlap.

Implement the activity selection with weighted jobs (maximize total weight, not count) and show greedy fails — requires DP.

Implement the job scheduling to minimize lateness: sort by deadline, prove exchange argument for correctness.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust