1.1 Learning Objectives:

• More on recursion
• More on pointers - handling multiple references to an object
• More on computing Big O
• Parenthesis free notation for polynomials
• More on inductive proofs

1.2 What is given

• polyTree.tu : A class that handles polynomials represented as a binary tree -- part 1. It is a solution to Assignment 3
• poly2.tu : A class that handles polynomials represented as circuits -- part 2.
• treeNode.tu: A class that handles polynomials represented as a binary tree.
• debug.tu : A class that handles debug flags - modified from Assignments 2 and 3.
• polyCirc.dem : A demonstration program that you can use to test your program
• circNode.dem : A demonstration program that you can use to test your modified treeNode.tu
• sample.in : An example input file that you use with polyCirc.dem. The file may be changed up to Wednesday, April 2, 10:30am. Be sure to obtain a copy after that date to use with rundemo. sample.in original version before April 2.
• sample.out : The output from the sample input. sample.out original version before April 2.
• rundemo : A script for running the polyCirc.dem that produces a file to hand in.
• Cover page To be the first page handed in.

1.3 What to hand in

• Task 2 -- Modified treeNode.tu
• Tasks 3 & 5 -- poly2.tu -- any modified procedures/functions in polyCirc.tu (the modified polyTree.tu) and other substantial changes should be moved to poly2.tu. Do not hand in polyCirc.tu as we do not want to see unmodified program parts.
• Task 4 -- Answers to the questions
• Task 6 -- rundemo.out -- To be safe that you have used the final version of sample.in be sure to get a copy of sample.in after Wednesday, April 2, 10:30am, and then create rundemo.out.

I would recommend reading over and thinking about the entire assignment before starting any of it.

---

2 Multiple Access and Garbage Collection

In some applications, the same object will be used in a number of different contexts (eg., in the polynomial (x+y)*z + y/(x+y), the sub-polynomial (x+y) appears twice). Space can be saved by not having many copies of this object. Instead, each context will have a pointer to this same object in memory. However, problems arise if one context wants to change or delete the object when the others do not. We will not allow an object to be changed once it is created. Therefore, the only problem is with deletions.

The problem is as follows. Suppose that a context is pointing at an object and no longer needs it. It cannot free the object for fear that another context is using it. On the other hand, it cannot drop the object for fear that if no other context is pointing at it, a memory leak will be caused. Garbage collection solves this problem by keeping track of whether the object is being pointed at and freeing the memory space only when no pointer is pointing at it.OOT does not provide garbage collection. This is your first task. Before reading on, think. What is the minimal information that needs to be maintained about an object to know when it can be freed? Is it required to keep a full list of who is pointing at it?

You are to modify the class Node in treeNode.tu in the following ways:

1. Add the variable nPointingAtMe that is to always contain the number of pointers pointing at the Node object. What value does this variable need to be initialized to (ie. required value when the object is first created)?
2. Write a routine that allows the user to point another pointer at this same object.
   Instead of using:
       new p
       q := p
   the user must use:
       new p
       q := p->PointAtMe()
3. Write a routine that sets a pointer to nil that previously pointed at a Node object.
   Instead of using
       free p
   the user must use:
       p := p->FreeMe()
   Besides setting p to nil, the routine will free the object if no other pointer is pointing at it. Note that FreeMe is supposed to free itself (suicide). My first attempt at this was with the OOT line "free self". Recall "self" is a pointer to the object itself. This however did not work. Why doesn't it work? My second attempt worked as follows.
       var p : ^Node := self
       free p
4. Use a flag to indicate whether debug statements should be printed. When the flag is set to true, the code on the left should have the results on the right. (See the file circNode.dem)

var p,q,r : ^Node new p p->info := "fun" q := p->PointAtMe() r := q->PointAtMe() p := p->FreeMe() q := q->FreeMe() put r->info r := r->FreeMe() if p=nil & q=nil & r=nil then     put "ok" end if put "New count is ", Debug.count0 put "Free count is ", Debug.count1 assert(Debug.count0 - Debug.count1 = 0) put "#'new = #'free"

Pointing: nPointingAtMe = 2 Pointing: nPointingAtMe = 3 Dropping: nPointingAtMe = 2 Dropping: nPointingAtMe = 1 fun Freeing: nPointingAtMe = 0 ok New count is 1 Free count is 1 #'new = #'free

5. If your program works, you do not have to hand in this output. If your program does not work, indicate this.

Note: With PolyCircuits memory management becomes more difficult than with PolyTrees. The Debug module now contains 10 counters. Use the counter0 to count the number of times a new Node is created, and counter1 to count the number of times a Node is freed. The difference, counter0 - counter1, should be zero after all PolyCircuits have been finalized. By printing the values of counter0, counter1 and their difference, you have useful information about how your program manages memory, and how compact is the representation of your circuits.

3 Circuits Instead of Trees.

A circuit is defined to be a collection of gates (in this case +, -, *, and / gates) in which the output of one gate can feed into any number of other gates. This is in contrast to a formula in which the circuit is a tree. You are to modify the class PolyTree in polyTree.tu from assignment 3 to be the class PolyCircuit in polyCirc.tu.

1. Globally change the word "Tree" to "Circuit".
2. Use your modified Node class by replacing the appropriate code with q := p->PointAtMe() and
   p := p->FreeMe(). At this point the program should work as a polyTree.
3. Change the routine Operator so that h->Operand(f,"+",g) does not initialize f and g as the empty polynomial. Instead, f and g will continue to point at the same polynomial that they did. The result is shown in the left side of the following diagram. The result of h->Operand(f,"+",f) is shown on the right side of the following diagram. Be sure to handle the cases h->Operand(h,"+",f), h->Operand(f,"+",h), and h->Operand(h,"+",h).

h \_____ | + | f ----- g \_____/ \_____/ | | | | ----- -----

h \_____ | + | ----- / \ f \_____/ \_| | -----

4. Change the routine Copy so that it does not create new nodes, but only copies the pointer, called a shallow copy. The original Copy procedure was a deep copy.
5. The recursion for the Finalize operation must be moved to FreeMe. Suppose for example that node u is pointed to by many pointers and that node v is pointed to by node u, but by no other pointers. Think about what should happen when FreeMe is called for u. After FreeMe has been called for u enough times so that the counter nPointAtMe goes to zero the node must freed. What then happens to node v?
6. Think. What else needs to be changed (if anything)? If something else needs to be changed then remove it from polyCirc.tu and put it into poly2.tu.
7. Test the program to make sure that it works. You can use the tests from assignment 3. Again, if it works, no need to hand in these tests. If it doesn't work hand in the tests and indicate what does not work.

4 Questions

• Consider the following input to polyCiruit.dem.

operand p1 = y op p1 = p1 * p1 operand p2 = 3 op p3 = p1 + p2 op p4 = p1 * p3 pretty p4 final p1 final p2 final p3 final p4

1. Algebraically, what is the polynomial produced?
2. What is the output of pretty p4? Describe how PrettyPut still prints a tree even though the data structure is a circuit.
3. Draw a picture of the data structure in memory. Be sure to differentiate between the polyCircuit objects and Node objects and show where all the pointers point.
4. Trace the execution of FreeMe when final f4 is executed, ie. draw the tree of stack frames that gets called recursively. Indicate what the data structure looks like at EACH stack frame. Indicate which stack frames sets pointers to nil and which actually free memory.
5. When the node containing "3" is free'd draw the picture of the stack frames that are in memory. In addition to the input and output for the procedure call that each stack frame represents include a description of the data in the node and the line of the program that made the call.
• The circuit representation requires less space than the tree representation. Let n be the number of nodes (operands and operators) in the circuit representation of a polynomial and N be the number for the tree representation for the same polynomial. In the most extreme example, there is a sequence of polynomials (one for each value of n) for which N=2**n - 1.
1. Sketch a picture of the circuit and its corresponding tree for n=4, N=15.
2. Give a simple demo file that produces the circuit.
3. What is the bigO time complexity, in terms of either n or N, of running Put on this sequence of circuits? Explain why.
4. What is the bigO time complexity, in terms of either n or N, of running Finalize on this sequence of circuits? Explain why.
• Sketch a picture of a circuit that represents the polynomial 2y^2 + 3y^6, while using as FEW nodes as possible. Remember to reuse (ie point to more than once) as many of the sub-circuits as possible.
• Consider the following proof by induction.

Lemma: For every set of horses, all the horses in the set are the same colour.
Proof by Induction:
Let S(n) be the statement that for every set of horses of size n, all the horses in the set are the same colour.
Base Case: S(1) is true. Every set containing one horse contains only one colour of horse.
Induction Step: Assume S(n-1). Consider an arbitrary set of n horses. Arbitrarily order the horses. Consider the horses numbered 1, 2, ..., n-1. This is a set of n-1 horses. Hence, by the assumption, they are all the same colour. Now consider the horses numbered 2,..., n. This too is a set of n-1 horses and hence are all the same colour. By the first application of the assumption, we know that horse 1 and horse 2 are the same colour and by the second, we know that horse 2 and horse n are the same colour. It follows that horse 1 and horse n are the same colour. Hence, for this arbitrary set of n horses, they are all the same colour. Because this is true for an arbitrary set of size n, it must be true of all sets of size n. This proves S(n).
By way of induction, this proves that S(n) is true for all n.

1. Is this proof correct? If no, how does does the proof break down?
2. Is there a moral that can be taken from this that tells of a potential source of bugs when writing recursive programs? What is that moral and how can it be avoided?

5 Recursive Programs

Add the following routines to PolyCircuit. Like the recursive programs in assignment 3, each of these routines will require a recursive helper routine. The helper routine is passed a pointer to the root Node of the PolyCircuit.

1. Postfix notation has the advantage of not requiring brackets to specify order of operations. Write a routine Postfix() that prints the polynomial self on a single line using postfix notation. The following table shows the correspondence between postfix notation and infix notation.

Infix notation x+y (x+y)*(a+b) ((a+b)*c)/d a+(b*(c/d))

Postfix notation x y + x y + a c + * a b + c *d / a b c d / * +

2. Write a routine Derivative( f : ^PolyCircuit, variable : string ) that initializes the polynomial self to be the derivative of f with respect to the indicated variable, eg ff->Derivative( f, "x") gives ff := df/dx. The poly f should remain unchanged. The program will consider the following cases:
• If the poly is the operand "x", (ie poly->info = variable), then the derivative is 1.
• If the poly is a operand other than "x", (eg "y", "3.7", "fun"), then the derivative is 0.
• If the polynomial is g+h, then the derivative is g'+h'. Note you need to recursively take the derivative of poly->left and poly->right. Then you create a node that will add them together. Subtraction is the same rule as addition.
• If the polynomial is g*h, then the derivative is g'*h + g*h'.
• If the polynomial is g/h, then the derivative is (g'*h - g*h')/(h*h). Recall that all of those references to g and h can point to the same sub-polynomial.
3. The polynomial created by Derivative will not be in the simplest form. For example, the derivative of x*y with respect to x will be computed to be 1*y + x*0. This should be simplified to y. Write a routine Simplify() that will make these simplifications. It should recursively apply the following rules.

1*f = f      f*1 = f      0*f = 0     f*0 = 0
0+f = f      f+0 = f      f-0 = f
f/1 = f      0/f = 0

The following is an example of how the program works.

Polynomial to simplify _ * _ / \ _ + _ _ * _ = (yz + 0x) * (0x * z) / \ / \ * * z / \ / \ y z 0 x Recursively simplify the left subpoly, giving ___ * _ / \ / _ * _ = (yz) * (0x * z) / / \ * * z (Note that only one link to 0x was freed) / \ / \ y z 0 x Recursively simplify the right subpoly, giving _ * _ / \ * 0 = (yz) * (0) / \ y z Check to see if any of the three rules applies. In this case the second one does. Use FinalizeRec to recursively free the left subtree. Use FreeMe to free the root "*" node. Return a pointer to the 0 node. (Recall that a node cannot be changed once it is created. See section 2.)

---

6 Running the Demo Program

Create your own example demonstration input file in mysample.in. It should be approximately the same length as sample.in.

Copy polyCircuit.dem, sample.in and rundemo to your directory containing your PolyCircuit program. Execute the shell script program rundemo. Make sure you have set its protection mode to executable. The script runs the demonstration program polyCircuit.dem on sample.in and outputs a comparison of your output with sample.out. It then runs polyCircuit.dem on your test file mysample.in. The output is put into the file rundemo.out.