AD1 -- SML Assignment 2

A. Exponentiation

Introduction

When deriving a recurrence for a divide-and-conquer algorithm (that is a recursive algorithm) you are to make explicit the costs of every part of the algorithm especially the cost of dividing, conquering (recurring), and combining, and relate these costs to the relevant parts of the algorithm.

When you 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 (for example, guess the answer and prove by induction). In any case, always show all the details of your reasoning.

Powers

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.

Hand-in

Your report complying with ethics rules of the course should be handed in latest on Friday the 9th of February before 08:14 (morning) via the online course manager system, and should contain:

Answer, in English, for question A from above, in a *.txt, or *.pdf, or *.html file.
SML functions for question B from above, in a *.sml text file, running under Moscow ML version 2.01, and commented, in English, complying with coding convention.