Consider trying to find the longest substring of an n -character string s = s0 s
ID: 3836608 • Letter: C
Question
Consider trying to find the longest substring of an n -character string s = s0 s1 s2 ... sn-1 that is also a palindrome. For example, the longest palindromic substring of the string opposite is the substring oppo.
We will approach this problem as a dynamic programming problem based on a matrix:
Ai,j = 1 if si ... sj is a palindrome or i>j, and 0 otherwise.
3a. [9 points]
Compute entries of A0..3,0..3 for the string a b a b.
3b. [5 points]
Which entries Ai,j can you determine in constant time (per entry):
i=0, any given j
i=15, j=n-1
i=j
j=i+15
i= log(n-1), j=log(n-1)
3c. [5 points]
Which recurrence correctly relates elements of matrix A:
Ai,j = Ai-1,j-1 + 1
Ai,j = Ai-1,j* Ai-2, j
Ai,j = (si==sj) ? Ai+1,j-1 : 0
Ai,j = ( (si==sj) ? Ai-1,j-1 : 0 ) + 1
Ai,j = (si==sj) ? 1 : Ai+1,j-1
3d. [5 points]
Which of the following would always provide the solution to the problem (i.e. the size of the longest palindromic substring of s):
A0,n-1
An-1,n-1
largest j-i for which Ai,j==1
largest i+j for which Ai,j==1
largest i for which Ai,n-1==1
3e. [5 points]
Which of the following is true about the running time of this algorithm based on a dynamic programming using parts (a) through (c)?
O (n)
O (n2)
O (n2 log n)
O (n3)
O (n5)
Explanation / Answer
A) Compute entries of A0..3,0..3 for the string a b a b.
Here, Ai,j = 1 if si ... sj is a palindrome or i > j
else Ai,j = 0
0 1 2 3
0 1 0 1 0
1 1 1 0 1
2 1 1 1 0
3 1 1 1 1
B) Which entries Ai,j can you determine in constant time (per entry):
i=0, any given j => yes (s0==sj) ? A1,j-1 : 0
i=15, j=n-1 => yes (s15==sn-1) ? A16,n-2 : 0
i=j => yes 1
j=i+15 => yes (si==si + 15) ? Ai + 1,i + 14 : 0
i= log(n-1), j=log(n-1) => can't find in constant time
C) Which recurrence correctly relates elements of matrix A:
Ai,j = Ai-1,j-1 + 1 => false
Ai,j = Ai-1,j* Ai-2, j => false
Ai,j = (si==sj) ? Ai+1,j-1 : 0 => true
Ai,j = ( (si==sj) ? Ai-1,j-1 : 0 ) + 1 =>false
Ai,j = (si==sj) ? 1 : Ai+1,j-1 => false
D) Which of the following would always provide the solution to the problem (i.e. the size of the longest palindromic substring of s):
A0,n-1 => no
An-1,n-1 => no
largest j-i for which Ai,j==1 => yes
largest i+j for which Ai,j==1 => no
largest i for which Ai,n-1==1 => no
E) Which of the following is true about the running time of this algorithm based on a dynamic programming using parts (a) through (c)?
O (n) => incorrect
O (n2) => correct // we are running two loops to store is si,j is palindrome or not and update
O (n2 log n) =? incorrect