# 5hw-dsa-yong-liu-fall-2019
## 1
clrs excersice 22.4-1

Show the ordering of vertices produced by TOPOLOGICAL-SORT when it is run on the dag of Figure 22.8, under the assumption of Exercise 22.3-2.

> 22.3-2
Show how depth-first search works on the graph of Figure 22.6. Assume that the
for loop of lines 5–7 of the DFS procedure considers the vertices in alphabetical
order, and assume that each adjacency list is ordered alphabetically. Show the
discovery and finishing times for each vertex, and show the classification of each
edge.

:::success
p,n,o,s,m,r,y,v,x,w,z,u,q,t.
:::
## 2
## 3

# Function to preprcess input mat[M][N].  
# This function mainly fills aux[M][N] 
# such that aux[i][j] stores sum 
# of elements from (0,0) to (i,j) 
def preProcess(mat): 

    aux = [ [0 for i in range(N)]  
               for j in range(M) ] 
      
    # Copy first row of mat[][] to aux[][] 
    for i in range(0, N, 1): 
        aux[0][i] = mat[0][i] 
  
    # Do column wise sum 
    for i in range(1, M, 1): 
        for j in range(0, N, 1): 
            aux[i][j] = mat[i][j] + aux[i - 1][j] 
  
    # Do row wise sum 
    for i in range(0, M, 1): 
        for j in range(1, N, 1): 
            aux[i][j] += aux[i][j - 1] 
            
    return aux

aux = preProcess(mat)

def sumQuery(aux, a, b, c, d): 

      
    res = aux[c][d] - aux[a - 1][d] - aux[c][b - 1] + aux[a - 1][b - 1] 
  
    return res 

ref=
https://www.geeksforgeeks.org/submatrix-sum-queries/

## 4

# A Dynamic Programming based Python3 program to  
# find minimum of coins to make a given change V 
  
# m is size of coins array (number of  
# different coins) 
def minCoins(coins, m, V): 

    INF = float('inf')
      
    # table[i] will be storing the minimum  
    # number of coins required for i value.  
    # So table[V] will have result 
    table = [0 for i in range(V + 1)] 
  
    # Base case (If given value V is 0) 
    table[0] = 0
  
    # Initialize all table values as Infinite 
    for i in range(1, V + 1): 
        table[i] = INF 
  
    # Compute minimum coins required  
    # for all values from 1 to V 
    for i in range(1, V + 1): 
          
        # Go through all coins smaller than i 
        for j in range(m): 
            if (coins[j] <= i): 
                sub_res = table[i - coins[j]] 
                if (sub_res < INF and 
                    sub_res + 1 < table[i]): 
                    table[i] = sub_res + 1
    return table[V] 

print-out
https://github.com/y56/proving-ground/blob/master/coin-change-dp/print.out
ref =
https://www.geeksforgeeks.org/find-minimum-number-of-coins-that-make-a-change/

## Exercises from CLRS Textbook: 15.1-3, 15.4-3, 15-1, 16.1-1
## Exercise 15.1-3
>Consider a modification of the rod-cutting problem in which, in addition to a price p[i]​ for each rod, each cut incurs a fixed cost of $c$. The revenue associated with a solution is now the sum of the prices of the pieces minus the costs of making the cuts. Give a dynamic-programming algorithm to solve this modified problem.

MODIFIED-CUT-ROD(p, n, c)

    # creat a table
    let r[0..n] be a new array  
    
    # no rod no profit
    r[0] = 0
    
    
    for j = 1 to n  # query for every length, bottom up 
    
        q = p[j]  # profit for no-cut 
        
        # compare aomong all kinds of cut-out, p[i]
        # use table to find the profit of the residual rod, r[j - i]
        for i = 1 to j - 1
        
            # update to find the max
            q = max( q, 
                        p[i] + r[j - i] - c)  # to cut or not to cut, cuts cost
            
        r[j] = q
        
    return r[n]

## Exercise 15.4-3
:::danger
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
:::
Give a memoized version of LCS-LENGTH that runs in $O(mn)$ time.

MEMOIZED-LCS-LENGTH(X, Y, i, j)
    if c[i, j] > -1
        return c[i, j]
    if i == 0 or j == 0
        return c[i, j] = 0
    if x[i] == y[j]
        return c[i, j] = LCS-LENGTH(X, Y, i - 1, j - 1) + 1
    return c[i, j] = max(LCS-LENGTH(X, Y, i - 1, j), LCS-LENGTH(X, Y, i, j - 1))

## Problem 15-1

> Suppose that we are given a directed acyclic graph $G = (V, E)$ with real-valued edge weights and two distinguished vertices $s$ and $t$ . Describe a dynamic-programming approach for finding a longest weighted simple path from $s$ to $t$. What does the subproblem graph look like? What is the efficiency of your algorithm?

Since any longest simple path must start by going through some edge out of $s$, and we cannot later pass through $s$ because it must be simple, that is,
$$
\text{LONGEST}(G, s, t) =
\max_{s'}(
\text{weight}(s,s') +
\text{LONGEST}
(G', s', t)
)
$$
where $s'$ is connected by $s$ and $G'$ is $G$ without $s$

with the base case that if $s = t$ then we have a length of $0$.

Since the graph $G'$ we are considering is a subset of $G$, and the other two arguments $s'$ and $t$ in the substructure are distinguished vertices, then, the runtime will be $O(|V|^2 2^{|V|})$.
:::danger
???
:::

Though a DAG can't be a complete graph, we can consider it for upper bound of time complexity.

In such case, we have to pick up one vertex from $(|V|-i)$ vertices for the $i$-th time with $i = 1 \sim (|V|-1)$. And there are $\sum_{k=1}^{(|V|-i} k!$ paths to compare in the $i$-th time.
:::danger
???
:::

ref =
https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/
https://www.geeksforgeeks.org/longest-path-in-a-directed-acyclic-graph-dynamic-programming/
https://www.geeksforgeeks.org/longest-path-directed-acyclic-graph-set-2/
https://www.geeksforgeeks.org/longest-path-between-any-pair-of-vertices/
## Exercise 16.1-1
> Give a dynamic-programming algorithm for the activity-selection problem, based on recurrence (16.2). Have your algorithm compute the sizes c[i, j] as defined
above and also produce the maximum-size subset of mutually compatible activities.

$S_{ij}$
: the set of activities that start after activity $a_i$ finishes and that finish before activity $a_j$ starts.

$c[i,j]$
: the size of an optimal solution for the set $S_{ij}$

$a_k$
: We assume that the activities are sorted
in monotonically increasing order of finish time

DYNAMIC-ACTIVITY-SELECTOR(s, f, n)
    let c[0..n + 1, 0..n + 1] and act[0..n + 1, 0..n + 1] be new tables
    for i = 0 to n
        c[i, i] = 0      # S_i_i   is empty
        c[i, i + 1] = 0  # S_i_i+1 is empty
    c[n + 1, n + 1] = 0  # S_i_i   is empty
    
    take n = 3
    c is
    [0, 0, -, -, -]
    [~, 0 ,0 ,-, -]
    [~ ,~ ,0 ,0, -]
    [~ ,~ ,~ ,0, 0]
    [~ ,~ ,~ ,~, 0]
    '~' positions are never used
    
    for l = 2 to n + 1  # 2~4
        for i = 0 to n - l + 1  # 0~4-l ## 0~2 ## 0~1 ## 0~0
            
            j = i + l
            c[i, j] = 0  # [0,2] [1,3] [2,4] => [0,3] [1,4] => [0,4]
            # to scan diagonals from middl to up-right 
            
            k = j - 1 
            while f[i] < f[k]  # while a_k \in S_{ij} 
                if f[i] ≤ s[k] and f[k] ≤ s[j] and c[i, k] + c[k, j] + 1 > c[i, j]
                    c[i, j] = c[i, k] + c[k, j] + 1  # update max
                    act[i, j] = k  # record the intermediate a_k, who produce a max
                k = k - 1
                
    print "A maximum size set of mutually compatible activities has size" c[0, n + 1]
    # the final answer is on the up-right corner
    
    print "The set contains"
    PRINT-ACTIVITIES(c, act, 0, n + 1)
    # track back by k

# It's like printing a tree
PRINT-ACTIVITIES(c, act, i, j)
    if c[i, j] > 0
        k = act[i, j]
        
        PRINT-ACTIVITIES(c, act, i, k)
        print k  # in-order style
        PRINT-ACTIVITIES(c, act, k, j)
# the print-out is not in a_k sorting order

GREEDY-ACTIVITY-SELECTOR runs in $\Theta(n)$ time and
DYNAMIC-ACTIVITY-SELECTOR runs in $O(n^3)$ time.