Monte Carlo

the time is given (it will run always the same amount of time = constant runtime) and the result is random

maximizes the number of satisfied clauses
- randomly set each variable to 0 or 1 with 50 % probability and see what is the result (= how many clauses are satisfied)
the longer you’re running, more likely you will find better solution
- if there is no solution, it will be running forever

randomly selecting $k$ and verifying the equations (based on Little Fermat’s Theorem)
- $k^{n - 1} \equiv 1 mod n$
the longer it runs (the higher number of generated $k$ is) the smaller is the chance of being non-prime
- after 100 numbers the probability is really small (BUT it is not proven)
a lot of randomized algorithms consists of two phases
- a randomized phase = constructive
- a deterministic phase = iterative
- for example: Randomized SAT, GSAT, Random Walk SAT etc.
  - random selecting and deterministic iterating (if better configuration is found)

Las Vegas

the result will always be optimum, the runtime is random variable (it may run random time)

the result is always the optimum (=sorted array)
with random pivot selecting, there cannot be “artificially” crafted inputs for which the pivot will for sure fail (as in the normal quick-sorts, where the pivot is selected in a deterministic way)
it is proven that the average complexity is $O (n l o g (n))$
- it is almost impossible to find an example with $O (n^{2})$ complexity for a randomized quicksort

randomness from outside, randomness “noise” etc.
- example of a Knapsack
  - if I permute the order of the inputs, we can get different (“random”) results from a deterministic algorithm
- it has a lot of other examples
  - change of procedure (different language constructs doing the same thing) or inputs (different ordering, encoding, identifiers etc.) can lead to different results (or different time etc.)
there is a run-time vs. quality trade-off
- the longer it runs, the better results we may get

process of taking a random algorithm and creating a deterministic algorithm derived from it
for every randomized algortihm you can define a deterministic algorithm doing the same
- the randomized algos are not computationally better than deterministic ones (but they can be, for example, way faster than deterministic ones)

testing algorithms experimentally
the form of the experiment
- question → running the experiment → evaluating/interpreting the results
notes:
- random clones = randomly generated inputs that have similar/some properties of the practical instances (used in practice)