Provide unoptimized-optimized prefix using recursive rule

Assignment Help Programming Languages

Reference no: EM1371227

Fibonacci strings are defined as follows:

F1 = "b", F2 = "a", and Fn = Fn-1Fn-2, (n > 2)

where the recursive rule uses concatenation of strings, so F2 is "ab", F3 is "aba". Note that the length of Fn is the nth Fibonacci number.

(a Prove that in any Fibonacci string there are no two b's adjacent and no three a's.
(b) Give the unoptimized and optimized ‘prefix' (fail) function for F7.
(c) Prove that, in searching for a Fibonacci string of length m using unoptimized KMP, it may shift up to phi(log m) times, where phi = (1+p5)/2, is the golden ratio. (Hint: Another way of saying the above is that we are given the string Fn and we may have to shift n times. Find an example text T that gives this number of shifts).
(d) What happens here when you use the optimized prefix function? Explain.

Reference no: EM1371227

Questions Cloud

Determining marketing mix : Marketing mix is controllable set of activities that the firm employs to respond to the wants of its target markets. Make a report on the marketing mix and keep the following questions in mind:

Information and opposition to fair disclosure rule : securities professionals argue that individual investors aren't really capable of interpreting much of the information now available to them. Explain why one would agree or disagree with these opinions.

Sinking fund for outstanding preferred stock issue : Acme make a decision to establish a sinking fund for its outstanding preferred stock issue. $975318642 represents the value of the issue that will be retired in 26 years

Automobile that made a difference in mobility : There have been adventurous people traveling since the country was founded without which there would not have been the westward expansion.

Provide unoptimized-optimized prefix using recursive rule : Where the recursive rule uses concatenation of strings, so F2 is "ab", F3 is "aba". Note that the length of Fn is the nth Fibonacci number. Provide unoptimized and optimized ‘prefix' (fail) function for F7.

University pricing strategy : What market structure best characterizes the market in which universities compete? How does this structure influence the university's pricing strategy?

Explain making a short-term pricing decision where surplus : Explain What additional costs must be taken into account when making a short-term pricing decision where surplus capacity is not available

Media explosion allows information sharing : The art and literature of these cultures need to be shared with anyone who wants to learn about them. Explain

Question about cost drivers : Firm A produces three products. Firm A uses labor costs as a cost driver for support costs. Direct labor is estimated at $20 per hour.

User Account

All Pages