1. Homepage
  2. Programming
  3. CSCI 3136 Assignment 6: Parameter Passing and Tree Traversals

CSCI 3136 Assignment 6: Parameter Passing and Tree Traversals

Engage in a Conversation
JavaParameter PassingCSCI 3136Principles of Programming LanguagesCanadaDalhousie University

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: CourseNana.COM

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, CourseNana.COM

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. CourseNana.COM

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 CourseNana.COM

  • 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. CourseNana.COM

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. CourseNana.COM

Note:: The solution is quite simple. If you find that you’re writing many lines of code, you’re seriously overcomplicating things. CourseNana.COM

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: CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

Figure 1: Illustration of preorder numbering CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

Figure 2: Illustration of postorder numbering CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

Figure 3: Illustration of level-order numbering Implement two functions CourseNana.COM

preorderNumbering :: Tree a -> Tree (a, Int)
postorderNumbering :: Tree a -> Tree (a, Int)

Your functions should visit every node of the input tree only once. CourseNana.COM

Bonus: Level-order numbering and laziness

Implement a function CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

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. CourseNana.COM

Next we number the entries in our list of values, producing a list of value-number pairs. CourseNana.COM

We reconstruct a tree of the original shape from this list of valuenumber pairs and the list of node degrees. CourseNana.COM

The Conceptually Harder Solution That is Easy to Implement

Assume we have a helper function levelOrderHelper :: Tree a -> [Int] -> (Tree (a, Int), [Int]) CourseNana.COM

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 CourseNana.COM

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 CourseNana.COM

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 CourseNana.COM

following: We have n1' = n1 + 1. In general, if there are mi nodes on the ith level the tree t, then ni' = ni + mi. CourseNana.COM

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 CourseNana.COM

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. CourseNana.COM

Get in Touch with Our Experts

WeChat WeChat
Whatsapp WhatsApp
Java代写,Parameter Passing代写,CSCI 3136代写,Principles of Programming Languages代写,Canada代写,Dalhousie University代写,Java代编,Parameter Passing代编,CSCI 3136代编,Principles of Programming Languages代编,Canada代编,Dalhousie University代编,Java代考,Parameter Passing代考,CSCI 3136代考,Principles of Programming Languages代考,Canada代考,Dalhousie University代考,Javahelp,Parameter Passinghelp,CSCI 3136help,Principles of Programming Languageshelp,Canadahelp,Dalhousie Universityhelp,Java作业代写,Parameter Passing作业代写,CSCI 3136作业代写,Principles of Programming Languages作业代写,Canada作业代写,Dalhousie University作业代写,Java编程代写,Parameter Passing编程代写,CSCI 3136编程代写,Principles of Programming Languages编程代写,Canada编程代写,Dalhousie University编程代写,Javaprogramming help,Parameter Passingprogramming help,CSCI 3136programming help,Principles of Programming Languagesprogramming help,Canadaprogramming help,Dalhousie Universityprogramming help,Javaassignment help,Parameter Passingassignment help,CSCI 3136assignment help,Principles of Programming Languagesassignment help,Canadaassignment help,Dalhousie Universityassignment help,Javasolution,Parameter Passingsolution,CSCI 3136solution,Principles of Programming Languagessolution,Canadasolution,Dalhousie Universitysolution,