FUNCTIONAL PEARLS Maximum marking problems

Journal article

Here are two puzzles for you to solve. First, consider the binary tree in figure 1. Take a pencil (I am assuming that this is your personal copy of JFP!) and mark some of the nodes in such a way that the sum of the values of marked nodes is as large as possible. The catch is that you cannot mark all the nodes: if you mark a node, then you are not allowed to mark its parent. Equivalently, no two marked nodes can be contiguous in the tree. The second puzzle is similar though both the datatype and constraint are different. Consider the rose tree of figure 2 (a rose tree is a tree with arbitrary branching structure). Mark some of the nodes so that all marked nodes are now contiguous in the tree. For example, if you mark the root value 4 and the leaf value 1, then you must also mark the values 5 and −3 along the path from 4 to 1. Again the idea is to maximise the sum of the marked nodes. Of course, if all values were nonnegative, the best solution would be to mark all nodes. But they aren’t and the maximum sum is obtained only by a judicious choice of marking. Answers to both puzzles are given at the end of the paper. The Maximum Marking Problem (MMP) is the problem of marking the entries of some given data structure in such a way that a given constraint is satisfied and the sum of the values associated with marked entries is as large as possible. By the end of this pearl, you will be convinced that there is a linear-time solution for both the puzzles described above.

• Publisher: Cambridge University Press
• Journal: Journal of functional Programming
• Issue: 11
• Publication date: 2001-01-01
• Subjects: Computing Laboratory