Distinguish approximate answers from randomized execution
Approximation algorithms return a feasible answer with a bound relative to the optimum for a defined problem. Randomized algorithms use randomness in their execution; they may still always return an exact answer.
Randomized quicksort is a Las Vegas-style example: sorting remains correct, while running time varies with random choices. A hash-only equality check without verification is Monte Carlo-style: fast behavior may come with a probability of error. These categories describe different guarantees.
For unweighted vertex cover, repeatedly choose an uncovered edge and select both endpoints. The chosen edges form a matching, so any cover needs at least one endpoint per chosen edge. The algorithm selects two, giving a factor-two bound. This reasoning does not automatically extend to weighted vertices.
Exercise
Implement the vertex-cover approximation and compare its size with an exhaustive optimum on small graphs. Validate that every edge is covered before evaluating the ratio. For randomized quicksort, record seeds to reproduce performance anomalies.
Check: report the guarantee you actually have: exactness, approximation factor, expected runtime, or error probability. “Random” does not mean “approximately correct.”