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

Write a recursive procedure that computes number in integer, (a) Write a re...

(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

Define call by value - computer programming, Define Call by value - Compute...

Define Call by value - Computer Programming? Functions are raise by writing their name and an appropriate list of arguments within parenthesis. Usually these arguments are in t

Learning when and how to use a while loop, 1.  A function that produces the...

1.  A function that produces the Collatz sequence and counts the number of terms. 2.  A main function that calculates interesting values about the Collatz sequence. 1.The Col

Double roots, This case will lead to similar problem that we've had all oth...

This case will lead to similar problem that we've had all other time we've run in double roots or double eigenvalues. We only find a single solution and will require a second solut

Develop a diagram to model functionality, Develop (i) a context diagram, an...

Develop (i) a context diagram, and (ii) a use case diagram to model the following functionalities of an online brokerage house. eBroker is a discount online broker. An account h

Explain why the simplifiled knapsack code is not secure, 1- If the order of...

1- If the order of a (mod P) is 3, prove that the order of a+1 is 6. 2- Explain why the "simplifiled knapsack" code is not secure.

Pattern matching program in xhtml, Part 1 Given the following Regular Exp...

Part 1 Given the following Regular Expressions, explain in detail the pattern accepted by each. Pay attention to all the characters being used. Your answers need not appear with

Class Project, I need help getting started with a class project of creating...

I need help getting started with a class project of creating a project in the Perl programming language. I was thinking of maybe doing an employee directory

Shell script to remove colons from a colon–separated record, Normal 0 ...

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

Create hijara game application, Assignment is to create hijara game on any ...

Assignment is to create hijara game on any plate form, you can use any plate form you like or easy to you. For instance let's say you can use visual studio, game studio (Prefer to

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