---
title: CSCI6212_HW5
tags: CSCI6212, Algorithm
---
<style>
.text-center{
text-align: center; //文字置中
}
.text-left{
text-align: left; //文字靠左
}
.text-right{
text-align: right; //文字靠右
}
</style>
<h1 class="text-center">CSCI 6212 - Homework 5</h1>
<h3 class="text-center">Chien-Huan Kao (G37556856)</h3>
<br>
1. (10 points) Consider the recurrence relation $T(0) = T(1) = T(2) = 1$ and for $n > 1$,
$$
T(n)=\sum^{n-1}_{i=2}T(i)T(i-2)
$$
We want to compute $T(n)$ for a given arbitrary integer $n$. If you implement this recursion directly, the program would use exponentially (in n) many arithmetic operations. You can however obtain an algorithm for computing $T(n)$ using only $O(n)$ arithmetic operations by not computing the same $T(i)$ value twice. Give such an algorithm.
**Sol.**
``` python=
def T(n):
T_arr = [0]*(n+1)
T_arr[0] = T_arr[1] = T_arr[2] = 1
for i in range(3, n+1):
T_arr[i] = 0
for j in range(2, i):
T_arr[i] += T_arr[j]*T_arr[j-2]
return T_arr[n]
```
2. (20 points) Consider the longest monotonically increasing subsequence problem discussed in Homework 4. We solved the problem by transforming to the longest path problem in a DAG.
a) Give a dynamic programming algorithm to find the longest monotonically increasing subsequence of $A = \{a_1, a_2, \cdots, a_n\}$.
**Sol.**
```python=
def subsequence(A):
n = len(A)
dp = [1] * n
prev = [-1] * n
for i in range(1, n):
for j in range(i):
if A[j] < A[i] and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
prev[i] = j
max_len = max(dp)
idx = dp.index(max_len)
seq = []
while idx != -1:
seq.append(A[idx])
idx = prev[idx]
return reversed(seq)
```
b) Apply your algorithm in (a) to a sequence $A = \langle 1, 3, 2, 4, 6, 13, 14, 15, 5, 6, 8, 12, 13\rangle$ and show the result.
**Sol.**
3.
a)
**Sol.**
Assume $k=20,n=100,m=30$
There are $4$ gas stations between DC and Las Vegas.
DC location is $0$, and Las Vegas is $300$ which represents the distance from the start point to Las Vegas.
Let $V = (0,60,100,120,200,300)$ denote the location of each gas station.
Let $P = (19, 20,15,5,20,0)$ denote the gas price at each stations.
According to the algorithm, we will stop at $(v_1, v_3,v_5,v_6)$. The cost is $19 \times 20 + 15 \times 20 + 20 \times 20 = 1080$.
However, there is a counter case. We can stop at $(v_1,v_2,v_4,v_5,v_6)$. The cost is $19 \times 20+20 \times 4 + 5 \times 20 + 20 \times 16=880$.
Therefore, the algorithm is not an optimal algorithm.
b)
**Sol.**
$C(j,r)=\infty$ for all $j$ and $r$
base case: $C(1,r)=r \cdot p_1$ for all $r=0,\cdots,k$
recurrsively do $C(j,r)$
$\text{for all edge} (i,j)$
$\text{ } \text{ } \text{ } \text{ } \text{if } p_i\leq p_j$
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{for } s \text{ from 0 to } k$
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{if }r+D_{ij}\times\frac{k}{n}<k$
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } C(j,r)=\text{min}\{C(i,s)+\frac{D_{ij}}{n}k\times p_i+(r-s)p_i, C(j,r)\}$
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{else }$
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } C(j,r)=\text{min}\{C(i,s)+(k-s)p_i+(r-(k-\frac{D_{ij}}{n}k))p_j,C(j,r)\}$
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{endif}$
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{endfor}$
$\text{ } \text{ } \text{ } \text{ } \text{endif}$
$\text{ } \text{ } \text{ } \text{ } \text{if } p_i>p_j$
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{for s from 0 to }k$
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{if }s<\frac{D_{ij}}{n}k$
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } C(j,r)=\text{min}\{C(i,s)+(\frac{D_{ij}}{n}k-s)\times p_i+r\times p_j, C(j,r)\}$
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{else}$
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } C(j,r)=\text{min}\{C(i,s)+(r-(s-\frac{D_{ij}}{n}k))p_j,C(j,r)\}$
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{endif}$
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{endfor}$
$\text{ } \text{ } \text{ } \text{ } \text{endif}$
$\text{endfor}$
4. (20 points) Let $G$ be an edge-weighted graph with vertex set $V$ and edge set $E$. Let $V_0$ be arbitrary subsets of $V$ such that $V_0 \not= \emptyset$.
a) Describe an $O(n^3)$ time dynamic programming algorithm that finds a shortest path for every source-destination pair of nodes in $V$ such that no vertex in $V_0$ may be used as an intermediate vertex in any shortest path, but any vertex in $V - V_0$ may be used as an intermediate vertex in any shortest path.
**Sol.**
Let $C=(V-V_0) \cup V_0$ and all elements in $V_0$ must list behind $(V-V_0)$.
Let $n = |V|$, $m=|V_0|$
Let $A^k(i,j)$ denote the length of a shortest path from $i$ to $j$ going through no vertex of index greater than $k$th in $C$.
Then we recursively do the algorithm:
$$A^{k}(i,j) = \text{min}\{A^{k-1}(i,j), A^{k-1}(i,k)+A^{k-1}(k,j)\}$$ for $(n-m)\geq k\geq1$, and $A^0(i,j)=w(i,j)$ for all $i,j$ in $V$.
The answer is $A^{n-m}$.
This is Floyd's algorithm, and its time complexity is $O(n^3)$.
b) Describe an $O(n^3)$ time dynamic programming algorithm that finds a shortest path for every source-destination pair of nodes in $V$ such that exactly one vertex in $V_0$ must be used as an intermediate vertex in each shortest path, and any vertex in $V - V_0$ may be used as an intermediate vertex in any shortest path.
**Sol.**
According to (a),
$$B(i,j) = \mathop{\min}_{n-m+1\leq k\leq n} \{A^{n-m}(i,k)+A^{n-m}(k,j)\}$$.
The answer is $B(i,j)$.
This is Floyd's algorithm, and its time complexity is $O(n^3)$.
5. (10 points) Given an $m \times n$ matrix of integers, you are to compute a path of minimal weight such that a path starts anywhere in column $1$ (the first column) and consists of a sequence of steps terminating anywhere in column $n$ (the last column). A step consists of traveling from column $i$ to column $i+1$ in an adjacent (horizontal or diagonal) row. The first and last rows (rows $1$ and $m$) of a matrix are considered adjacent, i.e., the matrix "wraps" so that it represents a horizontal cylinder. For example, a move from cell $(1, 1)$ to cell $(m, 2)$ is legal. Legal steps are illustrated in Figure 2.
The weight of a path is the sum of the integers in each of the $n$ cells of the matrix that are visited. For example, two slightly different $5 \times 6$ matrices are shown in Figure 3 (the only difference is the numbers in the bottom row). The minimal path is illustrated for each matrix. Note that the path for the matrix on the right takes advantage of the adjacency property of the first and last rows.
**Sol.**
Let $A(i,j)$ denote the minimum weight path starting from column $1$ and ending in column $j$ that includes the cell $(i, j)$.
First, the base cases are $A(i,1) = \text{matrix}(i,1)$ since the only possible path starting in column 1 is to go straight down.
We then have
$$
A(i,j) = \text{min}\{A(i-1,j-1),A(i,j-1),A(i+1,j-1)\} + \text{matrix}(i,j)
$$ where $\text{matrix}(i,j)$ is the weight of the cell $(i,j)$ in the matrix. If $i-1=0$ then $i=m$, and if $i+1>m$ then $i=0$.
We can find the minimal weight by $\text{min}\{A(1,n),A(2,n),\cdots,A(m,n)\}$
6. (10 points) You are given n types of coin denominations of values $v(1) < v(2) <\cdots < v(n)$ (all integers). Assume $v(1) = 1$, so you can always make change for any amount of money $C$. Give an $O(nC)$ time dynamic programming algorithm which makes change for a given amount of money $C$ with as few coins as possible.
**Sol.**
Let $F(x)$ denote the minimum number of coins required to make change for $x$.
Fist, we initialize $F(0) = 0$, and $F(x) = \infty$ for all $x > 0$.
Then we run the following code:
```
F(C):
for x = 1 to C
for i = 1 to n
if v(i) <= x
F(x) = min(F(x), 1 + F(x - v(i)))
```
The answer is $F(C)$.
7. (10 points) The input to this problem is a sequence $S$ of $n$ integers (not necessarily positive). The problem is to find the consecutive subsequence of $S$ with maximum sum. For example if the input was $12,-14, 1, 23, -6, 22,-34, 13$, the output would be $1, 23, -6, 22$. Give a linear time dynamic programming algorithm for this problem.
**Sol.**
```python=
def subsequence(S):
n = len(S)
max_sum = [0] * n
max_sum[0] = S[0]
max_sum_end = S[0]
for i in range(1, n): #T(n)
max_sum[i] = max(S[i], max_sum[i-1] + S[i])
max_sum_end = max(max_sum_end, max_sum[i])
max_sum_start = max_sum.index(max_sum_end)
curr_sum = max_sum_end
for i in range(max_sum_start, -1, -1):
if curr_sum == S[i]:
max_subseq = S[i:max_sum_start+1]
break
curr_sum -= S[i]
return max_subseq
```
Sign in with Wallet
Connect another wallet