CS 341 Lecture 10 1 Constructing Optimum Binary Search trees
Given items 1..n and probabPilities-p1..pn, construct a binary search tree to minimize the search cost i pi ProbeDepth(i).
e.g.,p =···=p =1
1 5 5 # probes into tree
to find item i searchcost=1·1 +2·2·1 +2·O3·1 =7
tdepth
# modest e.g.,p1 =.6 p2 =p3+p4 =p5 =.1
cost = O1(.1) + 2 ·O2(.1)+ 3(.6) + 3(.1)
cost =O1(.6) + 2 ·O2(.1)+ 2 ·O3(.1) +O4(.1)
= 1.8
O
O
= 2.6
To apply dynamic programming:
• subproblems: optimal binary search tree for items i..j
• order subproblems by # items (i.e., by j i) to solve i..j
OO
5555
CS 341 Lecture 10
Details j ←
independent o f choice of K
2
M[i,j]= min{M[i,k 1]+M[k+1,j]}-
k=1..j
X
Pj
t=i i
because
Ppt
thenwecanget jt=ipt asP[j] P[i 1].
How to compute
First compute PP[i] = j=1 pj P[0] = 0
every
for ifrom 1to ndo M[i,i] := pi
M [i, i 1] := 0 od
for dfrom 1to n 1do for i from 1 to n d
a
od
# solve for M [i, i + d]
best := 1 # or a very large number for k from i to i + d do
temp := M [i, k 1] + M [k + 1, i + d]
if temp < best then best := temp fi; od
M[i,i+d]:=best+P[i+d] P[i 1] # subproblems od ✓
2 H2er Runtime O(n · n) = O(n )
#disj iinabove
\
tim e per subproblem
+p t=i
t
node gets 1 deeper
Dynamic
Recall the kna
Given ite
a su
Recall that
where
(e.g., flashlig
First attempt:
• if n
• if n
62 S
2S
Prog
bset S
ms
we
greedy algo
ht,
ramming for 0-1
psa
ck problem:
1, 2, ..., n,
of items
onsid
tent).
Like
— look f
— wan
weight
such
ered the
rithm works
or op
t sub
set
where
that
fr
.
K
ed interval s
tim
S
al s
of
napsack
item
Pi2S wi actional
Here
i
CS 341
has
cheduling,
olution for 1..
1.
.n
Xi2S
1
wit
w
Lecture
weig
version (
we consider
i
h
n
10
ht wi and
W
→ capa
-
W
and Pi2S
city of knaps
use fractions
can
the
d
0-1 version
istinguish
1
wn the
value vi
vi i
s
2
maximized.
whether
left
in
the
(wi
,vi
item
n
Z)
is I
c
N
hoose
o
rO
U
T.
3
ac
k
c
of items, e.g.,
where items
are
fl
our, rice)
indivisible
knaps
ack
a
subproblem
with
space
) we must solve
di↵erent weigh
t cap
acity
Subproblems: one for each pair i, w, Find subset S ✓ {1..i} s.t.
-
and
i2S vi.
•ifwi >wthenM(i,⇢w):=M(i 1,w)
*
Let M(i, w) = max To find M(i,w)
^
I
#
PX
X
i2S
wi w i2S
•elseM(i,w):=max M(i 1,w) #don’tusei vi+M(i 1,w wi) #usei
Pseudocode and ordering of subproblems: UsematrixM[0..n,0..W]
Initialize M [0, w] := 0 for w = 0..W for ifrom 1to ndo
m
subproblems
mirrork per sub problem
for w from 0 to W do compute M[i,w] using
od od
*
This is not a polynomial time algorithm. It is pseudo-polynomial time. The input is w1..wn, v1..vn, W. The size of the input is sum of # bits.
CS 341 Lecture 10
w = 0..W special order
4
i = 0..n,
note : n o
of items
vi is maximized
Analysis:n·W·c→ constantworkfor*
↳
SoO(n·W)
→ loopfor loopfor i
w
W
say it
But
Runti
is one
h
Finding the actua
1. Backtracking:
i
:=
whi
o
is
if
f the
as k bits
the algorith
m
e
numbers in
2 ⇥(log m takes
:k
polynomial
n
;w
le i >
M(i,w)
:=
l so
0
W;
do
=
in the
lution for kna
Use M to
S := ;
M(i
the
W).
O(n·W
inpu
)
value of
recove
1,w)
t.
CS 341
The
— that’s O(n ·
W
r solution
#
Lecture
size of
rather
didn’t use
10
tha
the inputs counts the
2k)
i
n
so
the s
it’s
iz
expo
e
of W
nential
.
si
ze of
in the
W
— let’s
input size.
5
psa
ck.
Two
methods:
2. Enhance
Tr
ade
— lis
-o↵s:
el
i
se
S
t
:= i #
:=
original code:
— do we use item i or
Or even store
of ite
(2) uses
(1)
1
u
S [ {i}
Soln(
m
s
sed
i,
to get
i
o
w)
more space
duplicates tests us
i
when
:=i-
not to
M (i,
l
we set
w
)
get M
ed to
(no
c
:=w
M (i,
w
(i, w) (we
backtracking
ompute M
i
od
fi
,
w
–
w)
also se
n
t
Flag(i,
still need
eed
ed)
w)
backtrac
king)
;
Memoization:
• use
doing
• danger time,
• fix — yo
Exa
fib
end
u
• advantage
• disa
recur
so fa
have
m
end
proc
dva
– harder to
– overhead
sion,
— that
e.g., T (n)
when
a
r.
stored
rather
y
ou solve th
= 2T(n
you solve
ple: “option remember”
:= proc(n)
option remember;
if n
elif
else
=0
if
ntages
n=
return
— mayb
a
nalyze
of recu
than
a
1)
solution. Solutio
then
1 then
e
return
fib(n
you do
runti
rsive
e
subp
m
xplicitly
e same
n’t
e
+
in
return 1
–
O(
roblem
0
1) +
solve
approach takes
CS 341
1) i
, st
ns ca
Maple
s
Lecture
solving all su
subproblem
exp
ore
n
fib(n –
all
be
10
onential.)
the solu
st
subproblems.
more time
bpr
over and over
oblems
tions.
ored in a matrix
2)
B
ef
bott
ore
or i
om-u
p
(possibly taking exponential
h
as we’ve been
(re)-solving, check
n
a
ash
table.
6
if
CS 341 Lecture 10 7 Common subarpproblems in dynamic programming
1. input x1..xn subproblems x1..xi
# subproblems n
2. input x1..xn subproblems xi..xj
# subproblems O(n2)
weighted
interval scheduling
optimal binary search tre e
3. input x1..xn y1..ym subproblems x1..xi and y1..yj # subproblems O(nm)
e d it distance