Assignments
• Assignment 2: Done
• Assignment 3:
• Will be released on 2 Oct
• Due: 23 Oct 23:59
• Grace period ends: 24 Oct 13:00
Final Project
• Milestone 1:
• Feedback sent on 26 Sep morning
• We are resolving issues with feedback for 10 students because of inconsistencies in the name used in wattle and enrollment record
• If you don’t want to have this type of delay, please use the same name as in your enrollment record
Final Project
• Milestone 2:
• Description released on 26 Sep night (please
read them)
• Due: 8 Oct 23:59
• Grace period ends: 9 Oct 13:00
• Last chance to alter application and assumptions
• Can modify at most 2 functionalities
• 2 things to submit • Design document • Program skeleton
COMP3600/6466 – Algorithms
Algorithm Design Techniques [Lev Intro of ch. 2-6, 8-10]
Hanna Kurniawati
https://cs.anu.edu.au/courses/comp3600/ comp_3600_6466@anu.edu.au
So far …
üThe Problem
üAlgorithm definition + Model of Computation
üAnalysis of Algorithms
üAsymptotic Notations
üRecurrence Analysis (Divide-and-Conquer)
üProbabilistic Analysis (Avg. case + Randomized Algorithms) ü Correctness
üEmpirical Analysis
üAbstract data structures üBinary Search Tree
ü Heaps
üAVL Tree
üRed Black Tree üHash Tables
Algorithm Design Techniques
• Brute Force
• Divide & Conquer
• Randomized Algorithm • Decrease & Conquer
• Transform & Conquer • Dynamic Programming • Greedy
• Iterative Improvement
Algorithm Design Techniques
• Brute Force: When stuck, start here and improve
• Divide & Conquer: Discussed a bit in recurrence analysis
• Randomized Algorithm: Discussed a bit in prob. analysis
• Decrease & Conquer: Very similar to divide & conquer, but reduce to 1 smaller sub-problem (e.g., Insertion Sort)
• Transform & Conquer: Simplify the problem. For instance, by pre-sorting and changing data representation (use suitable abstract data structures)
• Dynamic Programming
• Greedy
• Iterative Improvement
COMP3600/6466 – Algorithms
Dynamic Programming [CLRS ch. 15 + 22.4]
Hanna Kurniawati
https://cs.anu.edu.au/courses/comp3600/ comp_3600_6466@anu.edu.au
Topics
• What is it?
• Example: Fibonacci Sequence
• How to develop DP algorithms?
• Example: Shortest Path
• Example: Chain matrix multiplication
• Example: Longest Common Subsequence
• Example: Decision-making under uncertainty
What is Dynamic Programming (DP)
• DP is an approach to solve problems by trying all
possibilities while avoiding recomputation
• Key idea: Remember solutions that have been computed and reuse as much as possible
DP Requirements
• Not all problems can be solved using DP. Can only be applied to problems whose solutions can be constructed from solutions to its sub-problems
• Specifically, two requirements:
• Optimal substructure: Optimal solution to the problem is formed by optimal solutions to sub- problems, which can be solved separately.
• Overlapping sub-problems
DP – Trivia
• Invented by Richard Bellman in the ‘50s
• ”Programming” here has somewhat different
meaning than computer programming
• Many stories as to what the word “Programming” actually means and why it is used
• Regardless, it is a powerful algorithm design technique
• Often used for solving optimization problem
Types of Dynamic Programming
• Two types:
• Top-down (memoization)
• Start from the problem we want to solve
• Solve sub-problems “reachable” (based on a decomposition of the problem) from the problem and store the results (aka., made into a memo, memoization)
• Reuse the stored solutions whenever possible • Bottom-up
• Compute the sub-problems from small to large, starting from the base, keep the results
• Reuse whenever possible
Topics
üWhat is it?
• Example: Fibonacci Sequence
• How to develop DP algorithms?
• Example: Shortest Path
• Example: Chain matrix multiplication
• Example: Longest Common Subsequence
• Example: Decision-making under uncertainty
Example: Fibonacci Sequence
• The nth Fibonacci number is F(n) = F(n-1) + F(n-2)
• Algorithm to output the nth Fibonacci number NaiveFibonacci(n)
If n ≤ 2 Return 1
Else
Res = NaiveFibonacci(n-1) + NaiveFibonacci(n-2) Return Res
• Time complexity?
• 𝑇𝑛 =𝑇𝑛−1 +𝑇𝑛−2 +Θ1 =Θ(2!)
𝑇𝑛 =𝑇𝑛−1 +𝑇𝑛−2 +Θ1
Upper bound:
𝑇𝑛 ≤2𝑇𝑛−1 +𝑐 =22𝑇𝑛−2 +𝑐 +𝑐
=2.2(2𝑇 𝑛−3 +𝑐)+2𝑐+𝑐
=2.2.2…2.𝑇 2 +𝑐∑$%&2! !”#
𝑛−2
= 2$%’ + 𝑐 2$%’ − 1 = O(2$)
𝑇𝑛
≥2𝑇𝑛−2 +𝑐 =22𝑇𝑛−4 +𝑐 +𝑐 =2.2(2𝑇 𝑛−6 +𝑐)+2𝑐+𝑐
Lower bound:
! %(
= 2.2.2 … 2. 1 + 𝑐 ∑ ” 2! 𝑛 !”#
2
!
=2″ +𝑐2″ −1
!
= Ω(2$)
𝑇𝑛 =𝑇𝑛−1 +𝑇𝑛−2 +Θ1 =Θ2,
Can we do better?
• Yes, using DP
• The problem satisfies the two requirements
for DP:
• Optimal sub-structure: In this case, solution to Fibonacci(n) is formed by solutions to Fibonacci(n-1) and Fibonacci(n-2), and the sub-problems can be solved separately
• Overlapping sub-problems
Overlapping Sub-problems
NaiveFibonacci performs too many repeated calculations
Example: Memoization
• Top-down DP (sometimes called memoization)
TopDownDP-Fibonacci(n) Fibo[1..n] = -1
Return RecurseFibo(n, Fibo)
RecurseFibo(n, Fibo) If (Fibo[n] != -1)
Return Fibo[n] If n ≤ 2
F=1
Time complexity? Θ(𝑛)
Else
F = RecurseFibo(n-1, Fibo) + RecurseFibo(n-2, Fibo)
Fibo[n] = F Return F
Example: Bottom-Up
• Bottom-up DP BottomUp-Fibonacci(n)
Fibo[1] = 1 Fibo[2] = 1 For i = 3 to n
Fibo[i] = Fibo[i-1] + Fibo[i-2] Return Fibo[n]
• Time complexity? Θ(𝑛)
Bottom-Up DP
• No recursion
• Although asymptotic time complexity is the same as top-down, in practice bottom-up is faster because it reduces the number of function calls
• How to decide which sub-problem to compute first?
• Reverse topological order of the sub-problem graph
• Sub-problem graph encodes dependencies of the sub-problems
• Vertices: Sub-problems
• An edge from u to v: Solving the sub-problem represented by u
requires direct solving of the sub-problem represented by v
• For DP to work this graph must be a directed acyclic graph (DAG)
Topological Sort of DAG [CLRS 22.4]
• Suppose G(V, E) is a DAG
• Topological sort of G is a linear ordering of all its vertices such that if G contains a directed edge (u, v) then u appears before v in the ordering
• Use DFS that maintain time stamp
• Discovery time of vertex v: The time v is first visited
• Finishing time of vertex v: The time all vertices in E adjacent to v have been visited
[CLRS p.604]
Example
• Start from u
Topological Sort of DAG [CLRS 22.4]
Time complexity: Θ( 𝑉 + 𝐸 )
• Example:
Now, back to Fibonacci DP Example
• Sub-problem graph:
What if sub-problem graph has cycle?
• Cause the DP to have infinite loop • What can be done?
Topics
üWhat is it?
üExample: Fibonacci Sequence
• How to develop DP algorithms?
• Example: Shortest Path
• Example: Chain matrix multiplication
• Example: Longest Common Subsequence
• Example: Decision-making under uncertainty
Next:
How to develop DP algorithms & More examples