Q1
1.
(a)
def TotalAndCountAbove(A, k, i):
if i == 0:
return (0, 0)
total, count = TotalAndCountAbove(A, k, i – 1)
if A[i] >= k:
total += A[i]
count += 1
return total, count
(b)
T(n) = T(n-1) + O(1) if(n > 0)
= O(1) (otherwise n = 0)
(c)
running time of Total&CountAbove algorithm
T(n) = T(n-1) + O(1)
= T(n-2) + O(1) + O(1)
= T(n-3) + O(1) + O(1) + O(1)
…..
= n*O(1)
= O(n)
running time of AverageAbove algorithms.
Y(n) = T(n) + O(1) = O(n)
Q2
Dear Amy,
I want to offer some advice that may help you solve the problem.
We want to split the string into valid tokens. To quantify the quality of a token, we need a string scoring function that give any sequence of characters a score that indicate how likely this sequence of character can be a valid token. Larger score indicates it is more likely to be a valid token.
Suppose now, we have such string scoring function, we can formally define the problems as follows.
Given a sequence characters of length n, segment the sequence into tokens such that the sum of the score of each token given by the string scoring function is largest.
Let the string scoring function names Score, the input character sequence as Seq which has length n, and the function Opt(k) gives the largest sum of score that substring Seq[1:k] can be segmented.
For a optimal segmentation of Seq, suppose the last token is Seq[k:n], then the segmentation of Seq[1:k-1] must be also a optimal segmentation, If not we can get a larger sum of score by
segment the Seq[1:k-1] optimally. So if iterate all possibility of the last token segmented, and compute them recursively, the one that gives the largest value will be solution. We can get solution of size n from combing the solution of the same problem whose size is less than n. Thus Function Opt can be defined recursively as follows:
Opt(0) = 0
Opt(k) = max(Opt(i-1) + Score(Seq[i:k])) for all i in [1, k]
In actual implementation, we won’t implement it recursively,
Rather we solve bottom up, from smaller to larger value and
store the result in a table. The pseudo code would be as follows.
Let Opt be an array [0…n]
For j = 1 to n
Opt[j] = max(Opt[k-1] + Score(Seq[k:j]) for k in [1, j])
For example, suppose the input sequence Seq = “jorice5westst”.
First, the simplest case empty string segmentation, Opt[0] = 0.
Then Opt[1] is computed from Opt[0] which will be Opt[1] = Score(“j”). Next compute Opt[2], which will be the larger value of Opt[0]+Score(“jo”) and Opt[1]+Score(“o”). Likewise we can compute all the value Opt[k] from k=0 to n. In every step we make use of the Opt[k] of smaller k. That is why we use an array to store the results and compute from smaller value to larger value.
Note, we iterate n times, in every time, we compute the largest of at most n numbers. So the running time will be O(n*n) = O(n^2) and the space needed is obviously O(n).
Previous algorithm only computed the best sum of score of the segmentation; we still need to recover the optimal segmentation that achieves this sum of score. The algorithm is as follows.
j = n
While j > 0
Find the 1<=k<=j that Opt[j] == Opt[k-1] + Score(Seq[k:j])
Output the token Seq[k:j]
j = k-1
Above algorithm will output the best segmented tokens reversely and its running time also O(n^2).
In summary, I have proposed the formal definition of the algorithm, offer the dynamic algorithm that compute the best value and the algorithm how to recover the segmentation, also analyze the running time of the algorithm. I hope all this can help you implement the solution successfully.
Good luck!