AD1 -- SML Assignment 2

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: