Randomized Algorithms

CS648

Lecture 1
An overview of the course

1
 Deterministic Algorithm

Input Output

Algorithm

The output as well as the running time are functions only of the input.

2
3
EXAMPLE 1 : APPROXIMATE MEDIAN

4
 Approximate Median
Problem :
Given an array A[] storing distinct numbers, compute the element with rank .

Best Deterministic Algorithm:

• “Median of Medians” algorithm
• Running time: O()
• Lower bound:
Reason: Every element must be read. Otherwise, …

The unread element could be the median element.

5
 Approximate Median
Definition:
Given an array A[] storing numbers and > ,
compute an element whose rank is in the range [( )/, ()/].

Best Deterministic Algorithm:

• Running time: O()
• No faster deterministic algorithm possible for approximate median 
Reason: At least elements must be read. Otherwise, …

½ - Approximate median elements could all be unread elements

6
 ½ - Approximate median

𝒏/ 𝟒 Elements of A arranged in 𝟑 𝒏/𝟒

Increasing order of values

Half of the elements are good candidates to be ½ - Approximate median

Idea  If we pick an element randomly uniformly,
it is going to be ½ - Approximate median for the array with probability at least .
O() time
A
in Output
On a few occasions
How to boost the success We shall revisit this
probability to be close to ? question later. 
7
EXAMPLE 2 : SORTING ALGORITHMS

8
 John von Neumann C. A. R. Hoare

Merge Sort, 1945 Quick Sort, 1960

Merge Sort Quick Sort

Average case comparisons 𝒏 𝐥𝐨𝐠𝟐 𝒏 1.39
Worst case comparisons
𝒏 𝐥𝐨𝐠𝟐 𝒏 𝒏(𝒏−𝟏)
9
 QuickSort()
When the input is stored in an array

QuickSort(,, )
{ If ( < )
 [];
 Partition(,,,x);
QuickSort(,, );
QuickSort(,, )
}

10
 A serious problem with QuickSort

QuickSort(,, )
{ If ( < )
 []; an element selected randomly uniformly from [..];
 Partition(,,,x);
QuickSort(,, );
QuickSort(,, )
}
• Distribution sensitive:
Time taken depends upon the initial permutation of .

Can we make QuickSort

distribution insensitive ?

11
 Randomized QuickSort()
When the input is stored in an array

QuickSort(,, )
{ If ( < )
 []; an element selected randomly uniformly from [..];
 Partition(,,,x);
QuickSort(,, );
QuickSort(,, )
}
• Distribution insensitive: Time taken does not depend on initial permutation of .
• Time taken depends upon the random choices of pivot elements.

12
 Deterministic Algorithm

Input Output

Algorithm

The output as well as the running time are functions only of the input.

13
 Deterministic
Randomized Algorithm

Random bits

Input Output

Algorithm

The output as well as the running time are functions of the input and random bits chosen.

or
in Output
Excess running time On a few occasions
14
on a few occasions
 Still why to study
Randomized Algorithms ?

………. Efficiency
Deterministic algo.

Simplicity

15
 Quick sort popular ?
What makes Randomized Algorithms

Homework: Keep pondering over this question.

We shall answer this question in 2 weeks from now .

 Types of Randomized Algorithms

Randomized Las Vegas Algorithms:

• Output is always correct
• Running time is a random variable
Example: Randomized Quick Sort

Randomized Monte Carlo Algorithms:

• Output may be incorrect with some probability
• Running time is deterministic.
Example: Randomized algorithm for approximate median

17
10 MOTIVATING EXAMPLES FOR
RANDOMIZED ALGORITHMS

Interested in practical aspects only

Interested in theoretical aspects only

Interested in practical as well as theoretical aspects

18
 Example 1: Exact Median

Theorem**: Every deterministic algorithm for exact median

must perform at least comparisons in the worst case.

Theorem: There is a randomized Las Vegas algorithm that computes exact median
and performs only comparisons on expectation.

**Dorit Dor, Uri Zwick:

On Lower Bounds for Selecting the Median.
SIAM J. Discrete Math. 14(3): 312-325 (2001)

19
 Example 2: Smallest Enclosing circle
• There are points in plane.
• We select a random sample of points.

Let C be the smallest enclosing circle of sampled points.

What is the worst case no. of unsampled points lying outside C ? 𝑛/ 2
What is the expected no. of unsampled points lying outside C ? <

20
 Example 2: Smallest Enclosing circle
Problem definition: Given points in a plane,
compute the smallest radius circle that encloses all point.

Simple exercise : O()

Applications: Facility location problem

Best deterministic algorithm : [Megiddo, 1983]
• O() time complexity, too complex, uses advanced geometry
Randomized Las Vegas algorithm: [Welzl, 1991]
• Average O() time complexity, too simple, uses elementary geometry

21
 Example 3: minimum Cut
Problem definition: Given a connected graph G=(V,E) on n vertices and m edges,
compute the smallest set of edges whose removal will make G disconnected.

Deterministic algorithm : [Stoer and Wagner, 1997]

• O() time complexity.
Randomized Monte Carlo algorithm: [Karger, 1993]
• O( log ) time complexity.
• Error probability: for any that we desire
Deterministic algorithm: [Thorup and Kawarabayashi, 2015]
• O() time complexity.
22
 Example 4:
Primality Testing
Problem definition: Given an bit integer, determine if it is prime.
Applications:
• RSA-cryptosystem,
• Algebraic algorithms

Best deterministic algorithm : [Agrawal, Kayal and Saxena, 2002]

• O( ) time complexity.
Randomized Monte Carlo algorithm: [Rabin, 1980]
• O( ) time complexity.
• Error probability: for any that we desire

For = , this probability is

23
 Example 5:
Small world phenomenon
Any two persons in the world are connected by a chain of acquaintances.

24
 Example 6:
Generating a random structure
A fair coin  a random bit

1. Algorithm to generate a uniformly random number from []

time and random bits

2. Algorithm to generate a uniformly random permutation of objects.

time and random bits

3. Algorithm to generate a uniformly random spanning tree of a given graph ?

A polynomial time algorithm with polynomial number of random bits.

Ponder over these results, especially the last one.
25
 Example 7:
Hashing with worst case guarantee
• called universe
• and
•

Examples:
,
Aim
Build a data structure for a given to support the search query :
“Does ?” for any .
 Example 7:
Hashing with worst case guarantee
Query time Data structure Space

O()
Static O() Array
Makes use of
O() comparison
Dynamic O() Red-Black trees as the basic
operation
Dynamic O() Array
O() Impractical

Practical solution with no worst case guarantees

Makes use of fast
arithmietic operations
Hashing
on integers

ALU Few cycles for an arithmetic operation

 Example 8: All-Pairs Shortest Paths
Problem Definition: Given a graph , build a compact data structure
so that for any ,
• can be reported in time
• Shortest path from to can be reported in optimal time.

Results known:
• size data structure
(Distance matrix and Witness matrix)
• preprocessing time
(Dijkstra’s algorithm from each vertex)

Current-state-of-the-art RAM size: 8 GBs

Can’t handle graphs with even vertices (with RAM size) 

28
 All-Pairs Approximate Shortest Paths
Problem Definition: Given a graph , build a compact data structure
so that for any , it reports in time satisfying

: stretch.

Aim: To achieve
• Sub-quadratic space.
• Sub-cubic preprocessing time.
With query time.

Many elegant results have been invented for undirected graphs 

29
 A truly magical result

Approximate Distance Oracles

:Stretch Space Query time Preprocessing time

𝟏 𝟏
𝟑 𝑶 (𝒏
𝟏+
𝟐
) 𝑶 (𝟏) 𝑶 (𝒎𝒏 ) 𝟐

𝟏 𝟏
𝟓 𝑶 (𝒏
𝟏+
𝟑
)
𝑶 (𝟏) 𝑶 (𝒎𝒏 ) 𝟑

𝟏 𝟏
𝟐 𝒌 −𝟏 𝑶 (𝒏
𝟏+
𝒌
) 𝑶 (𝒌) 𝑶 (𝒌 𝒎𝒏 ) 𝒌

Mikkel Thorup and Uri Zwick:

Approximate Distance Oracles for graphs,
Journal of ACM (4), 2005

30
 Example 9:
Random walk and Electric networks

The expected number of steps to reach banana ? 𝑶 (𝒏𝒅) 31

 Example 9:
Random walk and Electric networks
Theorem:
Given an undirected graph on edges,
commute time between any pair of vertices and is ,
where is the effective resistance between and in the circuit
associated with .

Important lesson:
It is always good to know the fundamentals of other disciplines.
There are no boundaries defined in science .

32
 Example 10:
Rumor Spreading

Town with persons.

On day 1, one person knows the rumor.
Rumor spreads …

``Every morning, each person who knows the rumor calls a random person
and communicates the rumor to him/her.’’

How many days till the rumor spreads to the entire town ?

days with high probability

33
 Prerequisites for the course
Elementary knowledge of probability

Formal analysis

Basic knowledge of Data structures and algorithms Formal proof of

correctness

Basic algorithm
Ability to work very hard
paradigms

Commitment to attend all classes

unless you have any genuine personal/medical problem

35
 Course website

moodle.cse.iitk.ac.in

Use guest login.

36