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

Assignment Help:

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


Related Discussions:- Algorithm to compute a minimum cover time and space

Assignment, Assignment for Networing&camunication

Assignment for Networing&camunication

Write a program to read a text file and create a dictionary, Write a progra...

Write a program to read a text file and create a dictionary. The keys for the dictionary should be all 26 letters of the alphabet and the values of the dictionary should be the lis

C# xna game project, I am working on a game project using C# XNA. I only h...

I am working on a game project using C# XNA. I only have two weeks from the deadline. Would you help me to finish it up? Please let me know as soon as possible. Thanks, Sophi

Basics question, I am building wpf application and i want to install this a...

I am building wpf application and i want to install this application on a server pc and share it to other pces on a net work , my question is i have static class that contain data

Create application for a book store, You need to create a simple applicatio...

You need to create a simple application for the Note Plus book Store. The interface for the application is shown below:   REQUIRED: 1)  Create all necessary contro

Software application, Does anyone know anything about java programming here...

Does anyone know anything about java programming here?

Explain the continue statement - computer programming, Explain the Continue...

Explain the Continue statement - Computer Programming? This is alike to break but is encountered less frequently. It merely works within loops where its effect is to force an imm

Cobol 85, Open error message coming out when compiling

Open error message coming out when compiling

insertion sort algortihm, Define a higher order version of the insertion s...

Define a higher order version of the insertion sort algortihm. That is define functions insertBy :: Ord b => (a->b) -> a -> [a] -> [a] inssortBy :: Ord b => (a->b) -> [a] ->

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd