amit shekhar

Longest Increasing Sequence

2011-04-18T04:01:00.000-07:00

The Longest Increasing Subsequence problem is to find the longest increasing subsequence of a given sequence.

Formally, the problem is as follows:

Given a sequence a1, a2, ... an, find the largest subset such that for every

i < j

a i < a j

Example: 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 # sequence
0, 2, 6, 9, 13, 15 # longest increasing subsequence (not unique)

Using Back-Tracking technique:

--A sequence of integers is either empty or, an integer followed by a sequence of integers.
--The only subsequence of the empty sequence is the empty sequence.
--A subsequence of A[1 .. n] is either a subsequence of A[2 .. n] or A[1] followed by a subsequence of A[2..n]

The Algorithm:
The LIS of A[1 .. n] is: either the LIS of A[2 .. n] or, A[1] followed by the LIS of A[2 .. n] with elements larger than A[1], whichever is longer.

If A[1] <= x,

the LIS of A[1 .. n] with elements larger than x is the LIS of A[2 .. n] with elements larger than x. Otherwise,

the LIS of A[1 .. n] with elements larger than x is either the LIS of A[2 .. n] with elements larger than x

or,

A[1] followed by the LIS of A[2 .. n] with elements larger than A[1], whichever is longer.

Simple to Understand Algorithm:

A simple way of finding the longest increasing subsequence is to use the Longest Common Subsequence (Dynamic Programming) algorithm.
Make a sorted copy of the sequence A, denoted as B. O(nlog(n)) time.
Use Longest Common Subsequence on with A and B. O(n2) time.

PS: You may look up at my previous post on LCS/DP here

C++ Code :

#include <vector>
using namespace std;
 
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
void find_lis(vector<int> &a, vector<int> &b)
{
 vector<int> p(a.size());
 int u, v;
 
 if (a.empty()) return;
 
 b.push_back(0);
 
 for (size_t i = 1; i < a.size(); i++) 
    {
      // If next element a[i] is greater than last element of                          current longest subsequence a[b.back()], just push it at                      back of "b" and continue
      if (a[b.back()] < a[i]) 
                {
      p[i] = b.back();
      b.push_back(i);
      continue;
  }
 
       // Binary search to find the smallest element referenced by b which is        just bigger than a[i]
       // Note : Binary search is performed on b (and not a). Size of b is           always <=k and hence contributes O(log k) to complexity.    
  for (u = 0, v = b.size()-1; u < v;) 
  {
     int c = (u + v) / 2;
     if (a[b[c]] < a[i]) u=c+1; else v=c;
  }
 
  // Update b if new value is smaller then previously referenced value 
  if (a[i] < a[b[u]]) 
  {
   if (u > 0) p[i] = b[u-1];
   b[u] = i;
  } 
 }
 
 for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
}
 
/* Example of usage: */
#include <cstdio>
int main()
{
 int a[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };
 vector<int> seq(a, a+sizeof(a)/sizeof(a[0])); // seq : Input Vector
 vector<int> lis;                              // lis : Vector containing                                                    indexes of longest subsequence 
 find_lis(seq, lis);
 
 //Printing actual output 
 for (size_t i = 0; i < lis.size(); i++)
    printf("%d ", seq[lis[i]]);
 printf("\n");    
 
 return 0;

Edit Distance | Dynamic Programming contd...

2011-04-13T23:44:00.000-07:00

The algorithm thought process:

F O O D (m = 4)
M O N E Y (n = 4)

While travelling distance here we'll encounter either of these four for any pair of chars. As usual a Brute-Force will ask us to visit and compare m*n times - taking into consideration of all permutations of the characters.

Deletion: Delete Y

Change: Change F to M

Insertion:

Same Character: Nothing to be done

You may recall DP as:
Dynamic Programming Hallmark #1:
OPTIMAL SUBSTRUCTURE - An optimal Solution to a problem (or an instance of problem) contains optimal solution to a subproblem.
Dynamic Programming Hallmark #2:
OVERLAPPING SUBPROBLEMS - A recursive solution contains a small number of distinct subproblems repeated many times.

Like my previous post for calculating Longest Common Subsequence, we can define a recursive method on the same line. Later, we can use a table to store and look-up and update the values[ the distance between the words]

Source Code:
// myProject.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <string>
#include <vector>
#include <algorithm>
#include <fstream>
#include <iostream>
#include "BaseClass.h"
using namespace std;

int EDITDISTANCE(const char A[], const char B[], int m, int n)
{
int Edit[20][20] = {0, };
for(int j = 0; j < n; j++)
Edit[0][j] = j;
for(int j = 0; j < m; j++)
Edit[j][0] = j;
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= n; j++)
{
if (A[i] == B[j])
Edit[i][j] = std::min( std::min( Edit[i-1][j] + 1, Edit[i][j-1] + 1), Edit[i-1][j-1] );
else
Edit[i][j] = std::min( std::min( Edit[i-1][j] + 1, Edit[i][j-1] + 1), Edit[i-1][j-1] + 1);
}
}
return Edit[m][n];
}

int _tmain(int argc, _TCHAR* argv[])
{
char A[] = "ALGORITHM";
char B[] = "ALTRUISTIC";
printf("%d\n", EDITDISTANCE(A, B, 9, 10));

printf("Hello World!");
return 0;
}

For ease try visualizing the table.
References:

Dynamic Programming | Longest Common Subsequence

2011-04-13T23:23:00.000-07:00

For the shake of chapter notes let me put forward the hallmarks of solving problem using Dynamic Programming.

Dynamic Programming Hallmark #1:

OPTIMAL SUBSTRUCTURE - An optimal Solution to a problem (or an instance of problem) contains optimal solution to a subproblem.

Dynamic Programming Hallmark #2:

OVERLAPPING SUBPROBLEMS - A recursive solution contains a small number of distinct subproblems repeated many times.

Enough stated before I explain a bit. Actually, any problem where one can see subproblem to a problem[or a problem instance] and that there is fair chance of solving the same using Brute-Force Algorithm can be solved by applying Dynamic Programming Concepts. One may go for recursive methods to solve such problem - But that's going to be a Brute-Force method. A word of caution here as there is a lot of possibility that one can't solve problems using Brute-Force method, leaving alone the efficient ones. So, after we are done with a recursive solution we can look at the recursion tree of those solvable problems. In most of the cases there is a fair chance that a small number of distinct subproblems will be repeated many times. As I go forward I'll explain how Longest Common Subsequence[LCS] problem's recursion tree has repeated subproblems. So, there comes Dynamic programming techniques for the rescue. Its second Hallmark, stated above, implies that One can avoid those subproblems getting computed again and again by saving those results. Though, it raise memory constraint but it reduces the computing overhead drastically - and more often, It provides an only way to solve for even moderately large n.

LCS:

X = A B C B D A B (Length m = 7)

Y = B D C A B A (Length n = 6)

Xi = {x1, x2, ... xi}

Length[i,j] = LCS value

Recursive Algo for LCS [merely, a brute force method]:

Here the thought lies as if the LCS of k-1th long string is known then we compare kth character of the string with each character of other string. If it matches then that means LCS can be increased by 1. If that does not match then assign LCS as maximum of Length[k-1-1, j] and Length[k-1, j-1] where j is the index of current character under consideration of 2nd string.

LCS(x, y, i, j)

for i = 1 to m

for j = 1 to n

if x[i] = y[j]

then Length[i, j] <- LCS (x, y, i-1, j-1) + 1

else Length[i, j] <- max ( LCS ( x, y, i-1, j), LCS( x, y, i, j -1) )

return Length[i, j]

As evident from Recursion tree, the height is (m+n) and so time reqd = 2 raised to (m+n) with a lot of repeated subproblems

LCS(x,y,6,5) will be computed twice for instance.

DP gives us better solution.

As evident we always need either of these: LCS (x, y, i-1, j-1), LCS ( x, y, i-1, j) and LCS( x, y, i, j -1)

Therefore, we can store previous values at a 2D matrix and whenever needed we use previous value - based upon current characters under consideration - and populate new one.

That makes a small change to our previous Algorithm:

LCS(x, y, i, j)

for i = 1 to m

Length[0, i] <- 0

for i = 1 to n

Length[i, 0] <- 0

for i = 1 to m

for j = 1 to n

if x[i] = y[j]

then Length[i, j] <- LCS (x, y, i-1, j-1) + 1

else Length[i, j] <- max ( LCS ( x, y, i-1, j), LCS( x, y, i, j -1) )

return Length[i, j]

The value at Length[m,n] will have the final value. And the LCS is done.

For better visualization one can draw a table.

A B C B D A B

0 0 0 0 0 0 0 0

B0 0 1 1 1 1 1 1

D0 0 1 1 1 2 ...

C0 ...
A0

A0

References:

Amit | अमित

2011-04-13T21:22:00.000-07:00

In Hindi and Bengali, Amit (Hindi: अमित) means infinite or immeasurable or boundless. It is the wordstem root of the Amitabha Buddha and one of the 108 names of Hindu God Shri Ganesha. It also means an eternal friend of everyone in Hindi, Nepali and Sanskrit

In Hebrew, Amit (Hebrew: עמית‎) means colleague, friend.

In Arabic, Amit (Arabic: اميت‎) means being highly praised, beloved and victorious.

More...

Amitābha (Sanskrit: अमिताभ, Amitābha (wordstem), Hindi pronunciation: [əmɪˈt̪aːbʱə]) is a celestial buddha described in the scriptures of the Mahāyāna school of Buddhism. Amitābha is the principal buddha in the Pure Land sect, a branch of Buddhism practiced mainly in East Asia, while in VajrayanaAmitābha is known for his longevity attribute and the aggregate of distinguishing (recognition) and the deep awareness of individualities. According to these scriptures, Amitābha possesses infinite merits resulting from good deeds over countless past lives as a bodhisattva named Dharmakāra. "Amitābha" is translatable as "Infinite Light," hence Amitābha is often called "The Buddha of Infinite Light."