ECS122B-L14

📗 -> 02/24/26: ECS122B-L14

---

[Lecture Slide Link]

🎤 Vocab

❗ Unit and Larger Context

Small summary

✒️ -> Scratch Notes

Deterministic vs Randomized

• Randomized - Different outcomes as a result of reliance on randomization
  • Complexity on the algorithm’s expected performance
  • Randomized Quicksort
• Deterministic - Same output for given input
  • Complexity on the worst case analysis
  • Deterministic Quicksort

Categories of Randomization

• Las Vegas
• Monte Carlo

Monte Carlo

• Fixed Speed (the time it takes is predictable)
• Random Correctness (subject to probability)
  • Prime Detection algorithm: Might say number is prime with 99.9% certainty
    • Randomness comes from sampling large search space

Las Vegas

• Guaranteed Correctness (the answer is always 100% correct)
• Random Speed (the randomness only affects the cost)
  • It may take 1 second today and 1 hour tomorrow on the same data.
• Example: Randomized Quick Sort

🔗 -> Links

Resources

• Put useful links here

Connections

• Link all related words