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.
- 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.
- 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]=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);
}
}