Randomized Algorithms

Probabilistic Analysis of Deterministic Algorithms

Algorithm Insertion Sort

Insertionsort (A)
for j = 2 to A.length
	key = A[j]
	i = j-1
	while i > 0 and A[i] > key
		A[i+1] = A[i]
		i = i - 1
	A[i+1] = key

Def Inversion An inversion is a permutation on an array of the form such that but . e.g. has 4 inversions Prop For an insertion sort, the best case has inversions, and the worst case has inversions.

Fact The goal of sorting is to remove inversions.

Prop In Insertion Sort, swapping a pair of numbers reduces the number of inversions by exactly .

Probabilistic Analysis of Randomized Algorithms

Def Randomized Algorithm A randomized algorithm is an algorithm whose behavior is determined not just by its input but also by random numbers. The behavior can vary even for the same input.

Algorithm Random Quick Sort

1. Pick a random element in the array.
2. Split the array into two sub-arrays, one containing elements smaller than the random element and one containing elements larger than that.
3. Do the above two steps recursively for each sub-array until the sub-arrays have only 1 element.

RandQuickSort (A, p, r)
	if p<r
		q = RandPartition(A, p, r) 
		RandQuickSort (A, p, q-1) 
		RandQuicksort (A, q+1, r)
	
RandPartition (A, p, r) 
	i =random(p, r)
	swap A[r] with A[i]
	return Partition(A, p, r)
	
Partition(A, p, r)
	x = A[r]
	i = p-1
	for j=p to r-1
		if A[j] <= x
			i = i+1
			swap A[i] with A[j]
	swap A[i+1] with A[r]
	return i+1

Randomized Algorithms

Fact

1. Computing matrix computation takes for a trivial algorithm. It can also be done in .
2. Computing matrix-vector computation takes for a trivial algorithm.

Algorithm Freivalds’s Algorithm Freivalds’s Algorithm is to verify the input matrices if they satisfy that .

1. Generate an random vector
2. Compute
3. Output Yes if is equal to zero and No otherwise Prop If , then the algorithm always returns Yes. If , then the probability it returns Yes is at most .

MAX-3-SAT

Def Boolean Variable A boolean variable is a variable that can take only the values True= or False=.

Def Negation The negation/NOT operator of a boolean variable is .

Def Literal and Clause A literal is a boolean variable or its negation. A clause is a disjunction of literals.

Def Conjunctive Normal Form A boolean formula is in Conjunctive Normal Form (CNF) if it is the conjunction of several clauses. It is called a CNF formula if all clauses contain literals.