Polya Problem Solving Question

I think the toughest question we've been given all year was from Assignment 1/Assignment 2. Yep, I'm talking about the ternary tree question. The question can be found here
http://www.cdf.toronto.edu/~heap/236/f08/A2/a2.pdf (It's the very first question on the assignment). Anyway, I looked back and realized that many of the methods I used on my way to coming up with a solution to this problem were from Polya himself. So I've decided to go back and reanswer the question using the Polya Problem Solving techniques.

1. Understanding the Problem

To understand this problem, you have to first understand certain characteristics of a ternary tree. I know that all trees in general (whether it be binary, ternary, quatrenary (sp?), etc.) all comprise of a root node. In this case, a ternary tree will have a root node plus at least 3 child nodes. The only exception to this rule is the empty tree. Also when I say that a ternary tree must have at least 3 child nodes, I mean that in kind of an "abstract-way". Don't get me wrong, a ternary tree could just have the root node with zero children, but when drawing ternary tree it`s easy to look at it as if there are exactly three spots available from the root node. Whether these be empty or not is totally dependent on the question.

My goal is to form some sort of algorithm that finds the number of non-equivalent ternary trees with n nodes, where n /in N. The defn. of a non-equivalent ternary tree could be found in the question.


2. Devise A Plan

First things first, I'm going to completley forget about the mathematical mumbo-jumbo and think of this question in a much simpler form. I know that every ternary tree has exactly ONE root node no matter what, so given n nodes I can make things simpler by breaking the question down to "the # of non-equivalent ternary trees with n-1 nodes, where n /in N."

Then I will treat the number n-1 as a "budget" of nodes I'm allowed to spend on any ternary tree, T. I also know that any T will have at least 3 child nodes connecting from the root. I will call these left (TL), middle (TM), and right (TR). Then I have n-1 nodes to spend between L, M, and R. Thinking about this question in a straight-forward, logical form should produce the right answer. So, let's give it a try:


3. Carry Out The Plan

Let T be an arbitary ternary tree with n nodes. Then when n >= 2 I know T must have three sub-trees. Let TL, TM, and TR be defined as the left, middle and right subtrees of T respectively. Then minus the root, R, I know that TL, TM, TR are comprised of n-1 nodes. Then I have a "budget" of n-1 nodes to "spend" on either TL, TM or TR.

First I will consider TL. Assume k is the number of nodes I choose to spend on TL (\exists k \in N). Then I have n-1 nodes to choose from, so k can be any number of nodes within n-1 and k must be less then or equal to n-1. Then I have k=0Zn-1 F(k). Now I must consider TM and TR. Assume n is the number of nodes I have left to spend on TM and TR (\exists m \in N). Then I have n-1-k nodes to choose from, since I originally had n-1 nodes and I've already spent k nodes on TL. Then m is dependent on k, m can be any number of nodes within n-1-k, and m <= n-1-k. Then I have m=0Zn-1-k F(m). Then I have n-1-k-m nodes left to spend on TR. I can treat TR as being fully dependent on k and m, because all the nodes left in my "budget" must ultimately be "spent" in the end. Then the total number of nodes in TR must be equal to n-1-k-m, so I have F(n-1-k-m).

Adding together all of the possible combinations formed by each k and m will give you the total number of non-equivalent ternary trees of n nodes. Then k=0Zn-1 F(k) * m=0Zn-1-k F(m) * F(n-1-k-m) is true!


4. Conclusion

Sometimes looking at the question in a purely logical and simplistic way is very helpful in figuring out the solution. In this case, I used the number of nodes available to me as a "budget" and applied it to any arbritrary ternary tree. In the end, it worked out perfectly! Obviously you would use induction to prove this sort of thing, but I was simply just showing the "method" I used to base my induction around.

10th Entry

2 more weeks left of school and we're outta here... I honestly can't wait! As good as this semester has been, I'm exhausted and in definite need of a break. It's been problem-set after assignment after midterm after lab after who knows what --- so yeah ... not doing ANYTHING for a little while sounds kind of nice.

I'm really interested in what we've been learning for the past couple of weeks in lecture. I find the regular expression stuff fun to do, especially constructing the DFSA's/NFSA's. It was complicating at first, but now that I've gotten the hang of it everything seems to come naturally. I was able to complete #4 on A3 with ease, and I'm quite proud of myself because of it considering I usually need help (even if it's just a little) for practically every question on a 236 assignment.

Other then that, the 6th and final Problem Set is due tomorrow and I was JUST able to finish it. It wasn't too-too bad, just a little a long.

Everything else is good. I'm planning on doing a Polya question over the weekend, so I'm gonna look a problem that catches my eye and attempt it over the weekend. Until then, cya!

9th Entry

This week we've begun looking more in-depth into Languages and Reglar Expressions. Now I've got to be honest, up until this morning's lecture I was pretty lost -- I didn't even really know what a "regular expression" was...

However after Danny's example in class today, I think I've grasped a somewhat understanding on the subject. Of course like everything else, it's going to take some practise and getting used to before I feel totally comfortable with the whole "regex" thing, but at least I kind of know what I'm doing now!

Assignment 3 was released yesterday so I'm gonna get cracking on that asap. I can't beleive we're already down to the last assignment/test/problem-set! This semester seriously just flew by.

8th Entry

I had some time so I thought I'd post a quick entry before I continue studying for the midterm tomorrow..

The only thing that has me worried right no is the time-complexity/closed-form/monotonic stuff -- it's so confusing!! Well, not all of it, but for the most part I'm just sitting here going "Wow...that's a lot of numbers..." Haha. I went to Danny's office hours today and he helped me understand a lot of it, but after reading through my notes and examples from class I'm still kind of lost. I mean I know where the numbers are coming from, but when it comes to sitting down and writing the test on my own -- that's where I run into trouble.

Anyway I hope it goes well tomorrow! This week (like the past couple of weeks before it) has been super busy. I'm trying to balance studying for this midterm, a CSC207 assignment and a MAT137 midterm next week ... oh well, after that, things should get a bit less crazy.

That's it for now.. so until next week, cya.