Assignment 2

This assignment did not go as well as the last one. I had an extremely hard time with question 1. My first instinct was to manipulate the number a tree with n - 1 nodes in some way to get the number of unique trees with n nodes. The zero case kept throwing off my formulas I tried pretending that it equaled zero but this still didn't get me anywhere.

Once I realized that wasn't going to work I broke it up into the cases where the root had 1, 2 or 3 children. The case where it had 1 child was easy because the tree would just look like a tree with n-1 nodes plus an extra node on top. However the cases where the root had two or three children were much more complicated because there were two or three different sub trees and the only restriction then the number of nodes in them was on the sum of their nodes. So I abandoned this idea.

Next I tried the hint suggested on the bulletin board. I didn't get far with this because I could not come up with a formula for any of the cases unless the left subtree had all the nodes. Also I was confused how to generalize it because with a bigger n you would have to consider more cases(eg. when the left sub tree has 1, 2, 3,..., n-1 nodes).

I looked of the bulliton board and found some interesting questins from when this question was on assignment 1. In responce to someone's question Danny had given a computer generated list of all the unique trees from n=1 to n=5. I thought that maybe if I could understand how an algorythm would come up with all the unique trees it would be eaiser to make a formula that counted them. After inspecting danny's simulation for a while I broke the problem up into the following cases. 1: the left sub tree had more then zero nodes. 2: the middle subtree had more then zero nodes and the left sub tree had zero nodes. 3: the right subtree had more then zero nodes and then other two had no nodes. This led me to a lot of very promiseing formulas but no matter how I tried manipulating them I could not find one that worked for n = 0 through n = 5.

I remembered that I gave up on my second aproach necause it seemed too hard but not becasue I ran out of ideas to try. So I went back to it and eventually came up with formula's for the cases where the root had two and three subtrees. The third case looked particularly ugly and involved a nested summation of trees of different lengths multiplied together. But I think it worked. For all of my other methods I was just trying different numbers to get a formula that worked but I actually understood how this formula worked.

I wasn't sure how to go about asking for help with this problem because I didn't really know where I was stuck. Also I didn't start the assignment until friday so I couldn't go to office hours. That probabally would have saved me a lot of time. Maybe next time I'll try to get started on it sooner. And hopefully I won't have three assignments and a midterm on the same day again.