# 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:
• 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.