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
Alex_Xolod [135]
3 years ago
12

You are given a string of n characters s[1 : : : n], which you believe to be a corrupted text document in which all punctuation

has vanished (so that it looks something like itwasthebestoftimes...). You wish to reconstruct the document using a dictionary, which is available in the form of a Boolean function dict(): for any string w, dict(w) = true if w is a valid word false otherwise . (a) Give a dynamic programming algorithm that determines whether the string s[] can be reconstituted as a sequence of valid words. The running time should be at most O(n2), assuming calls to dict take unit time. (b) In the event that the string is valid, make your algorithm output the corresponding sequence of words.
Computers and Technology
1 answer:
alexdok [17]3 years ago
8 0

Answer: provided in the explanation section

Explanation:

Given that:

Assume D(k) =║ true it is [1 : : : k] is valid sequence  words or false otherwise

  • To determine D(n)

now the sub problem s[1 : : : k] is a valid sequence of words IFF s[1 : : : 1] is a valid sequence of words and s[ 1 + 1 : : : k] is valid word.

So, from here we have that D(k) is given by the following recorance relation:

D(k) = ║ false maximum (d[l]∧DICT(s[1 + 1 : : : k]) otherwise

Algorithm:

Valid sentence (s,k)

D [1 : : : k]             ∦ array of boolean variable.

for a ← 1 to m

do ;

d(0) ← false

for b ← 0 to a - j

for b ← 0 to a - j

do;

if D[b] ∧ DICT s([b + 1 : : : a])

d (a) ← True

(b). Algorithm Output

      if D[k] = = True

stack = temp stack           ∦stack is used to print the strings in order

c = k

while C > 0

stack push (s [w(c)] : : : C] // w(p) is the position in s[1 : : : k] of the valid world at // position c

P = W (p) - 1

output stack

= 0 =

cheers i hope this helps !!!

You might be interested in
A data center needs to ensure that data is not lost at the system level in the event of a blackout. Servers must stay operable f
poizon [28]

Answer: UPS

Explanation:

The redundancy effort that should be put in place to ensure the data remains available is the Uninterruptible Power Supply(UPS).

Uninterruptible Power Supply (UPS) is necessary in the provision of battery backup power when there's drop or stoppage in the flow of electricity. With regards to the question, it'll ensure that data is not lost at the system level in the event of a blackout.

3 0
3 years ago
The following pseudocode is an example of ____.do stepAdo stepBif conditionC is true thendo stepDelsedo stepEendifwhile conditio
rewona [7]

Answer:

Option d pretest

Explanation:

Given the pseudocode:

  1. do stepA
  2. do stepB
  3. if conditionC is true
  4. then do stepD
  5. else
  6. do stepE
  7. end if
  8. while conditionF is true
  9. do stepG
  10. end while

The pseudocode above shows that there is a pretest before some codes are executed. For example, line 3 check if condition is true then only execute stepD otherwise execute stepE. Line 8 check if conditionF is true then repeatedly execute stepG. These are examples of pretest a condition will must be met (pretest passed) before a block of codes can be executed. This pretest can be seen in if-else statements and also the while condition.  

6 0
3 years ago
Design a flowchart or pseudocode for a program that accepts three numbers from a user and displays a message if the sum of any t
Keith_Richards [23]

Answer:

Hi there! Pseudocode is the process of writing out the high-level structure of the program in simple English terms which acts as a blueprint of how the program will work. The pseudocode for this question is written below.

Explanation:

Prompt user for input 1

Validate input 1

Prompt user for input 2

Validate input 2

Prompt user for input 3

Validate input 3

Perform checks:

If  

 1 and 2 equals 3

 Or

 1 and 3 equals 2

 Or

 2 and 3 equals 1

Display message to user

6 0
3 years ago
Sam wants to move across the text and his documents to add data at predefined stops. Which key will Hughes to navigate through t
Setler [38]

Answer:

The TAB key

Explanation:

Sam would use the TAB key, located on the left side of the keyboard, to move around his document to add stops and format its information properly.

Pressing the TAB key will introduce a tab code in his document, which is like moving ahead by a certain number of spaces (5,6, 10 spaces for example, depending on the configuration of the document), but without using spaces, using a tab which is a much better option to position, align things up.

5 0
3 years ago
In a _____ network, each device on the network is attached to a central router. If the router fails, then the other devices will
Damm [24]

Answer:

In a STAR TOPOLOGY network, each device on the network is attached to a central router. If the router fails, then the other devices will be unable to communicate, but if only one connected device fails, then all other devices will still be able to communicate.

Explanation:

In this type of topology all the computers are connected to a single router through a cable. This router is the central node and all others nodes are connected to the central node.

7 0
3 years ago
Other questions:
  • The use of computers to combine data from multiple sources and create electronic dossiers of detailed information on individuals
    8·1 answer
  • Write a client program that writes a struct with a privateFIFO name (call it FIFO_XXXX, where XXXX is the pid that you got from
    11·1 answer
  • When changing the formatting of a spreadsheet to make it more readable, you should use light blue text on a bright blue backgrou
    12·1 answer
  • What is a computer network?
    5·1 answer
  • Can an iphone user see when an android user is typing
    10·2 answers
  • Explain motherboard in detail
    14·2 answers
  • Definition of digital
    9·2 answers
  • What methods do phishing and spoofing scammers use? List and explain methods to protect against phishing and spoofing scams.
    14·1 answer
  • GRAND THEFT AUTO 5 LOLLL
    15·2 answers
  • Which of the following tabs on the Ribbon contains the command to add a Quick Part to a document? A Design B Insert C View D Hom
    7·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!