1. Suppose there is a procedure f that decides a language A in O(g(n)) time, where n is the length of the input string. Use dynamic programming (not memoization) to create an algorithm that decides A^*in O(n^2 g(n))time.Implement your strategy in python here.

import numpy as np

#Suppose there is a procedure inA that decides a language A.
#Use dynamic programming (not memoization) to create an
#algorithm that decides A* in O(n^2) time, where n is the
#length of the input string.

#This is run by "Submit"
def inAstar(x, inA):
""" Returns true if x is in A^* and false otherwise.
The input inA should be assumed to be a function
that takes are string as input and return True or False."""
#Your code here

#This is run by "Test Run"
def main():
def inA(x):
   return x in ['0', '10']
def inB(x):
   return x in ['01','010','100','110','0010','1001','1011','1100','1101','1110','1111']
assert(inAstar('10111111100101011011000101010100101100100110011101', inB))
assert(inAstar('0101000010', inA))
assert(not inAstar('000110010', inA))

if __name__ == '__main__':
main()

2. Consider an arbitrary string 〖X = x〗_0…x_(n-1). A subsequence of X is a string of the form x_(i_1 ) x_(i_2 )…x_(i_k,)where 1≤i_1<⋯<i_k<n. For example ‘ape’ is a subsequence of ‘apple.’ A string is palindromic if it is equal to its own reverse (i.e. the string is the same whether read backwards or forwards).

We will use dynamic programming to find the length of the longest palindromic subsequence of X. For i≤j, let L(i,j) be the length of the longest palindromic subsequence of the substring x[i:j] (the substring going from the ith character to the jth character of x, not including the jth character).

Derive a recurrence for L(i,j), remembering to include the base case?
Why is this recurrence correct?
Write a dynamic programming algorithm based on the recurrence for L(i,j) in python. Use backtracking to construct a longest palindromic subsequence.
What is its running time?

#Consider an arbitrary string X = x_1...x_n.
#A subsequence of X is a string of the form
#x_i_1 x_i_2...x_i_k ,where 1 <= i_1< ... < i_k <= n.
#A string is palindromic if it is equal to its
#own reverse (i.e. the string is the same whether
#read backwards or forwards).

#a) Derive a recurrence for L(i, j).Why is your recurrence correct?
#b) What is the base case?
#c) Use dynamic programming to implement the procedure below.
#d) What is its running time?

def lps(s):
"""Returns a longest palindromic subsequence of the string s."""

def main():
assert(lps('axayyybaxca4baza') in ['aabacabaa','axayyyaxa', 'aabaxabaa'])

if __name__ == "__main__":
main()

3. Let A(x) = a_(0 )+a_1 x+⋯+a_n x^n and let B(x) = b_0+b_1 x+⋯+b_n x^nn be two polynomials. Recall that C(x) = A(B(x))=a_0+a_1 B(x)+a_2 B^2 (x)+⋯a_n B^n (x)=c_0+c_1 x+⋯c_(n^2 ) x^(n^2 ). Implement an O(n^3 logn) for finding the coefficients of C:

#Your task is twofold:
#1. Implement the polycomp(A,B) procedure below so
# that it returns the composition of polynomials A and B.
#2. Explain why your algorithm is O(n^3 log n) or
# (better still) O(n^3)

#In the procedure polycomp(A,B), the polynomials are given
#as numpy arrays with type int. In numpy as in most numerical
#packages, polynomials are represented as arrays with the
#coefficient on the largest power oming first. Thus, an
#array A on length n would represent the polynomial
#
#A[0] * x**(n-1) + A[1] * x**(n-1) + ...+ A[n-2] * x + A[n-1].
#
#We will use the same convention here.
#
#
#Two possible strategies include:
#1. Adapt one of the standard strategies for evaluating
# polynomials (e.g. Horner's rule) to the task of composing them.
# If n is the larger order of the polynomials, this will give
# you a O(n^3 \log n) algorithm
#
#2. Use the fft (scipy.fft, scipy.ifft) to achieve a
# O(n^3) algorithm. Be careful about the order of
# your coefficients.
#
#
#Some potentially useful calls are:
#
############################################################
#C = np.zeros(n, dtype=int) #to create an array of n zeros
#(http://docs.scipy.org/doc/numpy/reference/generated/numpy.zeros.html)
#
###########################################################
#C = np.convolve(A,B) #to convolve the arrays A and B
#(http://docs.scipy.org/doc/numpy/reference/generated/numpy.convolve.html)
#
############################################################
#V = np.polyval(A,x) #Evaluates A at the point values in x.
# Note that A[-1] is the constant term
#(http://docs.scipy.org/doc/numpy/reference/generated/numpy.polyval.html)
#
############################################################
#c = fft(C, npts) #where npts is the number of points that will be output.
#C = ifft(c, npts) #where npts is the number of points that will be output.
#Note that C[0] is the constant term.
#(http://docs.scipy.org/doc/numpy/reference/routines.fft.html)
#
############################################################
#C = C[::-1] # to reverse the array C
#
############################################################
#C = C.real.round().astype(int) #To round complex numbers to ints along real axis
#
############################################################

import numpy as np
from numpy.fft import fft, ifft

def polycomp(A,B):
"""Computes A(B(x))"""
#Your code here

def main():
A = np.array([2, 1, 1], dtype=int)
B = np.array([1, 3, 1], dtype=int)
ans = polycomp(A, B)

assert type(ans) is np.ndarray
assert np.array_equal(ans, np.array([2, 12, 23, 15, 4], dtype=int))

if __name__ == '__main__':
main()
Explain your running time analysis. It’s okay if it’s faster than Ω(n^3 logn).
Now, make your algorithm O(n^3). Explain your running time analysis in your comments.

4. Given two sets A and B of integers, their sum set C is defined to be C = {a+b: a∈A,b∈B}. For each c∈C, let m(c)denote the number of ways in which c can be obtained, i.e., m(c) = |{(a,b)∶ a ∈A,b ∈B,a+b = c}|. For example, if A = {1,2,3} and B={0,1,4}, then their sum set is C = {1,2,5,3,6,4,7} and m(1) = 1, m(2) = 2, m(3) = 2, m(4) = 1, m(5)=1, m(6) = 1, and m(7) = 1.
For two arbitrary sets A and B of integers, what is the worst-case complexity of computing their sum set?
Suppose now that A,B consist of integers in the range [0,n). Give an upper bound on the number of distinct elements in their sum set.
With the above assumption, give an O(nlogn)to find (c,m(c)) for each c∈C.

# Given two sets A and B of integers, their sum set C is defined to be
# C = {a+b: aA, bB}. For each c \in C, let m(c)denote the number of ways in
# which c can be obtained, i.e., m(c) = |{(a,b) : a A, b B, a+c = c}|.
# For example, if A = {1,2,3} and B={0,1,4}, then their sum set is
# C = {1,2,5,3,6,4,7} and
# m(1) = 1, m(2) = 2, m(3) = 2, m(4) = 1, m(5)=1, m(6) = 1, and m(7) = 1.

# Answer the following:
# a) For two arbitrary sets A and B of integers, what is the worst-case
# complexity of computing their sum set?
# b) Suppose now that A,B consist of integers in the range [0,n). Give
# an upper bound on the number of distinct elements in their sum set.
# c) With the above assumption, implement the sumset procedure below
# using an O(nn)to find (c,m(c)) for each c \in C.

# Hint: Use numpy's convolve routine, which takes only O(n log n)
# time to produce an algorithm that is O(n log n) overall.
#Example uses of convolve
#print np.convolve([3, 0, 2], [1, 1, 1, 1]))
#or
#print np.convolve(np.array([3, 0, 2]), np.array([1, 1, 1, 1]))

import numpy as np

def sumset(n,A,B):
#Replace the naive implementation below with one that runs
#in O(n log n) time.
#YOUR CODE HERE
C = np.zeros(2*n,dtype= int)

for a in A:
   for b in B:
         C[a+b] += 1

return [ (i,C[i]) for i in range(len(C)) if C[i] > 0]

def main():
A = [1,2,3]
B = [0,1,4]

C = sumset(5,A,B)

C.sort()

assert (C == [(1, 1), (2, 2), (3, 2), (4, 1), (5, 1), (6, 1), (7, 1)])

if __name__ == "__main__":
main()

1.&nbsp; &nbsp;Suppose there is a procedure f that decides a langu...

1. Suppose there is a procedure f that decides a langu...