Program Design II (PK2)

SML Assignment 2 of Spring 2006

A. Exponentiation

In any recurrence for a divide-and-conquer algorithm, first make explicit the costs of every part of the divide, conquer (recurse), and combine steps, and relate these costs to the relevant parts of the algorithm. Clearly state any assumptions you make. Then maximally simplify the resulting expressions before continuing.

To derive tight asymptotic bounds Θ(...), use the Master Theorem (MT) where possible. If the MT is applicable, then show in detail which case you apply, why it is applicable, and how you apply it. You can assume that the regularity condition holds, if need be. If the MT is not applicable, then first explain why that is so and then use any other suitable theorem or method seen in the course, again giving the full details of your reasoning.

  1. Give a recurrence for the running time T(k) of the power x k function below, which returns x^k for any integer x and natural number k. 
       fun power x 0 = 1
     | power x k = x * power x (k-1)
    Derive a tight asymptotic bound for T.
     
  2. Give a recurrence for the running time T'(k) of the power' x k function below, which also returns x^k for any integer x and natural number k. 
       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'.
     
  3. Discuss the results.

B. Correctly Parenthesised Texts

Write a predicate p 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:
p "((a+b) * (c-d))" = true
p "((a+b * (c-d))" = false
p "(a+b)) * ((c-d)" = false
p "(a[(b+c) * d] + e) * f" = true
p "(a[(b+c) * d) + e] * f" = false
p "({ab} [+b(c *)])" = true

Hint: The explode function returns the character list corresponding to a string.

Submission

Your solution, prepared in compliance with the ethics rules of the course, must be submitted by the published deadline via the course manager system, and shall contain: