PK II -- SML Assignment 4
Problem generalisation is a powerful technique for:
- improving the time and/or space complexity of an algorithm, and
- dealing with problems for which a recursively defined algorithm
cannot readily be found.
In this exercise, you will apply two different generalisation
techniques to the same problem, and compare the results.
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. Is your function tail-recursive? Why / Why not?
- The function preorder' has the same specification as
preorder.
Requirements: Use exactly one help
function, which must be obtained by introducing an accumulator.
(This technique is also known as performing a descending
generalisation.) Is your help function tail-recursive? Why
/ Why not?
- The 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.)
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. Each clause must have at most one recursive
call. Is your function tail-recursive? Why / Why not?
- The function preorder'' has the same specification as
preorder.
Requirement: Use preorders as help function.
- Give recurrences for the average-case running times
T, T', and T'' of your
preorder, preorder', and preorder''
functions, respectively. Make explicit the costs of every part of
their dividing, conquering (recurring), and
combining parts, and relate these costs to the relevant
parts of these functions. State any assumptions you make.
- Derive tight asymptotic bounds Θ(...) for T,
T', and T'', using 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. Discuss
the results.
Inlämning
Din redovisning, enligt kursens etikregler, måste lämnas in senast
måndag 9 maj, klockan 10:14 (på morgonen), med hjälp av inlämningssystemet, och ska
innehålla:
- SML funktionerna för frågorna 1-4 ovan, i en *.sml textfil, körbar
under Moscow ML version 2.01 (det som inte är kod ska vara
bortkommenterat), och dokumenteras, på engelska, enligt kursens kodkonventionerna.
- Svar, på engelska, på frågorna 5-6 ovan, i en *.txt eller *.pdf
eller *.html fil.