程序代写代做代考 algorithm C CS 341 Lecture 10 1 Constructing Optimum Binary Search trees

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,k1]+M[k+1,j]}-
k=1..j
X
Pj
t=i i
because
Ppt
thenwecanget jt=ipt asP[j]P[i1].
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 n1do 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[i1] # subproblems od ✓ 2 H2er Runtime O(n · n) = O(n ) #disjiinabove \ 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(i1,w)
*
Let M(i, w) = max To find M(i,w)
^
I
#
PX
X
i2S
wi  w i2S
•elseM(i,w):=max M(i1,w) #don’tusei vi+M(i1,wwi) #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