Dynamic Programming Practise Problem Set 3

1. Calculate M = M1 × M2 × M3 × M4, where the dimensions of the matrices are

M1: 10,20       M2: 20,50       M3: 50,1       M4: 1,100

a) Calculating M = M1 × ( M2 × ( M3 × M4 ) )
b) Calculating M = ( M1 × ( M2 × M3 ) ) × M4

2 Calculate the length of longest sub string in Hello and Aloha

3. Calculate longest sub sequence in  houseboat and computer.
Answers
1 a) 125000
   b)  2200

2
       A L O H A

    H  0 0 0 1 0
    E  0 0 0 0 0
    L  0 1 0 0 0
    L  0 1 0 0 0
    O  0 0 2 0 0
3.  out     is a common subsequence of     houseboat     and     computer .

Read More

Longest common substring problem

Given two sequences of letters, such as A = HELLO and B = ALOHA,
find the longest contiguous sequence appearing in both.

One solution:   (assume strings have lengths m and n)
For each of the m starting points of A, check for the longest common string starting at each of the n starting points of B.

The checks could average Θ(m) time → a total of Θ(m^2*n) time.

Dynamic programming solution:
Let Li, j = maximum length of common strings that end at A[i] & B[j].   Then,

Li, j  =  0 if i = 0 or j = 0
        =    Li-1, j-1 + 1 if A[i] = B[j]
        = 0                   if A[i] != B[j]
     

int LONGEST_COMMON_SUBSTRING(A,m,B,n)
{
  if (m==0 || n ==0) return 0;  
  for i = 0 to m
                   L[i,0] = 0
    for j = 0 to n
                  L[0,j] = 0
    len = 0 ;
    answer = L[0,0];
    for i = 1 to m do
       for j = 1 to n do
          if A[i] != B[j]
             L[i,j ]  = 0;
          else
             Li,j = 1 + L[i-1,j-1];
             if L[i,j] > len then
                len := Li,j
               
}
Example:

       A L O H A

    H  0 0 0 1 0
    E  0 0 0 0 0
    L  0 1 0 0 0
    L  0 1 0 0 0
    O  0 0 2 0 0

Read More

Dynamic Programming Practise Problem Set 2

1. 1. Below is a dynamic programming solution for this problem to illustrate how it can be used. There is a very straightforward O(1) time solution. It can be shown that इफ n >= 50 then any solution will include a set of coins that adds to exactly 50 cents.
   Hence it can be shown that an optimal solution uses 2 · [n/50 ] quarters along with un optimal solution for making n/50 − bn/50c cents which can be looked up in a table ऑफ़ size 50.
   Here’s the dynamic programming solution for this problem. (It does not use the फक्त that an optimal solution can be proven to use 2 · bn/50c quarters and hence is not अस efficient.) The general subproblem will be to make change for i cents for 1 i n. Let
   c[i] denote the fewest coins needed to make i cents. Then we can define c[i] recursively
   by:
   c[i] =
   8><
   >:
   use i pennies if 1 i < 9
   c[i − 10] + 1 if 10 i < 24
   min(c[i − 10] + 1, c[i − 25] + 1) if i 25
   Note that c[n] is the optimal number of coins needed for the original problem.
   Clearly when i < 10 the optimal solution can use only pennies (since that is the
   only coin available). Otherwise, the optimal solution either uses a dime or a quarter
   and both of these are considered. Finally, the optimal substructure property clearly
   holds since the final solution just adds one coin to the subproblem solution. There
   are n subproblems each of which takes O(1) time to solve and hence the overall time
   complexity is O(n).
2. Recall that D1 is a DNA sequence with n1 characters and D1 is a DNA sequence with
   n2 characters. The general form of the subproblem we solve will be: Find the best
   alignment for the first i characters of D1 and the first j characters of D2 for 1 i n1
   and 1 j n2. Let D(i) be the ith character in string D. Let c[i, j] be the cost of
   an optimal alignment for D1(1), . . . ,D1(i) and D2(1), . . . ,D2(j). We can define c[i, j]
   recursively as shown (where c[n1, n2] gives the optimal cost to the original problem):
   c[i, j] =
   8>>><
   >>>: i
   if j
   =
   0
   j if i = 0
   c[i − 1, j − 1] if D1(i) = D2(j)
   min{c[i − 1, j − 1], c[i − 1, j], c[i, j − 1]} + 1 otherwise
   
   We now argue this recursive definition is correct. You can form D01 and D02 (and hence
   the alignment) for the subproblem from the right to left as follows. In an optimal
   alignment either the last character of D01 is a space or it is the last character (character
   i) of D1 and the last character of D02 is a space or it is the last character (character
   j) of D2. If D1(i) = D2(j) then clearly it is best to align them (so add a space to
   neither). However, if D1(i) 6= D2(j) then a space could be added to neither or just
   one. In all three cases one mismatch is caused by the last characters. Notice that
   there would never be any benefit in ending both D1 and D2 with a space. Hence the
   above recursive definition considers all possible cases that the optimal alignment could
   have. Since the solution to the original problem is either the value of the subproblem
   solution (if D1(i) = D2(j)) or otherwise one plus the subproblem solution, the optimal
   substructure property clearly holds. Thus the solution output is correct.
   For the time complexity it is clearly O(n1 · n2) since there are n1 · n2 subproblems each
   of which is solved in constant time. Finally, the c[i, j] matrix can be computed in row
   major order and just as in the LCS problem a second matrix that contains which of
   the above 4 cases was applied can also be stored and then used to construct an optimal
   alignment.
3. Let m[i] be the rental cost for the best solution to go from post i to post n for 1 i n.
   The final answer is in m[1]. We can recursively, define m[i] as follows:
   m[i] =
   8<
   :
   0 if i = n
   min
   i
   (fi,j + m[j]) otherwise
   We now prove this is correct. The canoe must be rented starting at post i (the starting
   location) and then returned next at a station among i + 1, . . . , n. In the recurrence
   we try all possibilities (with j being the station where the canoe is next returned).
   Furthermore, since fi,j is independent from how the subproblem of going from post
   j, . . . , n is solved, we have the optimal substructure property.
   For the time complexity there are n subproblems to be solved each of which takes
   O(n) time. These subproblems can be computed in the order m[n],m[n−1], . . . ,m[1].
   Hence the overall time complexity is O(n2).
   NOTE: One (of several) alternate general subproblem form that also leads to an O(n2)
   algorithm is to find the best solution to get from post i to post n where the canoe
   cannot be exchanged until post j is reached (for 1 i < j n).
4. The general form of the subproblem we solve will be: determine if z1, . . . , zi+j is an
   interleaving of x1, . . . , xi and y1, . . . yj for 0 i m and 0 j n. Let c[i, j] be
   true if and only if z1 . . . , zi+j is an interleaving of x1, . . . , xi and y1, . . . , yj . We use the
   convention that if i = 0 then xi = (the empty string) and if j = 0 then yj = . The
   subproblem c[i, j] can be recursively defined as shown (where c[m, n] gives the answer
   
   to the original problem):
   c[i, j] =
   8>>>>>><
   >>>>>>:
   true if i = j = 0
   false if xi 6= zi+j and yj 6= zi+j
   c[i − 1, j] if xi = zi+j and yj 6= zi+j
   c[i, j − 1] if xi 6= zi+j and yj = zi+j
   c[i − 1, j] _ c[i, j − 1] if xi = yj = zi+j
   We now argue this recursive definition is correct. First the case where i = j = 0 is
   when both X and Y are empty and then by definition Z (which is also empty) is a
   valid interleaving of X and Y . If xi 6= zi+j and yj = zi+j then there could only be a
   valid interleaving in which xi appears last in the interleaving, and hence c[i, j] is true
   exactly when z1, . . . , zi+j−1 is a valid interleaving of x1, . . . , xi−1 and y1, . . . yj which is
   given by c[i − 1, j]. Similarly, when xi 6= zi+j and yj = zi+j then c[i, j] = c[i − 1, j].
   Finally, consider when xi = yj = zi+j . In this case the interleaving (if it exists) must
   either end with xi (in which case c[i − 1, j] is true) or must end with yi (in which
   case c[i, j − 1] is true). Thus returning c[i − 1, j] _ c[i, j − 1] gives the correct answer.
   Finally, since in all cases the value of c[i, j] comes directly from the answer to one of
   the subproblems, we have the optimal substructure property.
   The time complexity is clearly O(nm) since there are n ·m subproblems each of which
   is solved in constant time. Finally, the c[i, j] matrix can be computed in row major
   order.

Read More

Matrix chain multiplication

Problem
Given a sequence of n matrices M₁, M₂, ... M_n, and their dimensions p₀, p₁, p₂, ..., p_n, where where i = 1, 2, ..., n, matrix M_i has dimension p_{i − 1} × p_i, determine the order of multiplication that minimizes the the number of scalar multiplications.

We wish to determine the value of the product ∏i = 1 to n Mi, where Mi has ri-1 rows and ri columns.

The order of which matrices are multiplied together first can significantly affect the time required.

To multiply M×N, where matrix M is p×q and matrix N is q×r, takes pqr operations if we use the "normal" matrix multiplication algorithm.   Note that the matrices have a common dimension value of q.   This makes the matrices have the property of compatibility, without which it would not be possible for them to be multiplied.   Also note that, while matrix multiplication is associative, matrix multiplication is not commutative.   That is, N×M might not equal M×N and, in fact, N×M might not even be defined because of a lack of compatibility.

Example 1
Compute  A * B * C * D
A = 30 × 1, B =  1 × 40, C =  40 × 10, D =  10 × 25

Multiplication order (A * B) * (C * D) requires
= M1 * M2 = (30 X 40 ) * (40  X 25)
= 30 * 1 * 40 + 40 * 10 * 25 + 30 * 40 * 25
        = 41, 200 multiplications.

Multiplication order A * ((B * C) * D) requires
= A * (M1 * D) = A * M2
1 * 40 * 10 + 1 * 10 * 25 + 30 * 1 * 25 = 1, 400 multiplications.
where M1 = (1 X 10) matrix = B*C = 1 * 40 * 10, M2 = (1 X 25 ) matrix = 1 * 10 * 25
and A*M2 = (30 X 25) = 30*1*25

Example 2

Calculate M = M1 × M2 × M3 × M4,
where the dimensions of the matrices are
M1: 10,20       M2: 20,50       M3: 50,1       M4: 1,100

Calculating M = M1 × ( M2 × ( M3 × M4 ) ) requires 125000 operations.
=M1 * (M2 * (50*1*100)) = M1 * (20 * 50

Calculating M = ( M1 × ( M2 × M3 ) ) × M4 requires 2200 operations.

We could figure out how many operations each possible order will take and then use the one having the minimum number of operations, but there are there are an exponential number of orderings.   Any of the n-1 multiplications could be first and then any of the remaining n-2 multiplications could be next and so on, leading to a total of (n-1)! orderings.

We can find the best order in time O(n^3) by using dynamic programming.

Matrix-Chain-Order(p){
n  = p.length - 1;
for (i from  1 to n)
 m[i, i]  =  0
for (l = 2 to n) // l is the chain length.
 for (i = 1 to n − l + 1){
  j=i + l − 1;
  m[i, j]=1;
  for (k=i to j − 1){
    q=m[i, k] + m[k + 1, j] + p[i-1]*p[k]*p[j]
    if q < m[i, j]){
     then m[i, j]=q
    s[i, j]=k
    }
  }  
 }
 return m and s
 }

In the above listing, length refers to the number of matrix multiplications in a subproblem. An alternative approach would be to use size (equal to length+1) as the number of matrices in the subproblem.

Here is java code:

private void matrixChainOrder(int[] p)
{
 int n = p.length - 1; // how many matrices are in the chain
 int[][] m = new int[n+1][n+1]; // overallocate m, so that we don't use index 0
 int[][] s = new int[n+1][n+1]; 
 
 // Initial the cost for the empty subproblems.
 for (int i = 1; i <= n; i++)
  m[i][i] = 0;

 // Solve for chains of increasing length l.
 for (int l = 2; l <= n; l++) {
  for (int i = 1; i <= n-l+1; i++) {
  int j = i + l - 1;
  m[i][j] = Integer.MAX_VALUE;

  // Check each possible split to see if it's better
  // than all seen so far.
  for (int k = i; k < j; k++) {
   int q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];
   if (q < m[i][j]) {
   // q is the best split for this subproblem so far.
   m[i][j] = q;
   s[i][j] = k;
   }
  }
  }
 }
}

For the example given above, we would calculate:
m1,1 = 0,   m2,2 = 0,   m3,3 = 0,   m4,4 = 0
m1,2 = 10000,   m2,3 = 1000,   m3,4 = 5000
m1,3 = 1200,   m2,4 = 3000
m1,4 = 2200

Read More

Dynamic Programming Practise Problem Set 1

1.  Suppose we want to make change for n cents, using the least number of coins of denominations 1, 10, and 25 cents. Describe an O(n) dynamic programming algorithm to find an optimal solution. (There is also an easy O(1) algorithm but the idea here is to illustrate dynamic programming.)
2.   Here we look at a problem from computational biology. You can think of a DNAsequence as sequence of the characters “a”,”c”,”g”,”t”. Suppose you are given DNA sequences D1 of n1 characters and DNA sequence D2 of n2 characters. You might want to know if these sequences appear to be from the same object. However, in obtaining the sequences, laboratory errors could cause reversed, repeated or missing characters. This leads to the following sequence alignment problem. An alignment is defined by inserting any number of spaces in D1 and D2 so that the resulting strings D01 and D02 both have the same length (with the spaces included as part of the sequence). Each character of D01 (including each space as a character) has a corresponding character (matching or non-matching) in the same position in D02. For a particular alignment A we say cost(A) is the number of mismatches (where you can think of a space as just another character and hence a space matches a space but does not match one of the other 4 characters). To be sure this problem is clear suppose that D1 is ctatg and D2 is ttaagc. One possible alignment is given by: ct at g tta agc In the above both D01 and D02 have length 8. The cost is 5. (There are mismatches in position 1, 3, 5, 6 and 8). Give the most efficient algorithm you can (analyzed as a function of n1 and n2) to compute the alignment of minimum cost. 1 
3. You are traveling by a canoe down a river and there are n trading posts along the way. Before starting your journey, you are given for each 1 i < j n, the fee fi,j for renting a canoe from post i to post j. These fees are arbitrary. For example it is possible that f1,3 = 10 and f1,4 = 5. You begin at trading post 1 and must end at trading post n (using rented canoes). Your goal is to minimize the rental cost. Give the most efficient algorithm you can for this problem. Be sure to prove that your algorithm yields an optimal solution and analyze the time complexity.
4.  For bit strings X = x1 . . . xm, Y = y1 . . . yn and Z = z1 . . . zm+n, we say that Z is an interleaving of X and Y if it can be obtained by interleaving the bits in X and Y in a way that maintains the left-to-right order of the bits in X and Y . For example if X = 101 and Y = 01 then x1x2y1x3y2 = 10011 is an interleaving of X and Y , whereas 11010 is not. Give the most efficient algorithm you can to determine if Z is an interleaving of X and Y . Prove your algorithm is correct and analyze its time complexity as a function m = |X| and n = |Y |.

Read More

Prim's Algorithm

This algorithm was first propsed by Jarnik, but typically attributed to Prim. It starts from an arbitrary vertex (root) and at each stage, add a new branch (edge) to the tree already constructed, much like a mould. The algorithm halts when all the vertices in the graph have been reached.

To understand the problem statement refer here.

This is similar to  djikstra's algorithm where we were clear where to begin with as we were given the source vertex, but here we have to choose arbitrarily.

This strategy is greedy in the sense that at each step the partial spanning tree is augmented with an edge that is the smallest among all possible adjacent edges.

Example
Lets start with following graph:

Lets start with edge 1 to begin with, covering 2 nodes.

We can now select the edge with min weight between 3 edges - 2,3,4. Lets select 2 as it is min.

Now we have 3 edges - 3 ,4 and 5, from the nodes that we have visited, so lets take 3 as it is minimum, but it doesn't add any new node, so we just discard it. (Marker in the below diagram means that we are just covering it)

Now we have 2 options of edges - 4 or 5, and as 4 is minimum we select it, it adds the last nodes also to the visited nodes, and hence prim's algo is complete.

So edges 1,2 and 4 make MST.

MST-PRIM

Input: A weighted, undirected graph G=(V, E, w)
Output: A minimum spanning tree T.

T={}

Let r be an arbitrarily chosen vertex from V.

X = {r}

WHILE | U| < n

DO

Find u in X and v in V-X such that the edge (u, v) is a smallest edge between X-V.

T = T U{(u, v)} //add u,v to T

X= X U {v}    //add v to vertices covered set U

Analysis
The algorithm spends most of its time in finding the smallest edge. So, time of the algorithm basically depends on how  do we search this edge.

Adjacency list analysis
Just find the smallest edge by searching the adjacency list of the vertices in V. In this case, each iteration costs O(m) time, yielding a total running time of O(mn) OR O(|E|.|V|).

Adjacency matrix analysis

Can we do better?
We will focus on adjacency lists only. Can we do better? Answer is yes. As we saw in the main WHILE loop, we are getting the minimum of the edge lengths crossing the frontier, and getMin() of heap will be very useful, which will speed up repeated getMin() elements on the edges.

Heap operation costs

• Insert element ----- O(log n)
• Get Min element ----O(log n)

More on heap - here.

This is similar to djikstra''s algo where we stored edges, but here we have to vertices.

Prim's Algorithm with Binary heap
By using binary heaps, the algorithm runs in O(m log n).

Invariant 1 : elements in the heap will be vertices   i.e. vertices of V-X
Invariant 2 : for v ∈ V-X, key[v] = cheapest edge (u,v) with u ∈ X. If this edge don't exists, put infinity.

Check - Can initialize heap with O (m+log n) = O(m log n) preprocessing.

Now we have to make sure that above 2 variants hold when we execute WHILE loop.
 So, first variant will hold as we have initialized the heap with vertices only.

Making the 2nd variant
eg.

when v added to X{
  foreach edge (v,w) in E {
     if(w belongs to V-X){
        Delete w from heap
        Recompute key[w] = min ([key[1], (v-w))
        re-insert into heap
     }
}

This ensures that 2nd variant holds. Deleting the vertex at some position is little tricky, so we have to do some book keeping to keep the index of the vertex as well.

Analysis:

• n-1 Inserts during pre-processing
• n-1 extract min (one per iteration while loop)
• each edge (v,w) triggers one delete/insert combo, implies O(m) time.

So, overall O(m log n) time.

Fibonacci heap
By using Fibonacci heaps, the algorithm runs in O(m + n log n) = O (m log n)

Correctness of Prim's algorithm
 Theorem - Prim's algorithm always computes an MST.

Part 1 - Prim's algorithm atleast computes a spanning tree T*
Part 2 - T* is an MST

To be done later.

Read More

Kruskal's Algorithm

In kruskal's algorithm the selection function chooses edges in increasing order of length without worrying too much about their connection to previously chosen edges, except that never to form a cycle. The result is a forest of trees that grows until all the trees in a forest (all the components) merge in a single tree. graph

Example

In Kruskal's algorithm, we sort the edges according to their edge weights and start counting them and including them in MST, if they are not forming any cycle.
Consider the graph:

So, we begin with the edge with lowest edge cost or weight, and change its color, making it part of spanning tree:

Likewise we add edge 2, and see if there is no cycle, then we are fine to go.

Now we add edge 3 and see if there is cycle, as there is no cycle, we are good to go.

Now we add edge 4, as it is next in sorted list of edges, but now the issue is it is making cycle, so we ignore it.

Now we add edge 5, and it is good to go, and is part of MST

Now we know that all the vertices are covered and hence it is the MST now.

Now lets see the pseudocode.
Pseudocode

Sort the edges in order of increasing cost
[Rename the edges 1,2,3,....,m so that c1 < c2 < c3 ....< cm]
T = {}

for i=1 to m {
   if ( T[i] has no cycles)
      add i to T

return T

Running time of straightforward implementation
Here is the running time  :

• Sorting of edges - O (m log n) [Actually sorting takes O(m log m), but m is nearly O(n2) ]
• Checking if the cycle exists, is actually checking if there is already a path between vertices u and v, which are end points of the new edge. If there is already exists, this will create a cycle. But how do we check if there is path between u and v - answer is BFS or DFS (breadth first search or depth first search). This will take max of O(n-1) vertices scan, and hence O(mn)
• So total running time = O(m log n) + O(mn)

 So, here the bummer is checking the cycle which is taking long time, and union find datastructure can help us solving this where it will return the cycle in constant time.

Implementing Kruskal Algorithm via Union-Find
Raise detre of union find data structure - Is to maintain partition of a set of objects.
Operation supported - Union and Find
Find(x) - return the name of group that x belongs to? eg. C3
Union (Ci Cj) - fuse group Ci and Cj into a single one.

Why useful for kruskal algorithm?
 When kruskal algorithm starts, all the edges are by themselves, with separate component in itself. so, when the edge is joined to the tree, the 2 components are connected. Suppose in Kruskal algorithm, the Tree has 4 connected components, and edge is coming with u,v vertices, with u in C1 and v in C2, hence 2 components join.
So, union find will contain the vertices as objects, and groups are connected components w.r.t currently connected edges.

Idea 1 : Maintain one linked structure per connected component of (V,T) , with each component has an arbitrary leader.

Invariant - each vertex points to the leader of its component

Key point - given edge (u,v) , we can check if u and v already in the same component in O(1) time (if and if only if leader pointer of u and v match)

Maintaining the variant problem
Also, if leaders dont match, we add to add the edge. But while adding the edge, we have to make sure that invariant of having 1 component pointing to 1 leader holds. In the worst case, it may take linear time to maintain the leader. So, again for each edge, it will lead to O(m.n) time, which is a issue. How to solve this?

To solve this lets have an idea 2:
Idea 2 : When two components merge, we should retain leader of 1 of the components, which will save us from pointer manipulation of atleast 1 component. Now suppose component A has 100 nodes, and B has 1000 nodes, so we have to keep the leader from component B as we have to then only re-write leader for 100 nodes of group A.

But still it doesn't solve our problem, as it will still take O(n) time for 1 edge to merge. Hence again O(m.n) times.

Idea 3 :
Now lets solve this problem in some other way - Lets think it in terms of each vertex term. Suppose that each vertex points to itself in start as there are n disconnected components to begin with. Now each time an edge is added, this vertex may or may not change its leader. So, how many times does a single vertex have its leader pointer update over the course of kruskal's algorithm? Answers is θ (log n).How?
So, when does  the vertex gets updated, when your component of say 20 vertices gets united with some other component of similar size. So, each time 2 components are united we have upper bound of  < = log 2 n times.

Running time of fast implementation

• Sorting - O(m log n ) time for sorting
• O (m) time for cycle check [O (1)  time for each edge, or per iteration - Idea 1)
• O (n log n) time overall for leader pointer updates (Using idea 3)

So, bottleneck for Kruskal algorithm is sorting ~ which is O(m log n) ie. O (|E| log |V|)

Read More

Dynamic-Programming Algorithm for the Activity-Selection Problem

Problem: Given a set of activities to among lecture halls. Schedule all the activities using minimal lecture halls.
In order to determine which activity should use which lecture hall, the algorithm uses the GREEDY-ACTIVITY-SELECTOR to calculate the activities in the first lecture hall. If there are some activities yet to be scheduled, a new lecture hall is selected and GREEDY-ACTIVITY-SELECTOR is called again. This continues until all activities have been scheduled.

LECTURE-HALL-ASSIGNMENT (s,f)

n = length [s)
FOR i = 1 to n
        DO HALL [i] = NIL
k = 1
WHILE (Not empty (s))
        Do HALL [k] = GREEDY-ACTIVITY-SELECTOR (s, t, n)
                k = k + 1
RETURN HALL

Following changes can be made in the GREEDY-ACTIVITY-SELECTOR (s, f) (CLR).

j = first (s)
A = i
FOR i = j + 1 to n
    DO IF s(i) not= "-"
            THEN IF

GREED-ACTIVITY-SELECTOR (s,f,n)
j = first (s)
A = i = j + 1 to n
        IF s(i] not = "-" THEN
            IF s[i] >= f[j]|           
                THEN A = A U {i}
                            s[i] = "-"
                                j = i
return A

CORRECTNESS:
The algorithm can be shown to be correct and optimal. As a contradiction, assume the number of lecture halls are not optimal, that is, the algorithm allocates more hall than necessary. Therefore, there exists a set of activities B which have been wrongly allocated. An activity b belonging to B which has been allocated to hall H[i] should have optimally been allocated to H[k]. This implies that the activities for lecture hall H[k] have not been allocated optimally, as the GREED-ACTIVITY-SELECTOR produces the optimal set of activities for a particular lecture hall.

Analysis: 
In the worst case, the number of lecture halls require is n. GREED-ACTIVITY-SELECTOR runs in θ(n). The running time of this algorithm is O(n2).

Observe that choosing the activity of  least duration will not always produce an optimal solution. For example, we have a set of activities {(3, 5), (6, 8), (1, 4), (4, 7), (7, 10)}. Here, either (3, 5) or (6, 8) will be picked first, which will be picked first, which will prevent the optimal solution of {(1, 4), (4, 7), (7, 10)} from being found.
Also observe that choosing the activity with the least overlap will not always produce solution. For example, we have a set of activities {(0, 4), (4, 6), (6, 10), (0, 1), (1, 5), (5, 9), (9, 10), (0, 3), (0, 2), (7, 10), (8, 10)}. Here the one with the least overlap with other activities is (4, 6), so it will be picked first. But that would prevent the optimal solution of  {(0, 1), (1, 5), (5, 9), (9, 10)} from being found.

Read More

An Activity Selection Problem ( Greedy Approach)

An activity-selection is the problem of scheduling a resource among several competing activity.

Statement: Given a set S of n activities with and start time, Si and fi, finish time of an ith activity. Find the maximum size set of mutually compatible activities.

Compatible Activities
Activities i and j are compatible if the half-open internal [si, fi) and [sj, fj) do not overlap, that is, i and j are compatible if si ≥ fj  and sj ≥ fi
Greedy Algorithm for Selection Problem

I. Sort the input activities by increasing finishing time.
f1 ≤  f2 ≤ . . . ≤  fn

II Call GREEDY-ACTIVITY-SELECTOR (Sif)
n = length [s]
A={i}
j = 1
FOR i = 2 to n
        do if  si ≥ fj
            then A= AU{i}
                    j = i
Return A

Operation of the algorithm
Let 11 activities are given S = {p, q, r, s, t, u, v, w, x, y, z} start and finished times for proposed activities are (1, 4), (3, 5), (0, 6), 5, 7), (3, 8), 5, 9), (6, 10), (8, 11), (8, 12), (2, 13) and (12, 14).

A = {p} Initialization at line 2
A = {p, s} line 6 - 1st iteration of FOR - loop
A = {p, s, w} line 6 -2nd iteration of FOR - loop
A = {p, s, w, z} line 6 - 3rd iteration of FOR-loop
Out of the FOR-loop and Return A = {p, s, w, z}

Analysis
Part I requires O(nlgn) time (use merge of heap sort).
Part II requires Theta(n) time assuming that activities were already sorted in part I by their finish time.

CORRECTNESS
Note that Greedy algorithm do not always produce optimal solutions but GREEDY-ACTIVITY-SELECTOR does.

Theorem: Algorithm GREED-ACTIVITY-SELECTOR produces solution of maximum size for the activity-selection problem.

Proof Idea: Show the activity problem satisfied
I. Greedy choice property.
II. Optimal substructure property

Proof:
    I.  Let S = {1, 2, . . . , n} be the set of activities. Since activities are in order by finish time. It implies that activity 1 has the earliest finish time.
Suppose, A is a subset of S is an optimal solution and let activities in A are ordered by finish time. Suppose, the first activity in A is k.
If k = 1, then A begins with greedy choice and we are done (or to be very precise, there is nothing to proof here).
If k not=1, we want to show that there is another solution B that begins with greedy choice, activity 1.
Let B =  A - {k} U {1}. Because f1 =< fk, the activities in B are disjoint and since B has same number of activities as A, i.e., |A| = |B|, B is also optimal.

    II.  Once the greedy choice is made, the problem reduces to finding an optimal solution for the problem. If A is an optimal solution to the original problem S, then A` = A - {1} is an optimal solution to the activity-selection problem S` = {i in S: Si >= fi}.
why?

If we could find a solution B` to S` with more activities then A`, adding 1 to B` would yield a solution B to S with more activities than A, there by contradicting the optimality.

Read More

Dijkstra's Algorithm (Shortest Path)

Consider a directed graph G = (V, E).

Problem    Determine the length of the shortest path from the source to each of the other nodes of the graph. This problem can be solved by a greedy algorithm often called Dijkstra's algorithm.

The algorithm maintains two sets of vertices, S and C. At every stage the set S contains those vertices that have already been selected and set C contains all the other vertices. Hence we have the invariant property V=S U C. When algorithm starts Delta contains only the source vertex and when the algorithm halts, Delta contains all the vertices of the graph and problem is solved. At each step algorithm choose the vertex in C whose distance to the source is least and add it to S.

Read More

Dynamic-Programming Solution to the 0-1 Knapsack Problem

Problem Statement 0-1 Knapsack problem
Input :
There are n items, and each item has a value:

• value vi   (non negative)
• size or weight wi (non negative and integral )
• Capicity W (non negative and integer)

Output:
  Select a subset  S ⊆ {1,2,3,....n}

• that maximizes ∑ vi 
• subject to max value&sum wi ≤ W

 Sometimes you may hear a cheesy problem a thief robbing a store and can carry a maximal weight of W into their knapsack. There are n items and ith  item weigh wi and is worth vi dollars. What items should thief take?d

There are two versions of problem:

• Fractional knapsack problem   
• 0-1 knapsack problem   

Comparing Fractional Knapsack vs 0-1 Knapsack

Fractional knapsack problem
The setup is same, but the thief can take fractions of items, meaning that the items can be broken into smaller pieces so that thief may decide to carry only a fraction of xi of item i, where 0 ≤ xi ≤ 1.

Exhibit greedy choice property.

•          Greedy algorithm exists.
•          Exhibit optimal substructure property.

0-1 knapsack problem
The setup is the same, but the items may not be broken into smaller pieces, so thief may decide either to take an item or to leave it (binary choice), but may not take a fraction of an item.

So, the above problem statement holds for 0-1 knapsack problem as we are referring to integral wi.

• Exhibit No greedy choice property. No greedy algorithm exists.
• Exhibit optimal substructure property.
• Only dynamic programming algorithm exists.

Brute force method
Since there are n items, there are 2ⁿ possible combinations of items.
We go through all combinations and find the one with maximum value and with total weight less or equal to W
Running time will be O(2ⁿ)

Dynamic-Programming Solution to the 0-1 Knapsack Problem
The naive way to solve this problem is to cycle through all 2ⁿ subsets of the n items and pick the subset with a legal weight that maximizes the value of the knapsack. But, we can find a dynamic programming algorithm that will USUALLY do better than this brute force technique.

Now lets see the dynamic programming route.
 

Let S be the optimal solution S.
Let n be the last item in an optimal solution S for W pounds.

Defining the sub problem - try 1
Let’s try this:
If items are labeled 1..n, then a subproblem would be to find an optimal solution for
Sk = {items labeled 1, 2, .. k}

If items are labeled 1..n, then a subproblem would be to find an optimal solution for Sk = {items labeled 1, 2, .. k}

This is a reasonable subproblem definition.
The question is: can we describe the final solution (Sn ) in terms of subproblems (Sk)?
Unfortunately, we can’t do that.


Consider the following items:
n=5, W=20

i	Item	wi	vi or bi
1	I0	2	3
2	I1	4	5
3	I2	5	8
4	I3	3	4
5	I4	9	10

Consider W= 20. Lets try to take 1st 4 items, ie. S4 and 1st 5 items - S5.

So, clearly S4 is not sub part of S5, hence our solution is flawed.

Defining the sub problem try 2
The subproblem then will be to compute V[i,x], i.e., to find an optimal solution for Sk = {items labeled 1, 2, .. i} in a knapsack of size x. Now we have to derive V[i,x].

Case 1: Suppose n ∉ S (n not in S)
Then S must be optimal solution with first n-1 Items Ii.
Maximum value obtained by n-1 items and W weight (excluding nth item).

Case2 : Suppose n ∈ S (n is indeed in S)
If we remove the last item n, then S - {n} is the optimal solution w.r.t. the 1st n-1 items and capacitiy W - wn.

Let V_ix = value of the best solution on that :

1. uses only the first i items
2. has total size ≤ x

Value of nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (including nth item).

So, we have to keep track of how many items we have used and the total size.

for i ∈ {1,2,3,...n}  and any x

V_ix = MAX ( V_(i-1)x  , vi + V_{(i-1)x- wi} ) OR

So, in case 1, wi>x. Item i can’t be part of the solution, since if it was, the total weight would be > w, which is unacceptable.
In case 2, wi ≤ x. Then the item i can be in the solution, and we choose the case with greater value.

One quick edge case, if wi > x, then we cant use it, and we have Vix = V(i-1)x , we are using case 1.

Step2 - The sub problem
Recall W and weight wi are integers, therefore in the worst case each case of residual capacities x ∈ {0,1,2,...,W).

Let A = 2-D array - as we have to keep track of 2 things - what items we have to use and what capacity we have to respect.

//The corner case where we don't take item at all, 
//i.e. i=0, and A[item,x] = 0 where item=0
for x = 0 to W
     A[0,x] = 0

FOR i=1 to n
    DO c[i, 0] = 0
        FOR x=0 TO W
            A[i,x] = max ( A[i-1,x],A[i-1,x-wi]+vi )

Running time
Note on run time: Clearly the run time of this algorithm is O(nW), based on the nested loop structure and the simple operation inside of both loops. When comparing this with the previous O(2ⁿ), we find that depending on W, either the dynamic programming algorithm is more efficient or the brute force algorithm could be more efficient. (For example, for n=5, W=100000, brute force is preferable, but for n=30 and W=1000, the dynamic programming solution is preferable.)

Example
Lets take the example now.
Input:
n=4, W=5
 Elements (weight, benefit):
(2,3), (3,4), (4,5), (5,6)

Solution
Lets denote sub problem solution weight by w, instead of x.
Case 0 - When we have no items, so w=0

case 1 - When we have w=0, so we have to select no items

After discussing the corner cases, lets now solve the actual problem.

Knapsack in java

// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
   int i, w;
   int K[n+1][W+1];
 
   // Build table K[][] in bottom up manner
   for (i = 0; i <= n; i++)
   {
       for (w = 0; w <= W; w++)
       {
           if (i==0 || w==0)
               K[i][w] = 0;
           else if (wt[i-1] <= w)
                 K[i][w] = Math.max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
           else
                 K[i][w] = K[i-1][w];
       }
   }
 
   return K[n][W];
}
 
int main()
{
    int val[] = {60, 100, 120};
    int wt[] = {10, 20, 30};
    int  W = 50;
    int n = sizeof(val)/sizeof(val[0]);
    printf("%d", knapSack(W, wt, val, n));
    return 0;
}

Thanks

Read More

Find the nth Fibonacci number

Problem: Write the code for nth Fibonacci number.

Solution: There are basically two approaches to solving the Fibonacci problem. Lets looks at the definition of Fibonacci series first.

The Fibonacci series is defined as follows

F(n) = 0 for n = 0
       1 for n = 1
       F(n-1) + F(n-2) for n > 1

So, F(n) = F(n-1)+F(n-2) for n≥2and 1 otherwise.

There are couple of approach to solve this.

Solution 1 - Using Recursion
If we translate that to the C language we get:

int RecursiveFibonacci(int n)
{
    if(n == 0) return 0;
    if(n == 1) return 1;
    return RecursiveFibonacci(n-1) + RecursiveFibonacci(n-2);
}

Time Complexity: T(n) = T(n-1) + T(n-2) + θ(1) which is exponential.
We can observe that this implementation does a lot of repeated work (see the following recursion tree). So this is a bad implementation for nth Fibonacci number.

                         fib(5)   
                     /             \     
               fib(4)                fib(3)   
             /      \                /     \
         fib(3)      fib(2)         fib(2)    fib(1)
        /     \        /    \       /    \  
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \
fib(1) fib(0)

Solving the recurrence  - T(n) ≥ 2 T(n-2)
Now its simpler. We keep on multiplying until T(n-2) reduces to T(1) and this can happen in n/2 steps as we can subtract 2 from n, n/2 times.
Hence T(n) ≥ 2^n/2 * constant
T(n) = θ (2 ^n/2)

Extra Space: O(n) if we consider the fuinction call stack size, otherwise O(1).

Solution 2 - Top Down Dynamic Programming Solution
Now, whats the running time of the above program. It's horrible!! It's exponential. Why? We have a lot of duplicate work being done on each recursive call.

Typically when you are doing duplicate work, Dynamic Programming can come to rescue. Now, I don't want to go into too much detail on dynamic programming, but you have 2 approaches to Dynamic Programming. One is the bottom up approach and the second is called the top down approach. Calculating F(n) given F(n-1) would be a bottom up approach and calculating F(n) by recursively calling F(n-1) and F(n-2) would be top down. For a thorough treatment of dynamic programming see a Algorithms text or this wikipedia entry.

We can improve the above RecursiveFibonacci function by caching results of previous calculations. Doing this greatly reduces the number of recursive calls and improves the program efficiency. This is an example of top down dynamic programming.

int RecursiveFibonacci(int n)
{
    if(n == 0) return 0;
    if(n == 1) return 1;
   
    if(cache[n] == null)
      cache[n] = RecursiveFibonacci(n-1) + RecursiveFibonacci(n-2);
    return cache[n];
}

Memoization
Now in DP, we will use something called memorization, which is similar to cache above. We hold a memo of what state we have went through, and hence we end something like this:

memo = {} //empty dictionary
int DPFibonacci(int n)
{
    if(n in Memo) return Memo[n];
    
    if(n == 1) return 1;
   
    f = DPFibonacci(n-1)+DPFibonacci(n-2)
    Memo[n] = f;
      
    return Memo[n];
}

So, we see memoization is very similar to what we were talking about caching. So, we are calling fib(k) only once rather and saving it, rather than computing it again and again whenever fib(k) is called in case of recursive solution.
So, lets assume that each time we call DPFibonacci, we have recursion and as it is happening only once, lets assume its constant time, and for each element we are only calling recursion once, and hence time complexity here is O(n). This is top down approach.

Solution 3 -Bottom up DP
Now lets look at the bottom up dynamic programming approach. For a given n we would need to have F(n-1), F(n-2), F(n-3) ... F(0) already solved. In this case we'll start at the bottom and work our way up.

int GetFibonacci(int n)
{
    if(n == 0) return 0;
    if(n == 1) return 1;
   
    last1 = 0;
    last2 = 1;   
    ans = 0;

    for(int i=0; i < n-1; i++)
    {
       ans = last1 + last2;
       last1 = last2;
       last2 = ans; 
    }

    return ans;
}

We could have used a cache like we used in the top down approach, but all we really need is the last 2 results. We can get away with just using 2 variables. This is also an iterative solution which is better compared to the recursive one because of the absence of the stack overhead involved in recursive calls.
 Time Complexity: O(n)
Extra Space: O(1)

Method 4 ( Using power of the matrix {{1,1},{1,0}} )
This another O(n) which relies on the fact that if we n times multiply the matrix M = {{1,1},{1,0}} to itself (in other words calculate power(M, n )), then we get the (n+1)th Fibonacci number as the element at row and column (0, 0) in the resultant matrix.
The matrix representation gives the following closed expression for the Fibonacci numbers:

#include <stdio.h>
 
/* Helper function that multiplies 2 matricies F and M of size 2*2, and
  puts the multiplication result back to F[][] */
void multiply(int F[2][2], int M[2][2]);
 
/* Helper function that calculates F[][] raise to the power n and puts the
  result in F[][]
  Note that this function is desinged only for fib() and won't work as general
  power function */
void power(int F[2][2], int n);
 
int fib(int n)
{
  int F[2][2] = {{1,1},{1,0}};
  if (n == 0)
      return 0;
  power(F, n-1);
 
  return F[0][0];
}
 
void multiply(int F[2][2], int M[2][2])
{
  int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0];
  int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1];
  int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0];
  int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1];
 
  F[0][0] = x;
  F[0][1] = y;
  F[1][0] = z;
  F[1][1] = w;
}
 
void power(int F[2][2], int n)
{
  int i;
  int M[2][2] = {{1,1},{1,0}};
 
  // n - 1 times multiply the matrix to {{1,0},{0,1}}
  for (i = 2; i <= n; i++)
      multiply(F, M);
}
 
/* Driver program to test above function */
int main()
{
  int n = 9;
  printf("%d", fib(n));
  getchar();
  return 0;
}

ime Complexity: O(n)
Extra Space: O(1)
Method 5 ( Optimized Method 4 )
The method 4 can be optimized to work in O(Logn) time complexity. We can do recursive multiplication to get power(M, n) in the prevous method (Similar to the optimization done in this post)

#include <stdio.h>
 
void multiply(int F[2][2], int M[2][2]);
 
void power(int F[2][2], int n);
 
/* function that returns nth Fibonacci number */
int fib(int n)
{
  int F[2][2] = {{1,1},{1,0}};
  if (n == 0)
    return 0;
  power(F, n-1);
  return F[0][0];
}
 
/* Optimized version of power() in method 4 */
void power(int F[2][2], int n)
{
  if( n == 0 || n == 1)
      return;
  int M[2][2] = {{1,1},{1,0}};
 
  power(F, n/2);
  multiply(F, F);
 
  if (n%2 != 0)
     multiply(F, M);
}
 
void multiply(int F[2][2], int M[2][2])
{
  int x =  F[0][0]*M[0][0] + F[0][1]*M[1][0];
  int y =  F[0][0]*M[0][1] + F[0][1]*M[1][1];
  int z =  F[1][0]*M[0][0] + F[1][1]*M[1][0];
  int w =  F[1][0]*M[0][1] + F[1][1]*M[1][1];
 
  F[0][0] = x;
  F[0][1] = y;
  F[1][0] = z;
  F[1][1] = w;
}
 
/* Driver program to test above function */
int main()
{
  int n = 9;
  printf("%d", fib(9));
  getchar();
  return 0;
}

Time Complexity: O(log n)
Extra Space: O(Logn) if we consider the function call stack size, otherwise O(1).

Source - http://www.geeksforgeeks.org

Read More

Solve the Rat In A Maze problem using backtracking.

This is one of the classical problems of computer science. There is a rat trapped in a maze. There are multiple paths in the maze from the starting point to the ending point. There is some cheese at the exit. The rat starts from the entrance of the maze and wants to get to the cheese.

This problem can be attacked as follows.
Have a m*m matrix which represents the maze.

For the sake of simplifying the implementation, have a boundary around your matrix and fill it up with all ones. This is so that you know when the rat is trying to go out of the boundary of the maze. In the real world, the rat would know not to go out of the maze, but hey! So, initially the matrix (I mean, the maze) would be something like (the ones represent the "exra" boundary we have added). The ones inside specify the obstacles.


111111111111111111111
100000000000000000001
100000010000000000001
100000010000000000001
100000000100001000001
100001000010000000001
100000000100000000001
100000000000000000001
111111111111111111111



The rat can move in four directions at any point in time (well, right, left, up, down). Please note that the rat can't move diagonally. Imagine a real maze and not a matrix. In matrix language



Moving right means adding {0,1} to the current coordinates.

Moving left means adding {0,-1} to the current coordinates.

Moving up means adding {-1,0} to the current coordinates.

Moving right means adding {1,0} to the current coordinates.



The rat can start off at the first row and the first column as the entrance point.

From there, it tries to move to a cell which is currently free. A cell is free if it has a zero in it.

It tries all the 4 options one-by-one, till it finds an empty cell. If it finds one, it moves to that cell and marks it with a 1 (saying it has visited it once). Then it continues to move ahead from that cell to other cells.

If at a particular cell, it runs out of all the 4 options (that is it cant move either right, left, up or down), then it needs to backtrack. It backtracks till a point where it can move ahead and be closer to the exit.

If it reaches the exit point, it gets the cheese, ofcourse.

The complexity is O(m*m).



Here is some pseudocode to chew upon


findpath()
{
Position offset[4];
Offset[0].row=0; offset[0].col=1;//right;
Offset[1].row=1; offset[1].col=0;//down;
Offset[2].row=0; offset[2].col=-1;//left;
Offset[3].row=-1; offset[3].col=0;//up;

// Initialize wall of obstacles around the maze
for(int i=0; i < m+1;i++)
maze[0][i] = maze[m+1][i]=1; maze[i][0] = maze[i][m+1]=1;

Position here;
Here.row=1;
Here.col=1;

maze[1][1]=1;
int option = 0;
int lastoption = 3;

while(here.row!=m || here.col!=m)
{
//Find a neighbor to move
int r,c;

while (option <= LastOption)
{
r=here.row + offset[position].row;
c=here.col + offset[option].col;
if(maze[r][c]==0)break;
option++;
}

//Was a neighbor found?
if(option <= LastOption)
{
path->Add(here);
here.row=r;here.col=c;
maze[r][c]=1;
option=0;
}
else
{
if(path->Empty())return(False);
Position next;
Path->Delete(next);
If(new.row==here.row)
Option=2+next.col - here.col;
Else { option = 3 + next.row - here.col;}
Here=next;
}
return(TRUE);
}
}

Read More

Representing the Solution Space

This section presents an interface for the nodes of a solution space. By using an interface, we hide the details of the specific problem to be solved from the backtracking algorithm. In so doing, it is possible to implement completely generic backtracking problem solvers.
Although a backtracking algorithm behaves as if it is traversing a solution tree, it is important to realize that it is not necessary to have the entire solution tree constructed at once. Instead, the backtracking algorithm creates and destroys the nodes dynamically as it explores the solution space.
Program  defines the Solution interface. Each instance of a class that implements the Solution interface represents a single node in the solution space.

  
Program: Solution interface.


The Solution interface comprises the following properties:

IsFeasible

This get accessor returns true if the solution instance is a feasible solution to the given problem. A solution is feasible if it satisfies the problem constraints.

IsComplete

This get accessor returns true if the solution instance represents a complete solution. A solution is complete when all possible decisions have been made.

Objective

This get accessor returns the value of the objective function for the given solution instance.

Bound

This get accessor returns a value that is a lower bound (if it exists) on the objective function for the given solution instance as well as all the solutions that can possibly be derived from that instance. This is a hook provided to facilitate the implementation of branch-and-bound backtracking which is described in Section .

Successors

This get accessor returns an IEnumerable object that represents all of the successors (i.e., the children) of the given solution instance. It is assumed that the children of the given node are created dynamically.

Read More

Balancing Scales

Consider the set of scales  shown in Figure . Suppose we are given a collection of n weights, , and we are required to place all of the weights onto the scales so that they are balanced.

  
Figure: A set of scales.


The problem can be expressed mathematically as follows: Let represent the pan in which weight is placed such that

The scales are balanced when the sum of the weights in the left pan equals the sum of the weights in the right pan,


Given an arbitrary set of n weights, there is no guarantee that a solution to the problem exists. A solution always exists if, instead of balancing the scales, the goal is to minimize the difference between between the total weights in the left and right pans. Thus, given , our objective is to minimize where

subject to the constraint that all the weights are placed on the scales.
Given a set of scales and collection of weights, we might solve the problem by trial-and-error: Place all the weights onto the pans one-by-one. If the scales balance, a solution has been found. If not, remove some number of the weights and place them back on the scales in some other combination. In effect, we search for a solution to the problem by first trying one solution and then backing-up to try another.
Figure  shows the solution space  for the scales balancing problem. In this case the solution space takes the form of a tree: Each node of the tree represents a partial solution to the problem. At the root (node A) no weights have been placed yet and the scales are balanced. Let be the difference between the the sum of the weights currently placed in the left and right pans. Therefore, at node A.

  
Figure: Solution space for the scales balancing problem.


Node B represents the situation in which weight has been placed in the left pan. The difference between the pans is . Conversely, node C represents the situation in which the weight has been placed in the right pan. In this case . The complete solution tree has depth n and leaves. Clearly, the solution is the leaf node having the smallest value.
In this case (as in many others) the solution space is a tree. In order to find the best solution a backtracking algorithm visits all the nodes in the solution space. That is, it does a tree traversal . Section  presents the two most important tree traversals--depth-first  and breadth-first . Both kinds can be used to implement a backtracking algorithm.

Read More