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 program to decrypt encrypted messages, You are working for a crypto...

You are working for a cryptography department, where one of your jobs is to decipher intercepted messages that have been encrypted using a book cipher. The messages are sent by dif

C program with creation of child process using fork system, Problem 6. ...

Problem 6. Demonstrate how and when can you use the commands- vi, cat, chmod, grep, man, pwd, ps, kill, mkdir, rm demonstrating how and when the above 10 commands can be

Project , You get a contract to implement a simple Java application that pr...

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

Program converts character array to signed decimal integer, 1. Write a func...

1. Write a function that converts a character array to a signed decimal integer. Function prototype must be as follows: int asciiToInt( char *str, unsigned char* eflag) YOU MAY NO

Oracal Query, Find out the selling cost average for packages developed in P...

Find out the selling cost average for packages developed in Pascal

Cookies management with perl, One of the main strengths of the Perl program...

One of the main strengths of the Perl programming language are its powerful text manipulation features. In this assignment, you will put them to  use for writing a Perl program tha

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

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

Program for read minimum three command line arguments, 1. Write a program t...

1. Write a program that reads a minimum of three command line arguments and displays the program's results. a. Command Line arguments:  i. The first argument will be the program

What are relative urls, What are Relative URLS ? When a web browser re...

What are Relative URLS ? When a web browser reads an HTML document, it has a great deal of information about the document. This includes the protocol used to retrieve the docu

Computes the least squares fit of the data, Your solution to the problem sh...

Your solution to the problem should be housed within a while loop, which allows the grader to test your solution repeatedly without having to re-execute the script, as shown in cla

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