Subquadratic Time Alignment $[15+5$ points$]$

a$.$ In class we learned how to solve the block alignment problem in time $O(\frac{n^2}{logn})$

using the Four Russians Technique. Specifically, in the case of an alphabet of

$||=4$ letters, we pre$-$computed all pairwise alignments of all strings of length

$t=lo{g}_2\frac{n}{4}.$ Protein sequences have an alphabet of $||=20$ letters. How

should we choose length $t$ to achieve the time bound of $O(\frac{n^2}{logn})$ if $||=20?$

Motivate your answer. $[5$ points$]$

b$.$ How should we choose length t if the size k$=|\backslash$Sigma $|$ of the alphabet is not

constant? What is the running time? Motivate your answer. $[5$ points$]$

Bonus: $+5$ points if you explain for what values of k this technique leads

to: $($i$)$ an asymptotic speedup, $($ii$)$ the same running time as regular dynamic

programming and $($iii$)$ an asymptotic slowdown.