Program Design II (PK2)
SML Assignment 4 of Spring 2006
The Power of Problem Generalisation
Problem generalisation is a powerful technique for:
- Improving the time or space complexity of an algorithm.
- Dealing with problems for which a recursively defined algorithm
cannot readily be found.
The objective of this assignment is to illustrate the first point
above, by applying two different generalisation techniques on the same
problem, comparing the results, and thinking whether they can be
usefully combined.
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.
The file binTrees.sml has
the beginning of a realisation of a polymorphic abstract datatype
(ADT) 'a bTree for binary trees, specified on slides 6.19 to 6.24. The file trees.sml has sample binary trees for your tests
and the examples below. Add the following functions to that ADT, but
declare it as a non-abstract datatype, just to ease the
testing:
- The function preorder returns the preorder walk, as a
list, of a binary tree.
Example:
preorder smallIntTree = [1,2,5,7,3,6,10,13]
Requirements: Do not use any help
functions.
Can you make your function tail-recursive? Why / Why not?
- The function preorder' has the same specification as
preorder.
Requirements: Use exactly one (local)
help function, to be called preorderAcc, which must be
obtained by introducing an accumulator. This technique is also
known as performing a descending generalisation on the
specification of preorder. Do not use any
standard or library functions for lists, not even @.
Can you make your help function tail-recursive? Why / Why not?
- The hidden function preorders takes a list of
binary trees as an argument and returns the concatenation of the
preorder walks of the trees in that list. This specification was
obtained by performing a tupling generalisation on the
specification of preorder. This technique aims at
reducing the number of recursive calls in each clause.
Example:
preorders [smallIntTree,anotherSmallIntTree] = [1,2,5,7,3,6,10,13,2,1,7,5,13,3,6,10]
Requirements: Do not use any help
functions. Do not use any standard or library functions
for lists, not even @. Each clause must have at most
one recursive call.
Can you make your function tail-recursive? Why / Why not?
- The function preorder'' has the same specification as
preorder.
Requirement: Use preorders as a (local)
help function.
- Discuss your answers to questions 1 to 4. In particular, if no
tail recursion in the strict sense has been achieved, would things
change with an inorder walk or a postorder walk? Would a
combination of the two generalisation techniques help to achieve
tail recursion in the strict sense with one of the three kinds of
walks?
- Give a recurrence for the running time T of your
preorder function on a balanced binary tree.
Derive a tight asymptotic bound for T.
- Give a recurrence for the running time T' of your
preorderAcc function on a balanced binary tree.
Derive a tight asymptotic bound for T'.
- Give a recurrence for the running time T'' of your
preorders function on a balanced binary tree.
Derive a tight asymptotic bound for T''.
- Discuss your answers to questions 6 to 8.
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:
- SML functions for Questions 1 to 4 above, in a .sml file,
executable under Moscow ML version 2.01, and documented, in
English, according to the coding
convention of the course.
- Replies, in English, to Questions 5 to 9 above, in a .txt or .pdf
or .html file.