CS535-HW4
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
1. The task is to find out the longest descending subsequence. Define L[i] to denote (1<=i<=n) the largest length of a longest descending subsequence ended with b[i]. Pre[i] denotes the previous index of b[i] in the longest descending subsequence ended with it. We can get the result by the following derivation of equation:
L[i] = max{L[j] + 1, L[i]} (1 ≤ i ≤ n, 1 ≤ j ≤ i − 1)
Initially, every L[i] is assigned as 1 and every Pre[i] is assigned as 0, representing that in the initial state the there’s only b[i] itself in the longest descending subsequence.
Traverse from i=1 … n. For each i, we inspect each 1 ≤ j < i. If b[j]>b[i], b[i] could be added to the longest descending subsequence ended with b[j] and if the length L[j]+1 is larger than L[i], we update L[i] and Pre[i] because there is a better choice. In this way, after inspecting every j from 1 to i-1, we make sure L[i] and Pre[i] have been updated to the optimal situation. For i=1, though the traversal of j won’tstart, L[i]=1 and Pre[i]=0 is the correct result so our algorithm won’t be wrong.
After the traverse, we can get the answer by find out the maximum L[i] (defined as Ans). If we need to output the longest descending subsequence, we can easily find the i=Ans and Pre[i] would help us to find the subsequence. When the optimal subsequence is not unique, this method still works as long as we do the same thing to every i=Ans.
Algorithm
L1..n ← 1
PTe1..n ← 0
foT i = 1 → n
foT j = 1 → i − 1
if (b[j] > b[i])&(L[j] + 1 > L[i]
L[i] ← L[j] + 1
PTe[i] ← j
Ans ← max L1..n
If we need to output all longest descending subsequence, we use an array a1..Ans to store the subsequence.
Algorithm
foT i = Ans → n
if (L[i] == Ans)
t ← i
foT j = Ans → 1
a[j] ← b[t]
t ← PTe[t]
output a1..Ans
The time complexity is 0(n2).
2. Assume there’re n points indexed as 0,1,…,n-1. We might as well assume point 0 is the topmost point (as we would finish a loop, which is the exact topmost point wouldn’t change the result). Define the distance between point q and point q is c[p][q].
We use bit operation and a state number m to represent the points that we have passed. In a binary representation of m, “1” means we have passed this point and “0” means we haven’t. For example, assuming there’re 5 points (n=5) and we have passed point 1 and point 3,mwill be (01010)2 or (10)10 .
Define di,j (0 ≤ i ≤ (1 ≪ n) − 1,0 ≤ j ≤ n − 1) as the shortest length when we arrived at point jand the current state is i. Our result is the minimum d(1≪n)−1,t + c[t][0].
We use the following recurrence to calculate the optimal result of each state: d[(1 ≪ j) | i][j] = min {d[i][k] + c[k][j], d[(1 ≪ j) | i][j])
The time complexity is 0(n2 · 2n ).
Algorithm TSP(n)
m ← (1 ≪ n)
d1..m,0..n−1 ← INF
PTe0..n−1 ← −1
d1,0 ← 0
for i = 1 → m − 1
for j = 1 → n − 1
if (i&(1 ≪ j)) | (! (i&1)) continue; // If j has already been passed or the state doesn’t include the topmost point 0, we skip to the next iteration of the loop.
fork = 0 → n − 1
if (i&(1 ≪ k)) &(d[i][k] + c[k][j] < d[(1 ≪ j) | i][j])
d[(1 ≪ j) | i][j] ← d[i][k] + c[k][j]
PTe[j] ← k
Ans, T ← INF
for i = 0 → n − 1
if d[m − 1][i] + c[i][0] < ans
Ans ← d[m − 1][i] + c[i][0]
T ← i
return Ans, T
If we want to print the sequence of passed points:
Algorithm Output_Path(n,T)
p ← T
for i = n → 1
a[i] = p
p = PTe[p]
a[n + 1] ← 0
output a1..n+1
3. Define the distance from point p to point q as c[p][q]. If there is no edge(p,q), c[p][q] is assigned as INF.
Defined[k][i][j] as the the shortest path from i to j with k hops, and we assume the maximum hop length is m.
(1) Initialization: Except d[0][i][i] = 0 for 1 ≤ i ≤ n, d1..m, 1..n, 1..n = INF (2) For each k=1 tom,we consider all pairs (i,j):
d[k][i][j] = min(d[k][i][j], dist[k − 1][i][t] + c[t][j])
tis defined as an intermediate point and we traverse all the points in the graph except point i,j.
Algorithm Shortest_Path(n,m)
m ← (1 ≪ n)
d1..m, 1..n, 1..n ← INF
d0,i,i ← 0
fork = 1 → m
for i = 1 → n
for j = 1 → n
if (j == i) continue;
fort = 1 → n
if (t == i) | (t == j) continue;
d[k][i][j] ← min {d[k − 1][i][t] + c[t][j], d[k][i][j]}
For each hop length, we have to examine all pairs of (i,j) and for each (i,j), we have to introduce an intermediate point to calculate the shortest path.
Therefore, the complexity of this algorithm is 0(n3 · m).
4. Defined[i][j] as the minimum money to make sure Bob can win when the number to guess is between i and j. Then d[1][n] will be our answer.
d[i][j] = min{x + max{d[i][x − 1], d[x + 1][j]} , d[i][j]} for all i < x < j, 1 ≤ i ≤ j ≤ n
Because the minimum coins to make sure Bob can win would be the money under the worst situation, so we use the MAX of d[i][x-1] and d[x+1][j]. Because we want to get the optimal answer, i.e. the minimum amount of coins to win, so we use MIN to get the minimum d[i][j].
Algorithm Minimum_Coins(n,m)
d1..n, 1..n ← INF
di, i ← 0 for all 1 ≤ i ≤ n
for i = n → 1
for j = i → n
if (j == i) continue;
for x = i → j
d[i][j] ← min {x + max {d[i][x − 1], d[x + 1][j]}, d[i][j]}
return d[1][n]
The time complexity is 0(n3).
2024-01-06