Question

The following algorithm finds the initial substring of y that can be reversed and found in y. For example, longestInitialReverseSubstringLength(“aabaa”) = 5, because “aabaa” is the same string forwards and backwards, so the longest initial substring that can be reversed and found in the string is “aabaa”. Also, longestInitialReverseSubstringLength(“bbbbababbabbbbb”) is 6, because “babbbb” can be found in the string (see color-highlighted portions of the string), but no longer initial string exists reversed in any part of the string.

longestInitialReverseSubstringLength(String y)

01 Max ← 0; //this will be our answer.

02 for i ← 1 to y.length() do: //loop (Main) tries to find reversed initial substrings of...

03 x ← empty string //...all possible lengths

04 for r ← i to 1 do: //reverses the initial i characters and stores in x

05 x ← x○y[r] // “○” indicates concatenation.

06 end for //end reversal loop

07 found ← false;

08 for j ← 1 to y.length() - x.length() + 1 do: //loop (A), which searches for x in y.

09 f ← true //unless contradicted, assume x is in y.

10 for k ← 1 to x.length() do: // loop (B), which searches y[j...j+k] for x.

11 if y[j+k] ≠ x[k] then: //there is a mismatch...

12 f ← false //so x was not found.

13 end if

14 end for //end loop (B)

15 if f then: //x was in y

16 found = true //remember it

17 break

18 end if

19 end for // ends the loop (A)

20 if found then: max = i //***Note the assignment*** new max length found.

21 end for //end loop (Main).

22 return max; //return the answer.

end function

1. show your program running and taking 1 second to run.

2. Analyze the algorithm’s runtime mathematically and express the runtime using big-oh notation (provide a tight upper bound).

3. Analyze the function experimentally.  

   1. Implement the algorithm

   2. Let x be the string length at which your program takes 2 seconds to run, collect running times for your algorithm using the following string lengths: x/4, 2x/4, 3x/4, x, 5x/4, 6x/4, 7x/4, 2x.

   3. Generate your strings by reading the attached file, only reading as many characters as you need.

   4. Plot your results (x-axis is string length, y-axis should be time)

   5. Draw conclusions based on your graph. You may also need to plot another curve (e.g., n, n2, or n3, to support your conclusions).

4. Give the runtime of the following algorithm, which calculates the average of an array of length 100. Note, importantly, this function only works if the length of A is 100.  

average(A) :

If length(A) != 100 then:

ERROR

End If

Sum ← 0

For x in A do:

Sum ← Sum + x

End For

Return Sum / 100

end average

Answer 1

Here is your code what you wanted from the above algorithm.

import sys

def printSubStr(st, low, high) :

sys.stdout.write(st[low : high + 1])

sys.stdout.flush()

return ''

def longestInitialReverseSubstringLength(st) :

n = len(st)

table = [[0 for x in range(n)] for y

in range(n)]

maxLength = 1

i = 0

while (i < n) :

table[i][i] = True

i = i + 1

start = 0

i = 0

while i < n - 1 :

if (st[i] == st[i + 1]) :

table[i][i + 1] = True

start = i

maxLength = 2

i = i + 1

k = 3

while k <= n :

i = 0

while i < (n - k + 1) :

j = i + k - 1

if (table[i + 1][j - 1] and

st[i] == st[j]) :

table[i][j] = True

if (k > maxLength) :

start = i

maxLength = k

i = i + 1

k = k + 1

print( printSubStr(st, start, start + maxLength - 1) )

return maxLength

st = input("Enter your string : - ")

l = longestInitialReverseSubstringLength(st)

print( l )