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
Question 1 Explain the three traits of Object Oriented Programming Question 2 Write a note on (a) Assignment Operators                             b) Bitwise Operators.

For this assignment you will need to design and construct a basic math program which targets elementary school children. Your program must adhere to the following steps and require

Microsoft Intermediate Language in .NET When you create value in any terminology and gather, it will be changed to an 'Intermediate Language' (Microsoft Advanced Language - MSIL

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

Write a function called withdraw (in the file 'withdraw.m') that simulates withdrawing money from a bank account. The function takes a single input argument, a positive scaler doub

As an XML expert you are required to model a system for an online bookshop. After an interview with the shop manager you have the following information: The detail of th

Extend the AirRaid game, so that the planes drop a bomb on the gun as they go over it. The gun has to move out of the way otherwise it will be destroyed if hit. Provide three lives

The program presents mainframe contains two button new user, existing user PART ONE: CLICKING ON NEW USER New window appear contains: text field represent username,

Use an insertion sort to sort an array (sequence) of long word integers. The size of the list will appear just before the list itself. Use the same labels as in this example: LE

In this assignment, you will design a program to perform the following task: Calculate the total price to purchase all the components required to build a state-of-the-art gaming c