CSCI 3136 Assignment 6: Parameter Passing and Tree Traversals
Assignment 6: Parameter Passing and Tree Traversals
Question 1: Pass by Reference in Java (4 points)
In Wednesday’s class, we discuss parameter passing modes. Assume foo calls bar with some local variable x of foo as argument. When passing x to bar by reference, this means that bar receives a pointer to x’s location in foo’s stack frame. In particular, bar can make arbitrary modifications to the content of foo’s variable x. C only has pass by value, but it has explicit pointers. Thus, we can easily simulate pass by reference using code like this:
void bar(int *z) {
// Modify foo's x via assignment to *z. For example,
*z = 5;
}
void foo() {
int x;
bar (&x);Java cannot pass function arguments by reference either. For primitive values, it uses pass by value. For objects (ones created using new), it uses pass by sharing. As we discuss in class, pass by sharing is what we get when we combine pass by value with a reference model of variables. In particular, in the following code snippet,
void bar(Obj arg) {
...
}
void foo() {
Obj obj = new Obj();
bar(obj);
}bar does not know where in memory foo’s obj variable is stored. Thus, it cannot change which object obj points to. However, bar’s argument arg points to the same object that obj points to. Thus, if bar modifies arg in place (as in arg.makeSomeChanges()), then this also updates (the object pointed to by) obj, because obj and arg point to the same object. If we assign a new object to arg (as in arg = new Obj()), then this does not change the object stored in obj.
Now, here is your task. Pass by reference can be very useful in some situations. Provide an implementation of pass by reference in Java. To be precise, let’s recap what we can do with pass by reference
- The callee (bar) can modify the object stored in the caller’s (foo’s) variable and
- The callee can store a completely new object in the caller’s variable.
The former is supported using call by sharing. The latter is not. Your task is to implement a mechanism that can be used to pass an object from the caller to the callee, and the callee can communicate changes to this object back to the caller or send a completely new object back to the caller.
Of course, this can be done by having the callee return the new or updated object as its return value. Assume you can’t do this. You should communicate the result back to the caller only through the callee’s arguments.
Note:: The solution is quite simple. If you find that you’re writing many lines of code, you’re seriously overcomplicating things.
Question 2: Tree Traversals in Haskell (4 points + 2 bonus points)
Haskell data structures, take 2 (after last week’s Haskell question ended up being too ambitious). Here’s an implementation of a rooted tree storing some elements of type a:
data Tree a = Tree a [Tree a]This says that a tree has a root storing some element of type a and a list of children that are themselves trees storing values of type a. If the list of children is empty, the node is a leaf.
When writing algorithms that work with trees, it is often useful to number the nodes in a tree in some fashion. Such a numbering algorithm converts a Tree a into a Tree (a, Int) of the same shape. In other words, the value stored at each node has been replaced with a pair whose first component is the value stored at the node originally, and the second component is the number of the node.
There are three common numberings of the nodes of a tree: Preorder numbering: If the tree has n nodes, these nodes are numbered 1 through n so that the following conditions hold: The number of every node is less than the number of any of its children.
If v and w are children of u, and v appears before w in the list of u’s children, then all nodes in the subtree with root v have smaller numbers than all nodes in the subtree with root w.
Less formally, this simply says that we number the root first and then we recursively number the nodes in each of its subtrees, from left to right.
Figure 1: Illustration of preorder numbering
Postorder numbering: If the tree has n nodes, these nodes are numbered 1 through n so that the following conditions hold: The number of every node is greater than the number of any of its children.
If v and w are children of u, and v appears before w in the list of u’s children, then all nodes in the subtree with root v have smaller numbers than all nodes in the subtree with root w. Less formally, this simply says that we recursively number the nodes in each subtree, from left to right, and finally we number the root.
Figure 2: Illustration of postorder numbering
Level-order numbering: If the tree has n nodes, these nodes are numbered 1 through n so that the following conditions hold: If u is closer to the root than v, then u has a smaller number than v.
All nodes at the same distance from the root are numbered left to right. Formally, assume that v and w have the same distance from the root. Let u be the lowest common ancestor of v and w, that is, the node farthest away from the root that is an ancestor of both v and w. Then v and w belong to different subtrees v and w of u. Node v has a smaller number than node w if and only if v appears before w in the list of children of u.
Figure 3: Illustration of level-order numbering Implement two functions
preorderNumbering :: Tree a -> Tree (a, Int)
postorderNumbering :: Tree a -> Tree (a, Int)Your functions should visit every node of the input tree only once.
Bonus: Level-order numbering and laziness
Implement a function
levelOrderNumbering :: Tree a -> Tree (a, Int)Your function should visit every node of the input tree only once. In an imperative language, we would compute a level-order numbering essentially using breadth-first search. We would maintain a queue of nodes to be visitied, initialized to hold the root. Then we would repeatedly remove a node from the queue, give it the next number, and add its children to the end of the queue. This doesn’t work so well in a functional language, because we cannot update nodes in place; we can only return new nodes. The problem is that the tree we build from these new nodes needs to have the same shape as the original tree, something that is easiest if we can traverse the original tree recursively (that is, using depth-first search) and have each recursive call return a tree of the same shape as the tree on which we made the recursive call. This inherently visits nodes in preorder, not in level order.
There are at least two ways to solve this problem functionally. To complete this bonus question, you can choose either of them. Given the difference in the amount of coding involved, I’d personally lean towards the second solution, which is also faster. Furthermore, it forces you to think about lazy evaluation.
The Conceptually Simple Solution That is Hard to Implement
We flatten the tree into a list of values, arranged level by level, left to right. In addition, we also produce a sequence of node degrees, again level by level, left to right.
Next we number the entries in our list of values, producing a list of value-number pairs.
We reconstruct a tree of the original shape from this list of valuenumber pairs and the list of node degrees.
The Conceptually Harder Solution That is Easy to Implement
Assume we have a helper function levelOrderHelper :: Tree a -> [Int] -> (Tree (a, Int), [Int])
This function takes as argument a tree t and a list ns with at least as many entries as t is deep. Assume that ns = [n1, n2, n3, ...]. Then levelOrderHelper gives the root of t the number n1. It numbers the nodes on
the next level (the children of the root) n2, n2 + 1, .... It numbers the grandchildren of the root n3, n3 + 1, ..., and so on. What levelOrderHelper returns is a tree t' :: Tree (a, Int), where every node
now stores its original value and the number it was given, and a list ns' = [n1', n2', n3', ...]. The relationship between ns and ns' is the
following: We have n1' = n1 + 1. In general, if there are mi nodes on the ith level the tree t, then ni' = ni + mi.
Figure 4: Illustration of the function levelOrderHelper This function levelOrderHelper is easy to implement recursively. Thanks to lazy evaluation, levelOrderNumbering becomes a two-liner that simply calls levelOrderHelper with the right list ns as argument. Note that the root
should receive the number n1 = 1, the first child of the root should receive the number n2 = n1 + 1, the first grandchild of the root should receive the number n3 = n' + 1, where n' is the number of the rightmost child of the root, and so on. To choose this implementation of levelOrderNumbering and earn the bonus marks, you have to figure out the rest yourself.
