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

C programming, Write an interactive C program which prompts the user with t...

Write an interactive C program which prompts the user with the following options on the opening menu: 1) Student information 2) Theory counselling batch-scheduling

Fortran source code, For this programming assignment, you are to develop a ...

For this programming assignment, you are to develop a Fortran 90/95/2003 program to automate a useful task. The aim of the assignment is for you to reveal your competence in the Fo

Shell script, find value of nCr using function

find value of nCr using function

C++ programing, how to rewrite C++ program the DNAStrand class (DNA Project...

how to rewrite C++ program the DNAStrand class (DNA Project) to instead store the nucleotide sequence in a dynamically-allocated array?

and gate- or gate-logical-program , System.in and System.out should not be...

System.in and System.out should not be used anywhere in the programs except in main and only for testing purposes.  All calculations should be done in a method.  Note:  To use J

Html code to create a web page design , 1.  Develop HTML code to create a W...

1.  Develop HTML code to create a Web page with the red background and title "My First Page" in any other color. 2.  Develop an HTML document with details of your name, telephon

Create a structure that will represent a deck of cards, We want to create a...

We want to create a structure that will represent a deck of cards  (not necessarily full). Each card has a character (between  '2'  to  '9' and  'T',  'J',  'Q',  'K',  'A') and a

Basics of html-hypertext markup language, In the form of hypermedia documen...

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

Assembly language program, a program that enter an alphabet from the user a...

a program that enter an alphabet from the user and compare it is vowel or not?

Need support in mobile app using angularjs and cordova, Need support in Mob...

Need support in Mobile app using AngularJS, Cordova (PhoneGap), Ionicframework We need an experienced front-end developer with a obsession for performance in mobile environment.

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