Approximation — provably close to optimal

An approximation algorithm trades exactness for speed — with a number attached to how much you sacrificed.

1. 01
   The classic 2-approximation for vertex cover: pick any uncovered edge, add both endpoints, repeat. Twenty lines, formal guarantee of at most twice the optimal cover size. Faster than the ILP from page 27 — use it when 2× is good enough.

   use std::collections::HashSet;
   
   fn vertex_cover_2approx(n: usize, edges: &[(usize, usize)]) -> HashSet<usize> {
       let mut covered = vec![false; edges.len()];
       let mut cover = HashSet::new();
       for (i, &(u, v)) in edges.iter().enumerate() {
           if covered[i] { continue; }
           cover.insert(u);
           cover.insert(v);
           let _ = n; // unused; kept for signature parity
           for (j, &(a, b)) in edges.iter().enumerate() {
               if cover.contains(&a) || cover.contains(&b) { covered[j] = true; }
           }
       }
       cover
   }

2. 02
   .enumerate() is an iterator combinator that pairs every element with its 0-based index, yielding (usize, item) tuples. Same idea as Python's enumerate(list) or JavaScript's Array.prototype.entries(). Page 33 uses it twice — both times to walk the edges while keeping the index handy for indexing into the covered boolean array. The double destructuring (i, &(u, v)) unpacks both layers in one step: the outer tuple is the (index, &edge) pair from enumerate, and the inner &(u, v) reaches past the reference to copy the two usize endpoints (the same Copy trick from page 15). After binding, i is the edge index, u and v are the endpoints — clean to use, no * dereferences needed in the body.

   // .enumerate() — pair each element with its 0-based index.
   let names = ["Alice", "Bob", "Carol"];
   
   for (i, name) in names.iter().enumerate() {
       println!("{}: {}", i, name);
   }
   // 0: Alice
   // 1: Bob
   // 2: Carol
   
   
   // Page 33's pattern — destructure index AND inner tuple values at once:
   for (i, &(u, v)) in edges.iter().enumerate() {
   //   ─  ──────
   //   │      │
   //   │      └── &(u, v): reach past the reference and copy out the
   //   │           two usize values (Copy trick from page 15)
   //   └──────── i: the index, usize, from enumerate()
       if covered[i] { continue; }
       cover.insert(u);
       cover.insert(v);
       // ...
   }
   
   
   // Equivalent without enumerate — index-heavy, more typing:
   for i in 0..edges.len() {
       if covered[i] { continue; }
       let (u, v) = edges[i];               // separate indexing step
       cover.insert(u);
       cover.insert(v);
   }
   
   
   // .enumerate() chains with other combinators — works on any iterator:
   let scores = vec![85, 92, 78, 95];
   
   let above_80: Vec<usize> = scores
       .iter()
       .enumerate()
       .filter(|(_, &s)| s > 80)
       .map(|(i, _)| i)
       .collect();
   // = [0, 1, 3]    — indices of scores above 80
   
   
   // Note the order: (index, item).  Same convention as Python's enumerate.
   //
   // Family of "yield more info with each element" combinators:
   //   .enumerate()         (index, item) pairs
   //   .zip(other)          (item, other_item) pairs        (page 32)
   //   .peekable()          .peek() looks at the next item without consuming it
   //   .step_by(n)          take every nth element