#include<iostream>
#include<cstdlib>
using namespace std;
int compare(const void* a, const void* b)
{
const int* x = (int*) a;
const int* y = (int*) b;
if (*x > *y)
return 1;
else if (*x < *y)
return -1;
return 0;
}
double SmallestKMean(int A[], int n, int k)
{
//First need to sort the array
// Then find mean from first k smallest element in array
int total = 0;
qsort(A, n, sizeof(int),compare);
for(int i=0;i<k;i++){
total += A[i];
}
return total/k;
}
int main(int argc, char const *argv[])
{
int n=10, k =5;
int A[10] = {10,5,11,234,143,87,987,1,2,76};
cout << SmallestKMean(A,n,k);
return 0;
}
//output:
b)
#include <iostream>
#include<stdlib.h>
using namespace std;
# define NO_OF_CHARS 256
/*Algorithm
bad-Shift Table
Seq: T A A T C A G G A A A G C G T A A T A A T A A T A
Pat: T A A T A A
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 21 22 23
we start match from the last char of pattern and we find that index 4 is mismatch.
mismatching char is C is not in pattern So we will shift pattern past to index 5
Seq: T A A T C A G G A A A G C G T A A T A A T A A T A
Pat: T A A T A A
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 21 22 23
we start match from the last char of pattern and we find that index 11 is mismatch.
mismatching char is G is not in pattern So we will shift pattern past to index 10
Seq: T A A T C A G G A A A G C G T A A T A A T A A T A
Pat: T A A T A A
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 21 22 23
we start match from the last char of pattern and we find that index 13 is mismatch.
mismatching char is G is in pattern.
Now we will search for last occurence of G in pattern. which is not in Pattern
so we will move by last mismatch char which is at 13
Seq: T A A T C A G G A A A G C G T A A T A A T A A T A
Pat: T A A T A A
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 21 22 23
Now we got the pattern matched.
*/
void badCharHeuristic( string str, int size, int badchar[NO_OF_CHARS])
{
int i;
// Initialize all occurrences as -1
for (i = 0; i < NO_OF_CHARS; i++)
badchar[i] = -1;
// Fill the actual value of last occurrence of a character
for (i = 0; i < size; i++)
badchar[(int) str[i]] = i;
}
int findPattern( string txt, string pat)
{
int m = pat.size();
int n = txt.size();
int badchar[NO_OF_CHARS];
/* Fill the bad character array by calling
the preprocessing function badCharHeuristic()
for given pattern */
badCharHeuristic(pat, m, badchar);
int s = 0; // s is shift of the pattern with respect to text
while(s <= (n - m))
{
int j = m - 1;
/* Keep reducing index j of pattern while
characters of pattern and text are
matching at this shift s */
while(j >= 0 && pat[j] == txt[s + j])
j--;
/* If the pattern is present at current
shift, then index j will become -1 after
the above loop */
if (j < 0)
{
return s;
}
else
/* Shift the pattern so that the bad character
in text aligns with the last occurrence of
it in pattern. The max function is used to
make sure that we get a positive shift.
We may get a negative shift if the last
occurrence of bad character in pattern
is on the right side of the current
character. */
s += max(1, j - badchar[txt[s + j]]);
}
return -1;
}
/* Driver code */
int main()
{
string txt= "TAATCAGGAAAGCGTAATAATAATA";
string pat = "TAATAA";
cout << "First Pattern fount at index::" << findPattern(txt, pat);
return 0;
}
//output:
b) Design a presorting-based algorithm to find the smallest possible mean of k elements in an array of n elements. Algorithm SmallestKMean (AI1. .n], k) c)Consider the problem of searching for genes...
Consider the problem of searching for genes in DNA sequences. ADNA sequence is represented by a text on the alphabet A, C, G, T, and the gene or gene segment is the pattern. Pattern: TCCTATTCTT Text: TTATAGATCTCGTATTCTTTTATAGATCTCCTATTCTT a. Construct the good suffix table of the pattern for the Boyer-Moore algorithm. b. Apply Boyer-Moores algorithm to locate the pattern in the text c. Construct the table and a diagram of the FSM used by the KMP algorithm
Consider the problem of searching for genes in DNA sequences. A DNA sequence is represented by a text on the alphabet A, C, G, T, and the gene or gene segment is the pattern. Pattern: TCCTATTCTT Text: TTATAGATCTCGTATTCTTTTATAGATCTCCTATTCTT Construct the table and a diagram of the FSM used by the KMP algorithm.
and w Two-dimensional gel electrophoresis separates proteins based on a. shape; charge Ob.size; concentration c. concentration; shape O d. size, charge O e. size; shape Refer to the table. Several strains of a bacterium are sequenced to investigate the pan and core genomes. In the table, + denotes presence of the gene and denotes its absence. Gene Gene Gene Gene Gene Strain ! Strain 2 + Strain 3 + Strain 4 + + + + Strain 5 + + What...