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.

Test 1

Test 1 went a lot better then I was expecting. I thought there was a perfect, questions to time ratio. I had just enough time to look over my test before handing it in and I was actually able to fix a mistake I made in question 2. I didn't really understand why the claim in question 3 was true at first but the good thing about induction is that you don't always have to fully understand something to prove it. I rushed through the first two questions before I realized that I would have plenty of time to finish so for future tests in this class I think I will read over the hole test and estimate how long each question will take me so that I can write more in depth proofs.

Assignment 1 reflection and Test 1 preporation

Assignment 1 ended up going quite well. Even though I accidentally handed it in instead of problem set two. I was stuck on question 3 for a long time but I eventually realized that I didn't know what well ordering was so after looking it up question 3 wasn't so hard. I'm a little nervous about the test tomorrow because the questions on the assignment all took me a long time to figure out but I've heard that the test questions will be pretty straight forward. To prepare for the test I've just been reading over previous course notes but I plan on trying out some proofs from the notes and old problem sets too. So far the part of this class that I've been having trouble with is keeping up with this blog. But I just dropped out of calculus so I should have a lot more time now to stay on top of my other classes.