Welcome to CS166!
Course information handout available up
front.
Today:
Course overview.
Why study data structures?
The range minimum query problem.
Course Staff
Keith Schwarz (htiek@cs.stanford.edu)
Kyle Brogle (broglek@stanford.edu)
Daniel Hollingshead (dhollingshead@stanford.edu)
Nick Isaacs (nisaacs@stanford.edu)
Aparna Krishnan (aparnak@stanford.edu)
Sen Wu (senwu@stanford.edu)
Course Staff Mailing List:
cs166-spr1314-staff@lists.stanford.edu
The Course Website
http://cs166.stanford.edu
Required Reading
Introduction to
Algorithms, Third
Edition by Cormen,
Leiserson, Rivest, and
Stein.
You'll want the third
edition for this
course.
Available in the
bookstore; several
copies on hold at the
Engineering Library.
Prerequisites
CS161 (Design and Analysis of Algorithms)
CS107 (Computer Organization and Systems)
We'll assume familiarity with asymptotic notation,
correctness proofs, algorithmic strategies (e.g.
divide-and-conquer), classical algorithms,
recurrence relations, etc.
We'll assume comfort working from the
command-line, designing and testing nontrivial
programs, and manipulating bitwise representations
of data. You should have some knowledge of the
memory hierarchy.
Not sure whether you're in the right place? Please feel
free to ask!
Grading Policies
Grading Policies
50% Assignments
25% Midterm
25% Final Project
Axess: Enrollment Limited
Because this is a new course, we're limiting
enrollment in CS166 to 100.
If you are interested in taking the course, please
sign up on Axess as soon as possible so that we
can get an approximate headcount.
If enrollment is under 100, then everything will
work as a normal course.
If enrollment exceeds 100, we'll send out an
application. Sorry for the inconvenience!
Why Study Data Structures?
Why Study Data Structures?
Explore the intersection between
theory and practice.
Learn new approaches to modeling
and solving problems.
Expand your sense of what can be
done efficiently.
Range Minimum Queries
The RMQ Problem
The Range Minimum Query (RMQ)
problem is the following:
Given a fixed array A and two indices
ij, what is the smallest element out of
A[i], A[i + 1], , A[j 1], A[j]?
31
41
59
26
53
58
97
93
A Trivial Solution
There's a simple O(n)-time algorithm for
evaluating RMQA(i, j): just iterate across the
elements between i and j, inclusive, and take
the minimum!
Why is this problem at all algorithmically
interesting?
Suppose that the array A is fixed and we'll
make k queries on it.
Can we do better than the nave algorithm?
An Observation
In an array of length n, there are only (n2) possible
queries.
Why?
1 subarray of
length 5
2 subarrays of
length 4
3 subarrays of
length 3
4 subarrays of
length 2
5 subarrays of
length 1
A Different Approach
There are only (n2) possible RMQs in an array of
length n.
If we precompute all of them, we can answer RMQ in
time O(1) per query.
0
1
16
0
18
1
33
2
98
3
2
3
18
Building the Table
One simple approach: for each entry in
the table, iterate over the range in
question and find the minimum value.
How efficient is this?
Number of entries: (n2).
Time to evaluate each entry: O(n).
Time required: O(n3).
The runtime is O(n3) using this approach.
Is it also (n3)?
0
1
2
3
4
5
6
7
Each
Eachentry
entryin
inyellow
yellowrequires
requiresat
at
least
leastnn/ /22==(n)
(n)work
workto
toevaluate.
evaluate.
2
2
There
are
roughly
n
2/ 8 = (n )
There are roughly n / 8 = (n2)
entries
entrieshere.
here.
3
Total
work
required:
(n
Total work required: (n)3)
A Different Approach
Navely precomputing the table is inefficient.
Can we do better?
Claim: Can precompute all subarrays in time (n2)
using dynamic programming.
0
0
16
0
18
1
33
2
98
3
16 16 16
18 18 18
33 33
98
Some Notation
We'll say that an RMQ data structure has time
complexity p(n),q(n) if
preprocessing takes time at most p(n) and
queries take time at most q(n).
We now have two RMQ data structures:
O(1), O(n) with no preprocessing.
O(n2), O(1) with full preprocessing.
These are two extremes on a curve of tradeoffs:
no preprocessing versus full preprocessing.
Question: Is there a golden mean between
these extremes?
Another Approach: Block Decomposition
A Block-Based Approach
Split the input into O(n / b) blocks of
some block size b.
31
Here, b = 3.
Compute the minimum value in each
block.
31
41
59
26
26
53
58
97
23
93
23
84
62
62
64
33
27
83
27
Analyzing the Approach
Let's analyze this approach in terms of n and b.
Preprocessing time:
31
O(b) work on O(n / b) blocks to find minimums.
Total work: O(n).
Time to query RMQA(i, j):
O(1) work to find block indices (divide by block size).
O(b) work to scan inside i and j's blocks.
O(n / b) work looking at block minimums between i and j.
Total work: O(b + n / b).
31
41
59
26
26
53
58
97
23
93
23
84
62
62
64
33
27
83
27
Intuiting O(b + n / b)
As b increases:
The n / b term drops (fewer blocks to look at).
As b decreases:
The b term rises (more elements to scan within
each block).
The b term drops (fewer elements to scan within
a block).
The n / b term rises (more blocks to look at).
Is there an optimal choice of b given these
constraints?
Optimizing b
What choice of b minimizes b + n / b?
Start by taking the derivative:
d
n
(b+n/b) = 1 2
db
b
Setting the derivative to zero:
1n/b2 =
0
1
= n/b2
b2
=
n
b
= n
Asymptotically optimal runtime is when b = n1/2.
In that case, the runtime is
O(b + n / b) = O(n1/2 + n / n1/2) = O(n1/2 + n1/2) = O(n1/2)
Summary of Approaches
Three solutions so far:
No preprocessing: O(1), O(n).
Full preprocessing: O(n2), O(1).
Block partition: O(n), O(n1/2).
Modest preprocessing yields modest
performance increases.
Question: Can we do better?
A Second Approach: Sparse Tables
An Intuition
The O(n2), O(1) solution gives fast
queries because every range we might
look up has already been precomputed.
This solution is slow overall because we
have to compute the minimum of every
possible range.
Question: Can we still get O(1) queries
without preprocessing all possible
ranges?
An Observation
0
0 31 31 31 26
1
2
41 41 26 26
59 26 26 26
31 41 59 26 53 58 97 93
53 53 53 53
58 58 58
97 93
93
5 6
26 26 26 26
The Intuition
It's still possible to answer any query in time O(1)
without precomputing RMQ over all ranges.
If we precompute the answers over too many
ranges, the preprocessing time will be too large.
If we precompute the answers over too few ranges,
the query time won't be O(1).
Goal: Precompute RMQ over a set of ranges such
that
There are o(n2) total ranges, but
there are enough ranges to support O(1) query
times.
Some Observations
The Approach
For each index i, compute RMQ for ranges
starting at i of size 1, 2, 4, 8, 16, , 2k as long
as they fit in the array.
Gives both large and small ranges starting at
any point in the array.
Only O(log n) ranges computed for each array
element.
Total number of ranges: O(n log n).
Claim: Any range in the array can be formed
as the union of two of these ranges.
Creating Ranges
18
16
16
Creating Ranges
4
4
Doing a Query
To answer RMQA(i, j):
Find the largest k such that 2k j i + 1.
With the right preprocessing, this can be done in
time O(1); you'll figure out how in the problem
set!
The range [i, j] can be formed as the overlap
of the ranges [i, i + 2k 1] and [j 2k + 1, j].
Each range can be looked up in time O(1).
Total time: O(1).
Precomputing the Ranges
There are O(n log n) ranges to precompute.
Using dynamic programming, we can compute
all of them in time O(n log n).
31 41 59 26 53 58 97 93
0
0
1
2
3
4
5
6
7
20
21
22
31
41
59
26
53
58
97
93
31
41
26
26
53
58
93
23
Sparse Tables
This data structure is called a sparse
table.
Gives an O(n log n), O(1) solution to
RMQ.
Asymptotically better than precomputing
all possible ranges!
The Story So Far
We now have the following solutions for
RMQ:
Precompute all: O(n2), O(1).
Precompute none: O(1), O(n).
Blocking: O(n), O(n1/2).
Sparse table: O(n log n), O(1).
Can we do better?
A Third Approach: Hybrid Strategies
Blocking Revisited
31
31
41
59
26
26
53
58
97
23
93
23
84
62
62
64
33
27
83
27
Blocking Revisited
This
Thisisisjust
justRMQ
RMQon
on
the
theblock
blockminimums!
minimums!
31
31
41
59
26
26
53
58
97
23
93
23
84
62
62
64
33
27
83
27
Blocking Revisited
31
31
41
59
26
26
53
58
97
23
93
23
84
This
Thisisisjust
justRMQ
RMQ
inside
insidethe
theblocks!
blocks!
62
62
64
33
27
83
27
The Setup
Here's a new possible route for solving RMQ:
Split the input into blocks of some block size b.
For each of the O(n / b) blocks, compute the
minimum.
Construct an RMQ structure on the block
minimums.
Construct RMQ structures on each block.
Combine the RMQ answers to solve RMQ overall.
This approach of segmenting a structure into a
high-level structure and many low-level structures
is sometimes called a macro/micro
decomposition.
Combinations and Permutations
The macro/micro decomposition isn't a single
data structure; it's a framework for data
structures.
We get to choose
the block size,
which RMQ structure to use on top, and
which RMQ structure to use for the blocks.
Summary and block RMQ structures don't have
to be the same type of RMQ data structure we
can combine different structures together to
get different results.
The Framework
Suppose we use a p(n), q(n)-time RMQ solution
for the block minimums and a p(n),q(n)-time
RMQ solution within each block.
Let the block size be b.
In the hybrid structure, the preprocessing time is
O(n + p(n / b) + (n / b) p(b))
The query time is
O(q(n / b) + q(b))
31
31
41
59
26
26
53
58
97
23
93
23
84
62
62
64
33
27
83
27
A Sanity Check
The O(n), O(n1/2) block-based structure from earlier uses
this framework with the O(1), O(n) no-preprocessing
RMQ structure and b = n1/2.
According to our formulas, the preprocessing time should
be
=
=
=
= O(n + p(n / b) + (n / b) p(b))
= O(n + 1 + n / b)
== O(n)
For
ForReference
Reference
The query time should be
p(n)
==11
p(n)
=
== O(q(n / b) + q(b))
q(n)
==nn
q(n)
=
== O(n / b + b)
p(n)
=
== O(n1/2)
p(n)==11
q(n)
q(n)==nn
Looks good so far!
bb==nn1/2
1/2
An Observation
A sparse table takes time O(n log n) to construct
on an array of n elements.
With block size b, there are O(n / b) total blocks.
Time to construct a sparse table over the block
minimums: O((n / b) log (n / b)).
Since log (n / b) = O(log n), the time to build the
sparse table is at most O((n / b) log n).
Cute trick: If b = (log n), the time to construct a
sparse table over the minimums is
O((n / b) log n) = O((n / log n) log n) = O(n)
One Possible Hybrid
Set the block size to log n.
Use a sparse table for the top-level structure.
Use the no preprocessing structure for each block.
Preprocessing time:
= O(n + p(n / b) + (n / b) p(b))
= O(n + n + n / log n)
For
= O(n)
ForReference
Reference
p(n)
Query time:
p(n)==nnlog
lognn
q(n)
==11
q(n)
= O(q(n / b) + q(b))
p(n)
= O(1 + log n)
p(n)==11
q(n)
= O(log n)
q(n)==nn
bb==log
An O(n), O(log n) solution!
lognn
Another Hybrid
Let's suppose we use the O(n log n), O(1) sparse table
for both the top and bottom RMQ structures with a
block size of log n.
The preprocessing time is
=
=
=
=
O(n + p(n / b) + (n / b) p(b))
O(n + n + (n / log n) b log b)
O(n + (n / log n) log n log log n)
O(n log log n)
For
ForReference
Reference
The query time is
p(n)
p(n)==nnlog
lognn
q(n)
= O(q(n / b) + q(b))
q(n)==11
= O(1)
p(n)
p(n)==nnlog
lognn
q(n)
We have an O(n log log n), O(1)
q(n)==11
solution to RMQ!
bb==log
lognn
One Last Hybrid
Suppose we use a sparse table for the top structure
and the O(n), O(log n) solution for the bottom
structure. Let's choose b = log n.
The preprocessing time is
=
=
=
=
O(n + p(n / b) + (n / b) p(b))
O(n + n + (n / log n) b)
O(n + n + (n / log n) log n)
O(n)
For
ForReference
Reference
The query time is
p(n)
p(n)==nnlog
lognn
q(n)
= O(q(n / b) + q(b))
q(n)==11
= O(1 + log log n)
p(n)
==nn
p(n)
= O(log log n)
q(n)
q(n)==log
lognn
We have an O(n), O(log log n)
bb==log
nn
log
solution to RMQ!
Where We Stand
We've seen a bunch of RMQ structures
today:
No preprocessing: O(1), O(n)
Full preprocessing: O(n2), O(1)
Block partition: O(n), O(n1/2)
Sparse table: O(n log n), O(1)
Hybrid 1: O(n), O(log n)
Hybrid 2: O(n log log n), O(1)
Hybrid 3: O(n), O(log log n)
Is there an O(n), O(1) solution to RMQ?
Yes!
Next Time
Cartesian Trees
The Method of Four Russians
A data structure closely related to RMQ.
A technique for shaving off log factors.
The Fischer-Heun Structure
A deceptively simple, asymptotically optimal
RMQ structure.
