"No more than 1/5 of the population can have more than 5 times the average income."
Proof by Picture! :-)
Proof by Algebra:
Idea: Apply Markov's Inequality to RV , since .
Example:
Consider the following coin flipping games
Let's compute expected value of winnings :
Proof:
Proof:
Proof:
General Properties:
General Properties:
Main Idea:
Input: Unsorted array of integers;
Output: median of
Find and such that:
Proof:
Time Complexity:
Correctness:
Proof:
Proof:
Proof:
Can we make this a Las Vegas algorithm?
What's the probability of seeing more than heads?
Can we get even closer to the mean?
qsort(array):
if length(array) ≤ 1 then
return array
else
pivot = array[random(0..length(array))]
less_or_eq = [ x <- array | x ≤ pivot ]
greater = [ x <- array | x > pivot ]
qsort(less_or_eq) ++ [pivot] ++ qsort(greater)
Proof:
"What fraction of CAS alumni like Haskell?"
Properties
Proof:
Proof:
Proof:
Example
KeysPerformance is proportional to height of tree!
Example: Red-Black Tree
Rebalancing Red-Black Tree
One-Shot Construction
Example: Skip List of keys
Suppose we search for key :
Remarks:
Performance:
Search for key :
Same as for Deterministic Skip lists - start at top-left and traverse zigzag-style
Construction - one element at a time:
Suppose we want to insert key :
Deletion:
Suppose we want to delete key :
Proof:
Proof:
Proof:
We've shown:
Proof: