Randomized Algorithms

Intro

Want to solve NPC problems in P? Well we can! (with a small margin of error)

Applications

Google Maps (travelling salesman), etc

Example

Randomized Algorithm for 3-SAT

Let $y_i = \begin{cases} 1, & if \; clause_i \text{ is true} \\ 0, & otherwise \end{cases}$

#clauses = $m$

Each clause has $k$ literals

$\begin{aligned} E[\sum_{i=1}^m{y_i}] & = \sum_{i=1}^m{E[y_i]} \quad \text{linearity of expectation} \\ & = \sum_{i=1}^m{Pr[y_i==1]} \quad \text{see note} \\ & = \sum_{i=1}^m{[1 - (\frac{1}{2})^k]} \\ & = m \times [1 - (\frac{1}{2})^k] \end{aligned}$

Note: Since $y_i = \{0, 1\}$, $E[y_i] = y_i * Pr[y_i] = 1 * Pr[y_i==1]$.