cs2102
Discrete Mathematics
This is a preserved file from cs2102 Fall 2016. An updated version may exist at https://uvacs2102.github.io/

Problem Set 8 Revisions


There are three important revisions to Problem Set 8:

  1. The definition of height for Problem 4 should have included that the height of the null tree is 0.

  2. The definition of the OrderedBinaryTree before Problem 7 did not make sense for constructing nodes where one (or both) of the subtrees are null. I have added clauses that allow empty trees to be used as the subtrees in a node. Without these, it would not be possible to construct any trees (other than the base null tree), since it would not be sensible to satisfy the maximum or minimum constraints for the null tree. It makes more sense to consider these undefined for the null tree, so it would be impossible to satisfy the constructor constraints without adding the disjunction clauses that allow the sub-trees to be null.

  3. For Problem 11, the definition of length using list_accumulate should be list_accumulate(lambda a, b: b + 1, lst, 0).

The version now posted has these revisions. If you already found work-arounds to these problems in your solutions, you can add a note to your assignment indicating this and don’t need to revisit them, but otherwise, please solve the revised problems.