Local sequence alignment

Local sequence alignment

Problem 1.

Write a program that solves the Local Sequence Alignment problem using dynamic programming.

The input includes strings v, w and a scoring matrix δ. The output is an alignment of v and w whose score (as defined by the matrix δ) is maximal among all possible alignments of v and w.

  1. Run your program to find the optimal local alignment for 1213434222 and 1343422421 under the match premium +1, mismatch penalty -1, and indel penalty -0.5.
  2. Submit your source code and screenshots of a sample run showing the correct output of your algorithm when given v = 1213434222 and w = 1343422421.

Problem 2.

Find the minimum number of coins needed to make change.

Given: An integer money and an array Coins of positive integers.

Return: The minimum number of coins with denominations Coins that changes money.

Sample Input:



Sample Output:




import java.io.*;


public class Coin


// m is size of coins array (number of different coins)

staticintminCoins(int coins[], int m, int V)


int[] table = new int[V+1];


for(int i=1;i<=V;i++)


table[i] =Integer.MAX_VALUE;


for(int i=1;i<=V;i++)


for(int j =0;j<=i)


intsub_res = table[i-coins[j]];

if (sub_res != Integer.MAX_VALUE&&sub_res + 1 < table[i])

table[i] = sub_res + 1;




return table[V];


public static void main(String args[])


Scanner in = new Scanner(System.in);

int value = in.nextInt();

int n = in.nextInt();

int coins[] = new int[n];

for(int i=0;i


import java.io.*;


import java.io.*;


public class LCS{

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */

staticintlcs( char[] X, char[] Y, int m, int n ){

int L[][] = new int[m+1][n+1];

int match =0;

int mismatch =0;

/* Following steps build L[m+1][n+1] in bottom up fashion. Note

that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */

for (int i=0; i<=m; i++){

for (int j=0; j<=n; j++){

if (i == 0 || j == 0)

L[i][j] = 0;

else if (X[i-1] == Y[j-1])

L[i][j] = L[i-1][j-1] + 1;



L[i][j] = Math.max(L[i-1][j], L[i][j-1]);



return L[m][n];


public static void main(String[] args){

//LongestCommonSubsequencelcs = new LongestCommonSubsequence();

String s1 = “1213434222”;

String s2 = “1343422421”;

char[] X=s1.toCharArray();

char[] Y=s2.toCharArray();

int m = X.length;

int n = Y.length;

int match = lcs( X, Y, m, n );

int mismatch = m-match;

intpenality =0;

int score = match-mismatch;

System.out.println(“#matchs = “+match);

System.out.println(“#mismatchs = “+mismatch);

System.out.println(“#score = “+score);