# 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:

8074

24,13,12,7,5,3,1

Sample Output:

338

Solution

Coin.java

import java.io.*;

importjava.util.*;

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];

table=0;

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

LCS.java

import java.io.*;

importjava.util.*;

import java.io.*;

importjava.util.*;

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;

//mismatch++;

else

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);

}

}