1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
kirza4 [7]
3 years ago
10

Dr. Watson has been kidnaped! Sherlock Holmes was contacted by the kidnapper for ransom. Moments later he received a message fro

m Dr. Watson's phone. The message contained three random strings. Sherlock being Sherlock, was able to deduce immediately that Dr. Watson was trying to give a hint about his location. He figured out that the longest common subsequence between the 3 words is the location. But since it was too easy for him, he got bored and asked you to find out what the actual location is. Your task is to find the longest common subsequence from the 3 given strings before it is too late. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For instance, given a sequence "drew"; "d", "w", "de", "drw", "drew" are all examples of valid subsequences (there are also others), while "er", "wdre" are not. Design a dynamic programming algorithm which takes three input sequences X, Y, and Z, of lengths m, n, and p, respectively, and returns their longest common subsequence. For full marks your algorithm should run in (mnp) time. Note that W is a common subsequence of X, Y, and Z if and only if W is a subsequence of X, W is a subsequence of Y, and W is a subsequence of Z.
Required:
Describe the set of subproblems that your dynamic programming algorithm will consider.
Computers and Technology
1 answer:
adelina 88 [10]3 years ago
8 0

Answer:

please mark me brainlist

Explanation:

This algorithm works for n number of strings in python3

Input:

83217

8213897

683147

Output:

837

from itertools import product

import pdb

import numpy as np

def neigh(index):

N = len(index)

for ri in product((0, -1), repeat=N):

if not all(i == 0 for i in ri):

yield tuple(i + i_rel for i, i_rel in zip(index, ri))

def longestCommonSubSequenceOfN(sqs):

numberOfSequences = len(sqs); # to know number of sequences

lengths = np.array([len(sequence) for sequence in sqs]); # to know length of each sequences placed in # array

incrLengths = lengths + 1; # here we are taking no .of sequences +1

lengths = tuple(lengths); # making lengths into tuple to make it mutable

inverseDistances = np.zeros(incrLengths);

ranges = [tuple(range(1, length+1)) for length in lengths[::-1]]; # finding ranges from 1 to each lengths

for tupleIndex in product(*ranges):

tupleIndex = tupleIndex[::-1];

neighborIndexes = list(neigh(tupleIndex)); # finding neighbours for each tupled index value and # store them in list

operationsWithMisMatch = np.array([]); # creating array which are miss matched

 

for neighborIndex in neighborIndexes:

operationsWithMisMatch = np.append(operationsWithMisMatch, inverseDistances[neighborIndex]);

#appending newly created array with operations miss match and inverseDistances

operationsWithMatch = np.copy(operationsWithMisMatch);

# copying newly generated missmatch indexs

operationsWithMatch[-1] = operationsWithMatch[-1] + 1;

# incrementing last indexed value

chars = [sqs[i][neighborIndexes[-1][i]] for i in range(numberOfSequences)];

# finding a string(chars) with neighbour indexes and checking with other sequences

if(all(elem == chars[0] for elem in chars)):

inverseDistances[tupleIndex] = max(operationsWithMatch);

else:

inverseDistances[tupleIndex] = max(operationsWithMisMatch);

 

subString = ""; # resulted string

mainTupleIndex = lengths; # copying lengths list to mainTupleIndex

while(all(ind > 0 for ind in mainTupleIndex)):

neighborsIndexes = list(neigh(mainTupleIndex));

#generating neighbour indexes with main tuple index in form of list

anyOperation = False;

for tupleIndex in neighborsIndexes:

current = inverseDistances[mainTupleIndex];

if(current == inverseDistances[tupleIndex]): # comparing indexes in main tuple index and inverse #distance tuple index

mainTupleIndex = tupleIndex;

anyOperation = True;

break;

if(not anyOperation): # if anyoperation is False then we are generating sunString

subString += str(sqs[0][mainTupleIndex[0] - 1]);

mainTupleIndex = neighborsIndexes[-1];

return subString[::-1]; # reversing resulted string

sequences = ["83217", "8213897", "683147"]

print(longestCommonSubSequenceOfN(sequences)); #837

You might be interested in
What is a spreadsheet​
Delicious77 [7]
A spreadsheet function that indicates the average of a group of numbers in a range.
8 0
3 years ago
When you run __________ on your hard drive, files are reorganized, making the hard drive work more efficiently.
andre [41]

Answer:

Disk Defragmenter

Explanation:

6 0
2 years ago
Help me pleaseeee!
kenny6666 [7]

Answer:

Try checking around on the router!

Explanation:

Assuming they haven't changed it, most routers have their default password displayed somewhere on it. I hope this helps!! ^^

5 0
2 years ago
Read 2 more answers
Write a program that will read in a line of text and output the number of words in the line and the number of occurrences of eac
kherson [118]

Answer:

Here is the C++ program:

#include<iostream>  //to use input output functions

#include <algorithm>  //to use tolower() function

using namespace std;  //to identify objects like cin cout

int main() {  //start of main function

 string text;  // to hold text input

 cout<<"Enter a line of text: ";  // prompts user to enter a string

 getline(cin,text);  // reads the input string (text) from user

transform(text.begin(), text.end(), text.begin(), ::tolower);  //converts the text into lower case

 int letter[26] = {0}; //to hold the letters

 int i;  // used as a loop variable

 int words=0;  // to hold the count of words

 for(i = 0; i< text.size();i++){  // iterates through the text

 if(isalpha(text[i])&&(text[i+1]=='.'||text[i+1]==','||text[i+1]==' '))  //checks if the character at i-th index of text is a letter, and checks if i+1 index position of text is a period, comma or a space

 words++;  // adds 1 to the count of words

 if(isalpha(text[i]))  // if the character at the i-th index of text is a letter

 letter[text[i]-'a']++;  }  // counts the occurrences of each letter

 char j = text[text.size()-1];  // sets j to the last character of text

 if(j != '.' && j!= ' '&& j!=',' &&j!= '\0')  //if the last character is not a period or empty space  or comma or end of lone

 words++;  //add 1 to the count of words

 cout<<"Number of words: "<<words<<endl;  //display the number of words in the text

 for(i=0; i<26; i++)  {  //iterates 25 times

   if(letter[i]>0)  //if letter at index i is greater than 0

   cout<<(char)('a'+i)<<" : "<<letter[i]<<endl;  }} //displays each letters and its number of occurrences in the text

 

Explanation:

The program is explained in the attached document with an example.

7 0
4 years ago
Explain what the World Wide Web is, including several tasks that can be accomplished online. Include definitions of the followin
Alja [10]

Answer:

<u>World Wide Web (WWW):</u>

The World Wide Web (WWW) or the Web, which was invented by Tim Berners-Lee in the year 1989, is an information system of internet servers containing web pages where specially formatted documents and resources, supported by Hypertext Transfer Protocol or HTTP, can be located by Uniform Resource Locators (URLs) with other hypertext links. Technical definition of the world wide web can be " all the user and resources using an HTTP protocol''.

<u>Web-page:</u>

A web page can be defined as the solitary page of a website. When a user wants to access a webpage, it can be accessed using a single URL, and that page can be copied and shared. Unlike a website, no navigation is required to view the webpage.  

It may contain text, graphics, audio, video, downloadable hyperlinks for other pages, etc. Web browsers are used to display web page content on a computer or mobile by connecting to the server. Some of these documents have to use Flash or Java to view the information.

<u>Downloading:</u>

Downloading means receiving data from a remote system to a local system or initiating any such data transfer. There are some similar remote systems from which one can download. A download can mean the process of obtaining a file that has been submitted or downloaded for downloading, or any such type of file.

<u>Website:</u>

A website is a collection of interconnected web-pages, publicly available on the Internet, that share a domain name. Exchange of information can be done by the website. It can also be used to provide entertainment, news, and education.

A website is a means of obtaining information through the Internet. Special programs are used to view websites on computers, which are called web browsers.

Websites are found on the web-server. Every website has an Internet address which is called URL. The web-browser displays the website according to this address. The web-browser uses HTTP script (HTTP) to access them.

<u>Web server:</u>

A web server is a software that serves web pages, that is, software that transmits web pages to users. This can be divided into two parts: the machine on which the web-server is installed and the software that acts as a web server. These are the first hardware and the second software.

6 0
3 years ago
Other questions:
  • What is the term for a male reproductive cell?​
    14·1 answer
  • How do the following improve security <br> User Id <br> Password<br> Encryption
    10·2 answers
  • How to make flashcards on microsoft word 2010?
    7·1 answer
  • How are network computers different from traditional personal computers? describe some usage scenarios in which it is advantageo
    12·1 answer
  • Steps to log out of an email account ​
    5·2 answers
  • The function known as "Comments" can be displayed during a presentation<br>O True<br>False​
    5·2 answers
  • What is the local portion of the e-mail address below? <a href="/cdn-cgi/l/email-protection" class="__cf_email__" data-cfemail="
    15·1 answer
  • A program that processes data submitted by the user. Allows a Web server to pass control to a software application, based on use
    11·1 answer
  • A systems flowchart:
    15·1 answer
  • Why do attackers tend to target public or private Wi-fi networks?
    10·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!