Assignment 2

A. Exponentiation

In any recurrence, make explicit the costs of dividing, conquering (recurring), and combining of a divide-and-conquer algorithm. To derive tight asymptotic bounds Θ(...), use the Master Theorem where applicable; otherwise, first state why it is not applicable and then use any other relevant method or theorem. In any case, always show all the details of your reasoning.

Give a recurrence for the running time T of the power x k function below, which returns x^k for any integer x and natural number k. State any assumptions you make. 

   fun power x 0 = 1
     | power x k = x * power x (k-1)
Derive a tight asymptotic bound for T.

Give a recurrence for the running time T' of the power' x k function below, which also returns x^k for any integer x and natural number k. State any assumptions you make. 

   fun power' x 0 = 1
     | power' x k =
         let val p = power' x (k div 2)
         in  if (k mod 2) = 0 then p * p
             else x * p * p
         end
Derive a tight asymptotic bound for T'. Discuss the results.

B. Correctly Parenthesised Texts

Write a predicate parenthesised that returns true if and only if its argument text, given as a string, is correctly parenthesised. The parentheses to be considered are the regular round parentheses (), the square brackets [], and the curly braces {}.

Examples and counter-examples:
parenthesised "((a+b) * (c-d))" = true
parenthesised "((a+b * (c-d))" = false
parenthesised "(a+b)) * ((c-d)" = false
parenthesised "(a[(b+c) * d] + e) * f" = true
parenthesised "(a[(b+c) * d) + e] * f" = false
parenthesised "({ab} [+b(c *)])" = true

Hint: The explode function returns the character list corresponding to a string.

Inlämning

Din redovisning, enligt kursens etikregler, måste lämnas in senast måndag 14 februari, klockan 10:14 (på morgonen), med hjälp av inlämningssystemet, och ska innehålla: