COMP3821: Assignment 3 Solution - Algorithms and Dynamic Programming

This document presents a comprehensive solution for COMP3821 Assignment 3, focusing on dynamic programming techniques and algorithm analysis. The solution explores two approaches to the cut-rod problem: memoized recursion and iteration, analyzing their time complexities. It also includes a ...Read More

COMP3821 Assignment 3
Jinming Dong(z5211275)
May 4, 2020
1
1.1
O(2n )
1.2
1.2.1 recursion
initial M [0, · · · , n] ←⊥ to store the value of cut-rod(P,n)
memoized − cut − rod(P, n)
· · · if M [n] 6=⊥ then
· · · · · · return M[n]
· · · if n=0 then
· · · · · · q ← 0
· · · else
· · · · · · q ← −∞
· · · · · · for i=1 to n do
· · · · · · · · · q ← max(q, P [i] + memoized − cut − rod(P, n − i))
· · · M [n] ← q
· · · return M[n]
1.2.2 Iteration
memoized − cut − rod(P, n)
· · · let M [0, · · · , n] to store the value of cut-rod(P,n)
· · · M[0] =0
· · · for i=1 to n do
· · · · · · M [i] ← −∞
· · · · · · for j=1 to i do
· · · · · · · · · M [i] ← max(q, P [j] + M [i − j])
· · · return M[n]
1
This study source was downloaded by 100000822526728 from CourseHero.com on 03-31-2021 06:46:33 GMT -05:00
https://www.coursehero.com/file/70008931/a3pdf/
This study resource was
shared via CourseHero.com

1.3
O(n2)
1.4
1. Base case:when n=0,a call to memoized-cut-rod(P,n) return 0 and a call
to cut-rod(P,n) return 0,so they return the same result.
2. Induction:when n>0, assume a call to memoized-cut-rod(P,n) returns the
same result as cut-rod(P,n).When n=n+1,a call to memoized-cut-rod(P,n)
returns the max(P [i] + memoized − cut − rod(P, n + 1 − i)), i ∈ {1, · · · , n +
1} and cut-rod(P,n) returns the max(P [i] + cut − rod(P, n + 1 − i)), i ∈
{1, · · · , n+1}.By assumption, memoized-cut-rod(P,x) = cut-rod(P,x) when
x ∈ {0, · · · , n} and n + 1 − i ∈ {0, · · · , n}.So when n=n+1,they return the
same result.
3. Hence,a callto memoized-cut-rod(P,n) returns the same result as cut-
rod(P,n) for any array P of length n ∈ N .
2
2.1
Sequence k
[R, B, R, G, O, O, G, T, I, I, T ]3
[R, G, B, G, R] 1
[C, C, C, C, A, X, B, X] 3
[Z, X, Y, Z, X] 5
[A, BD, C, BD, A] 1
[A, O, A, B, X, Z, Y, X] 6
[A, B, B, A, C, A, B] 4
2.2
subproblems:the minimum number ofsymmetric sequences that make up se-
quence S[1, · · · , i], store the number in M[i].
the base case:M[0]=0.
recurrence relation:M [i] = 1 + min(M [j]),0 ≤ j ≤ i − 1 and S[j + 1, · · · , i]is
symmetric.
2
This study source was downloaded by 100000822526728 from CourseHero.com on 03-31-2021 06:46:33 GMT -05:00
https://www.coursehero.com/file/70008931/a3pdf/
This study resource was
shared via CourseHero.com

2.3
The worst-case time complexity:O(n3)
For getting M[i],the algorithm willcheck if S[j + 1, · · · , i]is symmetric which
takes O(i−j) times, 0 ≤ j ≤ i − 1 and choose the minimum M[j].The worst-case
time complexity of the subproblem is O(i2). So the worst-case time complexity
of the algorithm is O(12 + 22, · · · , n2) = O(n3).
3
3.1
x0 x1 x2
1 0 1
0 2 0
3.2
Algorithm(C[1, · · · , n], s)
· · ·count=0
· · ·for x1=0 to s/C[1] do
· · · · · · · · ·for x2=0 to s/C[2] do
· · · · · · · · · · · · · · · ↓
· · · · · · · · · · · · · · ·for xn =0 to s/C[n] do
· · · · · · · · · · · · · · · · · ·if C [1]x1 + C[2]x2+, · · · , +C[n]xn = s then
· · · · · · · · · · · · · · · · · · · · ·count = count+1
· · ·return count
3.3
O(( s
m )n )
3.4
subproblems:let dp[i][j] denotes the the number of natural number to solutions
to the equation (C[1, · · · , i], j), and the answer is dp[n][s], n is the length of C.
base cases:dp[i][0] = 1, i = 1, · · · , n
recurrence relation:dp[i][j] =
P j
c[i]
t=0 dp[i − 1][j − t ∗ C[i]]
return dp[n][s]is the number of naturalnumber solutions to a linear equation
(C, s).
3
This study source was downloaded by 100000822526728 from CourseHero.com on 03-31-2021 06:46:33 GMT -05:00
https://www.coursehero.com/file/70008931/a3pdf/
This study resource was
shared via CourseHero.com
Powered by TCPDF (www.tcpdf.org)