程序代写代做代考 DynamicProgramming – Recall Fibonacci

DynamicProgramming – Recall Fibonacci
recursive f(n)
if n=0then return 0
elif n=1then return 1
else
CS 341 F20 Lecture 8 1 ” program” as in “exercise program”,
return f(n1)+f(n2) fi
T (n) = T (n1)+T (n2)+c so runtime grows like the Fibonacci numbers. BAD!
O000 duplication !
n o t
”
computer program ”
iterative
f(0) := 0
f(1):=1
for ifrom 2to ndo
f(i):=f(i1)+f(i2) od
O(n) arithmetic operations. GOOD!
– an example of dynamic programming
Main idea of dynamic programming:
solve “subproblems” from smaller to larger (bottom up) storing solutions
Runtime: (# subproblems)
⇥ (time to solve one subproblem)

Text segmentati
Gi
e.g.,
Can
Can
Clai
ven
Assume you
Note:
where
we
we
m
a string
do
each
THEMEMPTY
a
greedy solu
then
: Split[
o
have
on
f letters
something l
find
n] i
S
a
call takes
th
e
sho
test
plit[k]
rtest
or
Split[n
f and
(
)
ike
only
we
if A[
A
the
=
]?
h
[1
O(1)
splits into
tion might try to
..n], A[i] 2 {A,
Word[i,
word
longest wor
Fib
Tr
if at
ave
1.
.n]
j]
onacci?
⇢ Tru False
y
a
e
Spl
least
way
is
if
=⇢
THEM EM
o
CS
find
A[1..i] (pre
d
341 F20
True
Supp
A[1..k] is
otherwise
it[j] and
ne j gives
ose
to split A[1..n]
splittable, take A[j
Lecture
B,. .
False otherwise
PTY
fix)
A[1..i]
:
:
we
.,
if A[i.
8
Z
}, can
.j
THE
] is
THEME
knew
splittable
Word[j + 1,
True. Why?
+
a
for
n
1..n]
you split into
word
MEMPTY
MPTY
k
as
= 0..n1
] for all j =
last word
wr
wr
words?
ong
ong
0..n
1.
2

CS
341 F20
Lecture
8
3
Resulting algorith
m:
Split[0] :
=
True
for k fro
m 1 to n
do
Split[
k] :
=
False
for
j
from
0 to
k Wor
1
do
if Split[j]
an
d
d[j
+1,k]
t
hen
Split[k]
:=
True
fi
od
o
d
Runti
m
e:
O(n2)
Ex.
Show how
t
o
compu
te the actua
l split

Longest Increasing Subseq
Gi
ven
e.g.,
a sequence
This does not
!
need to
Better Idea:
Al
gorithm
LISe
for k
od
LI
fo
od
[1] := 1
r
if
fi
5
llowing previous app
LI
S[k] =
see
from
Se[k]
j
A[
L
O
:=
21
lengt
seem
from
LISe
k] >
of numbers,
h
O
if A[n] is
et LISe[k]
that end
2
1
to
1
A[j ]
43
t
[k] := max{
s
n
o
roach,
of longest
to gi
uence
16
ve en
la
do
k then
0
rge
=l
with
eng
A
1
A[1..n],
0
9
ough
enou
d
2
increasing
th of
[k].
o
LISe[k], LISe[j]
gh to
CS
lon
341 F20
A[i]
add
2
Increasing
if we set
s
ubs
info to get LIS[n
+1}
Lecture
N,
equ
fi
8
nd the
enc
to a previous
sub
e
of A[
] from
gest increasing subsequence
Ex.
longest increasing subse
sequence of
Runti
1.
.k]?
previous
seq
uen
ce
length
Argue correctne
m
e
O(n2)
of
A
4
[1..k]
ss
quence
.
4
Fo
w
hat
LIS[k]’s.

Exam
OR
Note:
ple
maximu
a
dd
m entr
dummy entry
there is
an
O
in LI
(n log n)
Se
A[n +
1] =
time
3
+1
algorith
CS
4
341 F20
2
Lecture
and return LISe[n
m
8
+
1
]
1
5
Run t
How do we
ime:
get the
y
final answer?
4
73
O(n2)

Longest Common
Recall pa
Gi
Al
ven
Useful in
so useful
TA
CA
ttern
a long
x
gre
R
T
: gi
s
M
A
tr
p, fin
ven
ing
Subsequence
matching
T and
d, etc.
x
two lo
AC
MA
..
xn
R
from
ng strings
A
N
CS
short pattern
…
240:
CS
341 F20
P
find longest
Note
b
ut must
t
hat
Lecture
find oc
we
8
currences of
common subsequence
can sk
preserve
ip letters i
ordering
.
P in
n
T.
b
oth
strin
gs,
6
Gi
Le
So
ven
t
M
M
M
lve
M (i,
How can
Cho
ices:
s
tr
(i,0) =
(0,j) =
(i,j) =
sub
ings x1 .
j) =
w
e
match
0
len
solve
8< 1 + : problems in 0 max gth o and y1 f longest this subprobl xi = yj, M(i M(i,j M(i any order 1, j 1,j) 1) ym, common su em skip xi, skip yj with based on solu 1 ) M(i1, bsequence if xi j tions = yj 1), of x1 · M(i · · xi1xi to “smaller” subproblems? 1,j ), M(i,j and 1) y1 · · · yj1yj befor e M (i, . j) CS 341 F20 Lecture 8 7 y1234 9 ;CATAMARAN x;000000 I tf 1T0 0 0 1→0I wth 2A001→1→2 3R00 M0 A entering each 4 t red boxgivesoptimum 6C4 for i = 0..n: M(i,0) := 0 for j = 0..m: M(0,j) := 0 for i = 1..n forj=1..m 8<1+M(i1,j1) ifxi =yj M(i, j) := max : M(i 1, j) M (i, j 1) M matrix jpg to fillthisentrywe → look a t 1416,9) 3 other entries arrow for that box Note that this is a correct ordering of i and j. In fact, if xi = yj we can use the first choice (no need to check max of other two choices). Runtime: O(n · m · c) →x subproblem s CS 341 F20 Lecture 8 8 # To find the actual max. common subsequence: work backwords from M (n, m). ! Call OPT(n, m). OPT(i, j) — recursive routine if i = 0 or j = 0 then done fi if M(i,j)=M(i1,j)then OPT(i1,j) elif M(i,j)=M(i,j1)then OPT(i, j 1) else — we must have matched i and j output i, j OPT(i 1, j 1) fi Or we can record, when we fill M(i,j), where the max comes from. Next day: more sophisticated “edit” distance between strings. tim e to solve o n e subproblem ( compare 3 possibilities ) Maximum Longest i L S S Clai = s m 9 52 23 ort L common ncreasi 4567 : Longest incr subsequence solves ng subse /00 9637 , 4 9 que nce easing subsequence inc reasing s CS 341 F20 of L ubs Lecture equenc 8 e of length 3 = maximum commo n subseq uence of L and S. 9