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
-(-13) P binary using signed. 2's complement representation
ArbitrLikvidat [17]

Answer:

00011101

00011101

Explanation:

Given the following arithmetic operations

a)   (+42) + (-13)

b)   (-42) - (-13)

From (a):

We need to convert +42 into binary, so we get = 00101010

Now for +13, when it is converted into binary, we get = 00001101

But, here, the 13 is negative. So, here is what we will do, we will have to take the two compliment of the binary. After doing that, we get = 111110011

∴

+ 42     →     00101010

<u> - 13      →     1 1 1 10011 </u>

<u>+29             000 11101  </u>

Thus, the arithmetic operation after we use 2's complement is 00011101

b)

Here both 42 and 13 are negative. Using two complement representation

-42 is first converted to binary as 00101010, Then → 11010101 + 1 = 11010110

-13 is converted to binary as 00001101 → 11110010 = 11110011

In between, a negative sign exists, so we take another 2's complement.

i.e.

11110011 → 00001100 + 1 = 00001101

- 42 →     1 1 01 0110

<u>+13  →     00001 101</u>

<u>-29         1 1 1 00011</u>

<u />

since there is no carry, we take two's complements for the result as:

1 1 1 00011 →00011100 + 1 = 00011101

3 0
3 years ago
The part of the computer that provides access to the internet is the?
OLga [1]
Google chrome or the inner webs
8 0
3 years ago
Imagine that you have a friend who has expressed interest in designing and programming video games. He loves to play video games
Julli [10]

Answer:

Point out that it takes education in coding and computer programming in order to get to the basis of designing and programming video games, and that it takes weeks, months, if not years to fully complete a game. He would need time and patience in order to work in the video game creation idustry. Schooling for programming computers and apps can take years.

Explanation:

8 0
3 years ago
You Could Never Size Me UP! Been Doing This Sh*t A Long ⏱time
SVETLANKA909090 [29]

Answer:

Have a nice day :) God Bless!

Explanation:

4 0
2 years ago
If we want to access files located in a directory on a remote server, which of these options would we use?
Ray Of Light [21]
DNS obviously...............
5 0
3 years ago
Read 2 more answers
Other questions:
  • How does scarcity affect what gets produced
    5·1 answer
  • ____ languages create source code using words and structures similar to spoken language.​
    15·1 answer
  • What sends massive amounts of email to a specific person or system that can cause that user's server to stop functioning? mail b
    6·1 answer
  • What percent of the internet is the deep web?
    14·1 answer
  • Which of the following is true about radio waves? They have short wavelengths. They have high energies. They reveal hot gases. T
    10·2 answers
  • Clearing the computer's cache helps store recently-used information.
    8·1 answer
  • __________ is a growing practice in cooperative farmingassociations to pool and sell the fruit as a common commodity underthe br
    6·1 answer
  • Which of the following scenarios is an example of irrelevant media?
    11·1 answer
  • DTE just installed 500kW of solar capacity on the MCCC campus. the cost of the installation was about $3 million. what was the c
    10·1 answer
  • Question 2
    7·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!