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