AD1 -- SML Assignment 4

Problem generalisation is a powerful technique for: 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:

  1. 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?
  2. 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?
  3. 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?
  4. The function preorder'' has the same specification as preorder.
    Requirement: Use preorders as help function.
  5. 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.
  6. 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.


Din redovisning, enligt kursens etikregler, måste lämnas in senast måndag 27 februari, klockan 08:14 (på morgonen), med hjälp av inlämningssystemet, och ska innehålla: