Algorithm to compute a minimum cover time and space, Programming Languages

Given strings s1 and s2 of lengths m and n respectively, a minimum cover of s1 by s2 is a decomposition s1 = w1w2 .... wk, where each wi is a non-empty substring of s2 and k is minimized. Eg., given s1 = accgtatct and s2 = cgtactcatc, there are several covers of s1 by s2 possible, two of which are:

(i) cover1: s1 = w1w2w3w4 (where w1 = ac, w2 = cgt, w3 = atc, w4 = t) , and

(ii) cover2: s1 = w1w2w3w4w5 (where w1 = ac, w2 = c, w3 = gt, w4 = atc, w5 = t).

However, only cover1 is a minimal cover. Give an algorithm to compute a minimum cover (if one exists) in O (m + n) time and space. If a minimum cover does not exist your algorithm should state so and terminate within the same time and space bounds. Give a brief justification of why you think your algorithm is correct - meaning, how it guarantees finding the minimial cover (if one exists).

Posted Date: 3/28/2013 6:25:52 AM | Location : United States







Related Discussions:- Algorithm to compute a minimum cover time and space, Assignment Help, Ask Question on Algorithm to compute a minimum cover time and space, Get Answer, Expert's Help, Algorithm to compute a minimum cover time and space Discussions

Write discussion on Algorithm to compute a minimum cover time and space
Your posts are moderated
Related Questions
n2=2:100; t=3; while t { g3(t)=(1/2)*(0.63)*(0.8.^(n2)); t=t+1; } g3(1)=0; g3(2)=0; what is wrong with the code above? it tells me that line: g3(t)=(1/2)

I need help programming an arduino uno to scan an ean-8 student barcode and display their name and id on computer. This is a capstone project.

You get a contract to implement a simple Java application that process NBA team roster : your application has to read the NBA team roster from a text file and then print each playe

Area Under Curve Write a program to find the area under the curve y = f(x) between x = a and x = b, integrate y = f(x) between the limits of a and b. The area under a curve be

Computers and Programming Concept 1. Classify computer systems according to capacity. How they are different from computers according to the classification of technology. Provi

In this Project your task is to create a program that displays various levels of the fractal structure of the so called square shaped Sierpinski-carpet. The display of level 4 is s

Define the The if statement - Computer Programming? The if statement is an influential selection statement and is used to control the flow of execution of statements. One of th

Translate the following formula into a prefix form expression in Scheme: Question 2 Define a procedure that takes three numbers as arguments and returns the sum of the squ

1. Write a shell script to locate executable files. This script takes a list of file names from the command line and determines which would be executed had these names been given a

How to make game in pascal language