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
In the form of hypermedia documents, Web pages or materials accessed by the Internet can be located anywhere in the world. Regardless of where they originated, most of the Web d

Normal 0 false false false EN-US X-NONE X-NONE MicrosoftInternetExplorer4

(a) Write a recursive procedure (digits n) that computes the number of digits in the integer n using a linear recursive process. For example, (digits 42) should return 2 and (digit

Normal 0 false false false EN-US X-NONE X-NONE MicrosoftInternetExplorer4

1. You are working as a designer for a university that offers a program in Computer Science. One of the tracts is computer security. One of your colleagues has recommended adding a

EF308 Assignment 2 Due: 3pm, 26 April 2012 Introduction This assignment is loosely based on Cheung et al. (2005) and Molodtsova and Papell (2009) and examines the out-of- sample pr

I need to do image reconstruction using Neural Network using Matlab

write a program to sort the file sequential order and store on magnetic tape and print sorted tape as the output of the program.

Operation • This application uses an Alligator class that implements a Countable interface to display Alligator objects as shown above. • This application uses a Sheep class that i

Your task will be to code a simulation of image compression based on the approximate low rank structure of the set of image patches. You will write functions .code = my block compr