CENG 303
DESIGN AND
ANALYSIS OF
ALGORITHMS
WEEK 13
Dynamic
Programming
Dynamic Programming (DP)
• Allows us to solve our problems in polynomial time
– Careful brute-force
– Try all possible solution in a smart way
– Create subproblems
– Re-use
• Fibonacci numbers
• Shortest path problems
• Text Justification
• Blackjack
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Dynamic Programming (DP)
• Five “easy” steps
– Easy means interdependent
1. define subproblems
2. guess (part of solution)
3. relate subproblem solutions
4. recurse & memoize
5. solve original problem
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Fibonacci Numbers
𝐹1 = 𝐹2 = 1
• ቊ
𝐹𝑛 = 𝐹𝑛−1 + 𝐹𝑛−2
• Compute 𝑛th Fibonacci number
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Fibonacci Numbers
• Naïve recursive algorithm
• fib(n) = if n≤2 : f = 1
else f = fib(n-1) + fib(n-2)
return f
• T(n) = T(n-1) + T(n-2) + Θ(1)
• Exponential
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Fibonacci Numbers
• T(n) = T(n-1) + T(n-2) + Θ(1)
• T(n) = T(n-2) + T(n-3) + Θ(1) +
T(n-3) + T(n-4) + Θ(1) +
Θ(1)
• T(n) = T(n-3) + T(n-4) + Θ(1) +
T(n-4) + T(n-5) + Θ(1) +
T(n-4) + T(n-5) + Θ(1) +
T(n-5) + T(n-6) + Θ(1) +
Θ(1) + Θ(1) + Θ(1)
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Fibonacci Numbers
• T(n) = T(n-1) + T(n-2) + Θ(1)
• T(n) ≥ T(n-2) + T(n-2) + Θ(1)
• ≥ 2T(n-2) + Θ(1)
• ≥ Θ(2𝑛/2 )
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Memoized DP Algorithm
memo = {}
fib(n)
if n in memo: return memo[n]
if n ≤2 : f=1
else f=fib(n-1) + fib(n-2)
memo[n] = f
return f
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Memoized DP Algorithm
𝐹𝑛
𝐹𝑛−1 𝐹𝑛−2
𝐹𝑛−2 𝐹𝑛−3 𝐹𝑛−3 𝐹𝑛−4
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Memoized DP Algorithm
𝐹𝑛
𝐹𝑛−1 𝐹𝑛−2
𝐹𝑛−2 𝐹𝑛−3 𝐹𝑛−3 𝐹𝑛−4
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Memoized DP Algorithm
𝐹𝑛
𝐹𝑛−1 𝐹𝑛−2
𝐹𝑛−2 𝐹𝑛−3 𝐹𝑛−3 𝐹𝑛−4
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Memoized DP Algorithm
𝐹𝑛
𝐹𝑛−1 𝐹𝑛−2
𝐹𝑛−2 𝐹𝑛−3 𝐹𝑛−3 𝐹𝑛−4
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Memoized DP Algorithm
• fib(k) only recurses the first time it’s called
• to calculate fib(k) the recursion happens only 𝑛 times
– fib(1), fib(2), fib(3),…, fib(n)
– Each recursion cost Θ(1)
• Memoized calls cost Θ(1)
• Θ(n)
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Dynamic Programming
• memoize (remember)
• re-use solutions to subproblems
• total time = the number of subproblems x
time for per subproblem
• we do not need to count memoized recursions
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Bottom-up DP Algorithm
fib = {}
for k in range(1,n+1)
if k≤2 : f=1
else f=fib[k-1] + fib[k-2]
fib[k] = f
return fib[n]
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Bottom-up DP Algorithm
• exactly same computation
• topological sort of subproblem dependency DAG
𝐹𝑛−3 𝐹𝑛−2 𝐹𝑛−1 𝐹𝑛
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Fibonacci Numbers
1. define subproblems
– fib(k) for 𝑘 = 1, … , 𝑛 | number of subproblems is 𝑛
2. guess (part of solution)
– nothing | number of choices is 1
3. relate subproblem solutions
– recurrence | fib(k) = fib(k-1) + fib(k-2)
Θ(1)
4. recurse & memorize
– topological order | for 𝑘 = 1, … , 𝑛
check subprob recurrence is acyclic
5. solve original problem
– fib(n)
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Shortest Paths
• 𝛿 𝑠, 𝑣 ∀𝑣
• recursive formulation
𝛿 𝑠, 𝑣 = min 𝛿 𝑠, 𝑢 + 𝑤 𝑢, 𝑣 𝑢, 𝑣 𝜖𝐸}
s u v
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Shortest Paths
• Guessing
• What is the last edge? Maybe 𝑢, 𝑣 ?
• To find best guess, try all edges going 𝑣 and use best
s u v
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Shortest Paths
• Guessing
• What is the last edge? Maybe 𝑢, 𝑣 ?
• To find best guess, try all edges going 𝑣 and use best
• key: small (polynomial) number of possible guesses per
subproblem — typically this dominates time/subproblem
s u v
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Shortest Paths
• The drawback:
– Takes infinite time if the graph is cyclic
𝛿 𝑠, 𝑣 a
𝛿 𝑠, 𝑎
s v
𝛿 𝑠, 𝑏
𝛿 𝑠, 𝑠 𝛿 𝑠, 𝑣 b
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Shortest Paths
• How to solve?
• Convert cyclic graph to acyclic graph
• We will not cover this!
time
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Text Justification
• split given text into “good” lines
• text is a list of words
(𝑝𝑎𝑔𝑒 𝑤𝑖𝑑𝑡ℎ − 𝑡𝑜𝑡𝑎𝑙 𝑤𝑖𝑑𝑡ℎ)3
• badness(i,j) = ቊ
∞ 𝑖𝑓 𝑑𝑜 𝑛𝑜𝑡 𝑓𝑖𝑡
– use words[i:j] as line
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Text Justification
1. subproblems: suffixes [i:]
– number of subproblems: |n
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Text Justification
1. subproblems: suffixes [i:]
– number of subproblems: |n
2. guess: where to start 2nd line
– number of choices : | ≤ 𝑛 − 𝑖 = O(n)
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Text Justification
1. subproblems: suffixes [i:]
– number of subproblems: |n
2. guess: where to start 2nd line
– number of choices : | ≤ 𝑛 − 𝑖 = O(n)
3. recurrence: DP(i)
𝐷𝑃 𝑗 +𝑏𝑎𝑑𝑛𝑒𝑠𝑠(𝑖,𝑗)
– min 𝑓𝑜𝑟 𝑗 𝑖𝑛 𝑟𝑎𝑛𝑔𝑒 (𝑖+1,𝑛+1)
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Text Justification
1. subproblems: suffixes [i:]
– number of subproblems: |n
2. guess: where to start 2nd line
– number of choices : | ≤ 𝑛 − 𝑖 = O(n)
3. recurrence: DP(i)
𝐷𝑃 𝑗 +𝑏𝑎𝑑𝑛𝑒𝑠𝑠(𝑖,𝑗)
– min 𝑓𝑜𝑟 𝑗 𝑖𝑛 𝑟𝑎𝑛𝑔𝑒 (𝑖+1,𝑛+1)
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Text Justification
1. subproblems: suffixes [i:]
– number of subproblems: |n
2. guess: where to start 2nd line
– number of choices : | ≤ 𝑛 − 𝑖 = O(n)
3. recurrence: DP(i)
𝐷𝑃 𝑗 +𝑏𝑎𝑑𝑛𝑒𝑠𝑠(𝑖,𝑗)
– min 𝑓𝑜𝑟 𝑗 𝑖𝑛 𝑟𝑎𝑛𝑔𝑒 (𝑖+1,𝑛+1)
– time per subproblem = O(n)
4. topological order
– DP(n) = 0
– i = n, n-1, n-2, …, 0
– total time = Θ(𝑛2 )
5. original Problem: DP(0)
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Blackjack
• The goal of blackjack is to beat the dealer's hand without going over 21.
• Face cards are worth 10. Aces are worth 1 or 11, whichever makes a better hand.
• Each player starts with two cards, one of the dealer's cards is hidden until the end.
• To 'Hit' is to ask for another card. To 'Stand' is to hold your total and end your turn.
• If you go over 21 you bust, and the dealer wins regardless of the dealer's hand.
• If you are dealt 21 from the start (Ace & 10), you got a blackjack.
• Blackjack usually means you win 1.5 the amount of your bet. Depends on the casino.
• Dealer will hit until his/her cards total 17 or higher.
• Doubling is like a hit, only the bet is doubled, and you only get one more card.
• Split can be done when you have two of the same card - the pair is split into two hands.
• Splitting also doubles the bet, because each new hand is worth the original bet.
• You can only double/split on the first move, or first move of a hand created by a split.
• You cannot play on two aces after they are split.
• You can double on a hand resulting from a split, tripling or quadrupling you bet.
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Blackjack
• Perfect-information Blackjack
• deck = 𝑐0 , 𝑐1 , … , 𝑐𝑛−1
• the sequence of cards in the deck is known
• 1 player vs dealer
• $1 bet per game
• there is no split, no doubling
• maximize the earning
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Blackjack
1. subproblems: suffix 𝑐𝑖
– number of subproblems: |n
2. guess: how many hits?
– number of choices | ≤n
3. recurrence
– Blackjack(i) = max (outcome ∈ {−1,0,1} | O(n)
+ Blackjack(j)
for # hits in range (0,n) | O(n)
– j = i+4+#hits+#dealer hits
– time per subproblem O(𝑛2 )
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Blackjack
4. topological order:
– for i in reversed(range(n)) |Θ(𝑛3 )
5. Solution:
– Blackjack(o)
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi
Blackjack
outcomes
1
1
0
-1
i i+4 i+5 i+6 i+7
valid plays
Ogr. Gor. Dr. Fadi YILMAZ – FALL 2020 Mühendislik ve Doğa Bilimleri Fakültesi