This question pertains to string alignment.
Describe an algorithm for counting the number of optimal alignments, given an optimal cost matrix S. Prove your algorithm is correct, and give its asymptotic runtime.
The response must be typed, single spaced, must be in times new roman font (size 12) and must follow the APA format.