A. Exponentiation

In any recurrence for a divide-and-conquer algorithm, make explicit the costs of every part of dividing, conquering (recurring), and combining, and relate these costs to the relevant parts of the 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 13 februari, klockan 08:14 (på morgonen), med hjälp av inlämningssystemet, och ska innehålla:
• Svar, på engelska, på fråga A ovan, i en *.txt eller *.pdf eller *.html fil.
• SML funktionerna för fråga B ovan, i en *.sml textfil, körbar under Moscow ML version 2.01 (det som inte är kod ska vara bortkommenterat), och dokumenteras, på engelska, enligt kursens kodkonventionerna.