Skip to content

Design Techniques II

All Pairs Shortest Path

Floyd Warshall Algorithm - Time complexity -> O(\(n^3\)) - When we call the algorithm for the \(i^{th}\) vertex, all the paths for vertex i will remain the same i.e the \(i^{th}\) row and \(i^{th}\) column will be as it is from the previous matrix. and all the 0-diagonals will be the same as well. - The formula for updating the shortest path here is: \(\(A^k[i,j] = min\{ A^{k-1}[i,j], A^{k-1}[i,k] + A^{k-1}[k,j] \}\)\) For example, \(\(A^1[i,j] = min\{ A^{0}[i,j], A^{0}[i,k] + A^{0}[k,j] \}\)\) - Repeat the above algorithm for all the empty cells of the matrix and fill up the matrix - Do the above procedure for all vertex from 1..n. - At the end of \(n^{th}\) iteration you will have the matrix with shortest path to all the nodes from all the other nodes!

0-1 Knapsack using tabulation and set method

  • Input
    • knapsack size m
    • profit array and weight array of size n

  • Steps

    1. create a table of size (m+1)*(n+1) for including 0 as well
    2. Initialize 0's row and column to 0
    3. for all cells use the following formula\(\(A[i,j]\ = \ max\{A[i-1,j],A[i-1,j-w[i]] + p[i]\}\)\)where i -> items and j -> weight After you have filled all the cells, the second problem is how to extract which items were put into the knapsack
    4. Choose the last entry in the table you filled, check the \(i-1^{th}\) entry to see if the value is the same.
      • Go to the first occurrence of the number.
      • When you get to the first occurrence, that row's item is to be included in the knapsack, and subtract the item's profit from the current number
      • Repeat the above steps till you reach 0.
    Set Method
    • We prepare a set of order pair (profit, weight)
    • Initial set \(S_0\) ={0,0}
    • then create \(S^0_1\) by adding first item to the \(S_0\)
    • we keep doing this till we get to the \(S^{n-1}_n\)
    • Meanwhile in the process discard any sets where the weight > maxWeight and wherever the weight to profit pattern is broken
    • At the end backtrack using the costliest element and try to find in which Set is it present from last to first.
    • the set in which it appears first is the item to be included in hte knapsack, and subtract the item's weight,profit value from the current element

Travelling Salesperson Problem

  • \[g(i,s) = min\{C_{ik} + g(k,s-{k})\}$$Where $i$ is the current element, and $s$ is the remaining element's set. E.g.$$g(2,\{3,4\}) = min\{c(2,3) + g(3,\{4\}) \ \ , \ \ c(2,4) + g(4,\{3\})\}\]

Chain Matrix Multiplication

  • Given n matrices, to be multiplied, return minimum number of multiplications to be done in minimum.\(\(m[i,j]\ = \ min\{m[i,k] + m[k+1,j] + d_{i-1}*d_{k}*d_{j}\}\)\)
  • To calculate the formula for multiplication, use the S table that you prepared, at every step of finding m[i,j] put the value of k as the deciding break point in the S table
  • At the end use the values in S table's 1st row to decide at what point to split the multiplication at every instance

Longest Common Subsequence

  • given to strings, return the largest common subsequence
  • Algo
    1. if characters match i.e. s1[i] == s2[j] then c(i,j) = c(i-1,j-1)+1 (give diagonal up arrow)
    2. else
      1. if(c[i-1][j] >= c[i][j-i]) -> c[i][j] = c[i-1][j] (give up arrow)
      2. else c[i][j] = c[i][j-1] (give left arrow)
  • To get the lcs string
  • from the last box traverse with the max value, when you encounter the diagonal arrow, include the current character and go diagonally up and repeat till you reach 0

Bellman Ford Algorithm

  • You relax all edges repeatedly n-1 times
    • Where n is the number of vertices
  • Relaxation -> if(d[u]+c(u,v) < d[v]) -> update distance of v to new value
  • Form a list of all edges, and then relax them all (n-1) times
  • Time Complexity O(|V| |E|) or O(\(n^2\)) if we consider v,e = n
    • Bell man ford does not work with cycles, the moment you add a cycle.
  • A bellman ford algo can detect negetive weight cycle, after relaxing n-1 time, we will relax one more time, if the costs change, then there is a negative weight cycle!!

Cutting a rod

  • Goal -> Maximize the profit
  • Input -> 2d Array of size 2xn size of the cut, profit for cut
  • draw a table of size rodLength+1 (o.....rodLength) x (n+1) (o..size of the cut)
  • rod length -> | size (downwards arrow)
  • Calculate and fill the table, at the end return the values in the set by reiterating through the dp table from end to back!

Subset Sum problem

  • Goal -> get the subset that matches the target sum
  • Input -> array of size n, targetSum
  • draw at table of size sum(0...targetSum --->) x elements(downwards)
  • Fill using DP

  • Reverse traverse from the end till 0, subtract current element from current sum when there is F in the parent and current element is T. Include current element. repeat till current element/current sum = 0

  • Algo``` 

    if(j < input[j])
    A[i[j] = A[i-1][j]
else
    A[i][j] = A[i-1][j] || A[i-1][j-input[i]]

Optimal Binary Search Tree

  • Given keys and their frequency, what will be the optimal BST for the given input
  • Input -> 2 Arrays of size n, keys and Frequency
  • Initialisation
    • Table of size nxn
    • all diagonals = 0
  • Formula:\(\(C[i,j]\ = \ min\{ c[i,k-1] + c[k,j]\} + w(i,j)\)\)w(i,j) excludes the ith value i.e. w(0,2) = w[1] + w[2]
  • After calculating the entire table with the root values for the node, construct the tree as follows
  • Take the root value of the last node of the 0th row. That is the root of the whole tree
    • now make two children for the root from (0 to rootvalue-1) , (rootValue to n)!
    • Repeat the process for the children