Chapter 19: Randomized and Approximate Algorithms. 25 sections.
25 items
Randomized algorithms differ from deterministic algorithms because their behavior depends on random choices made during execution.
A randomized algorithm can use randomness in several ways.
Las Vegas algorithms always return correct answers and use randomness to influence resource consumption.
Randomized quicksort is one of the most successful applications of randomization in algorithm design.
Random sampling is one of the most powerful techniques in algorithm design.
Shuffling converts an ordered collection into a uniformly random permutation.
Balanced search trees achieve logarithmic performance by carefully maintaining structural invariants.
Hash tables are usually presented as deterministic data structures: compute a hash, reduce it to a table index, and store or retrieve the key.
Many large-scale systems need to compare sets.
HyperLogLog estimates the number of distinct elements in a stream using a small, fixed amount of memory.
A Bloom filter is one of the most widely deployed probabilistic data structures in modern computing.
A Count-Min Sketch estimates item frequencies in a stream using fixed memory.
Many applications need to find similar items inside very large collections.
Some optimization problems are easy to state and hard to solve exactly.
Many approximation algorithms are built around a simple principle: make the best local decision available at each step.
Set Cover is the canonical greedy approximation problem.
Many optimization problems can be expressed as integer programs.
Primal-dual approximation algorithms use linear programming structure to design fast approximate solutions.
Most algorithms assume complete knowledge of the input before computation begins.
Streaming algorithms process data one item at a time while using much less memory than the input size.
Throughout this chapter, we have encountered a recurring theme: ```text A small amount of randomness can dramatically simplify
Randomized algorithms rarely stop at computing an expected value.
Randomized algorithms are often easier to design and analyze than deterministic algorithms.
Theoretical analysis explains why randomized algorithms work.
Randomized algorithms span a wide range of techniques.