Christos' CSC236 SLOG

Polya's steps to solving a problem

2008-12-05T17:09:00.000-08:00

I chose Problem # 1 from Assignment # 2 (that was originally Problem # 4 from Assignment # 1). I will present my solution using Polya's prescription for solving problems.

The problem is the following:

Define the set of ternary trees T_3 as:

(a) The empty tree, \lambda, is an element of T_3,

(b) If trees T_L, T_M, T_R are elements of T_3 having no nodes in common, and R is a node that is not in T_L, T_M or T_R then T = (R, T_L, T_M, T_R) is an element of T_3. We call T_L the left subtree, T_M the middle subtree and T_R the right subtree, of T.

For arbitrary natural number n, find a (possibly recursive) formula for the number of non-equivalent ternary trees with n nodes. Prove that your formula is correct.

Polya's four steps are:

1) Understanding the problem.

2) Devising a plan.

3) Carrying out the plan.

4) Looking back.

1) First I had to read the problem carefully and make sure I understood what was asked. Understanding the definition of a ternary tree and what consists an equivalent ternary tree is key in order to avoid duplicates.

2) My first reaction was to draw the ternary trees with a small number of nodes say up to four or five nodes. I was expecting a pattern to emerge that would help me come up with the formula. Then I would have to prove that formula correct.

3) I started drawing the ternary trees with zero, one and two nodes. I got 1, 1 and 3 respectively. The I started drawing trees with three nodes. Things started to look a bit more complicated but nothing too hard. The total number was 12. When I moved to four nodes things got messy. I was working hard to avoid duplicates. I got 55 ternary trees with four nodes.

Just to get an idea of what my drawings looked like, here is a picture of some of the ternary trees with four nodes:

When I moved to n=5, after hours and hours of careful drawing, I got 300 ternary trees. I talked to Professor Heap and he told me that the correct number for n=5 is 273. So I was not able to avoid duplicates. I spent more hours trying to figure out where I went wrong. I managed to find the problem (symmetry was to blame together with carelessness on my part). Even with the correct number I was not able to find a pattern. Clearly my plan was not working.

4) Looking back, it's obvious that my plan was not working. I had to come up with a new plan. The next thing that came to my mind was to approach the problem with a combinatorial perspective. So, I went back to step 3.

3) Here is a proof of the problem using a combination of combinatorics and complete induction:

First let T(n) be the number of ternary trees with n nodes.

The recursive formula that gives the number of ternary trees with n nodes is:

(i) T(n) = 1, for n=0
(ii) T(n) = Sum_i={0}^{n-1}Sum_j={0}^{n-1-i}[T(i)*T(j)*T((n-1)-(i+j))], for n>0

A ternary tree has the root note and a left subtree, a middle subtree and a
right subtree. Any of the subtrees can be the empty tree with zero nodes. In the
forumla above i stands for the number of nodes the left subtree can have and
of course it can have zero nodes up to (n-1) nodes (the other is the root node).
j is for the number of nodes that the middle subtree can have. In this case, j
can be zero, all the way up to (n-1)-i. Note that after i and j are selected,
the number of nodes that the right subtree has is determined since all of the
nodes must add up to (n-1).

Next, I will prove the following statement (claim),

P(n): "The recursive formula above gives the number of ternary trees with n
      nodes."

Proof (using the principle of complete induction):

Base Case:             For n=0, when we have zero nodes, we have only one
       possibility, the empty tree. The recursive forumla above
       also tells us that T(0)=1 so P(0) holds.

Induction hypothesis: Assume that the formula is correct for ternary trees with
                      one node, for ternary trees with two nodes, for ternary
       trees with three nodes, ..., for ternary trees with (n-2)
       nodes, for ternary trees with (n-1) nodes. That is, we
       assume that all of P(1), P(2), P(3),..., P(n-1) are true.

Now consider ternary trees with n nodes. If we exclude the root node, we have
(n-1) nodes to distribute among the subtrees. When the number of nodes for the
left and middle subtrees is determined, the number of nodes for the right
subtree is also determined because they need to add up to n-1. So, if we have i
nodes in the left subtree and j in the middle one, the right subtree has
(n-1)-(i+j) nodes. The total number of subtrees for this particular case (for
specific i and specific j) is the number of the different combinations of left,
middle and right subtrees. We know that we get the total number of combinations
by multiplying them. So, for a specific i and a specific j, the total number is
given by T(i)*T(j)*T((n-1)-(i+j)). That's the expression we have inside the
double sum. So, at each step, the formula counts the total number of ternary
trees when we have i nodes in the left subtree, j nodes in the middle subtree
and the remaining nodes in the right subtree. Note that i, j as well as
(n-1)-(i+j) get values from zero to n-1 (including the end points), therefore
they are in the range we want them to be for us to be able to use the induction
hypothesis.

So, by our assumption, we know that we have the correct number of ternary trees
with one node, with two nodes, ..., with (n-1) nodes. Thus, we are considering
all the different cases and at each case we have the mutliple of three numbers
that we know are correct by our assumption.

Therefore, we have that \forall n \in N, {P(0), P(1), ..., P(n-1)} \implies P(n)
and we hence, by the principle of complete induction, we can conclude that P(n)
holds for all natural numbers n. That is, we can conclude that the recursive
formula defined in the beginning of the problem gives us the number of ternary trees with n nodes, for all natural numbers n.

Week 13 - Thursday Dec 04, 2008

2008-12-05T16:35:00.000-08:00

Last week of the term! I can't believe we are in December already. It's true, time does fly.

We had test # 3 this week and it went very well. It was a fair test just like the other two tests we had for this course.

After the test we continued with PDAs and at the end of the class, the professor talked a little bit about the exam. I expect the exam to be straight forward. This year my exam schedule looks great I have lots of days to study in between the exams.

Looking back, this was my favorite course for the semester (just like CSC165 last year). I enjoyed the lectures and found the material very interesting. I even enjoyed most of the homework problems!

Good luck on the exam everyone and happy holidays!

PS I still need to post a solution to a problem using Polya's steps.

Week 12 - Thursday Nov 27, 2008

2008-12-01T12:13:00.000-08:00

Another week gone by, we are getting closer and closer to the end of this semester.

In this lecture we first saw the Pumping Lemma. I was a little bit confused in the beginning but after going over it in a couple of examples with Professor Heap I was able to understand what was really going on. I think it's very useful to have something to test whether a language is regular.

With that, we concluded Chapter 7 and we moved to a new topic: context-free grammars.

For some reason I really enjoyed constructing strings by following a set of rules. I found it really cool! The last few lectures were very interesting. I think I need to consider applying for the AI Subject POSt.

Test # 3, the final test for this class is in a couple of days. It covers the material from Chapter 7. I have to say that I find the material interesting but at the same time a little hard. We will see how it will go, I am not too worried about it.

I have a term paper for my Language and Society class due tomorrow (to go with the test for the same class) so I better continue my search for journals and articles!

Week 11 - Thursday Nov 20, 2008

2008-11-25T12:26:00.000-08:00

We started with a proof that was owed from the week before. Professor Heap proved the correctness of the DFSA we saw last week (accepting binary strings that are multiples of three). The proof used structural induction on string x.

We continued the lecture with NFSAs. We saw that every regular expression has an FSA (if we allow empty transitions) and that every NFSA defines a DFSA.

We also looked at the cartesian product method (if you paid attention to that then Problem # 4 on Assignment # 3 was easy to do).

Assignment # 3, the last assignment for this course was due Monay, Nov 24 (so it was due yesterday as I am posting this on Tuesday, Nov 25). I found this HW the easiest of the three. The hardest problem for me was Problem # 2, where we had several regular expressions and we had to prove whether or not the regular expressions denoted a language L (L was the set of all binary strings with an even number of 1s). Most of the times I can see if a regex denotes a language with a certain property but I have a hard time proving it. I guess that's always the case. I am getting better though because Problem Set # 6 dealt with this thing and Problem # 2 of Assignment # 2 and we saw an example of this in class. Practice makes perfect.

Week 10 - Nov 13, 2008

2008-11-13T22:10:00.000-08:00

We got Test 2 back today and I got exactly what I thought I would get. Not bad but not as good as Test 1. The important thing is that I know what my mistakes are and I also know how to avoid them. That's all I have to say about Test 2.

In the lecture this week we saw DFSA (Deterministic Finite State Automata). Drawing states and arrows seems fun!

I really liked that fact that you can represent a language using a DFSA quite easily. We saw how hard it was to express (L1 \intersection L2) using a regular expression but we came up with the DFSA for it fairly easily. L1 was the language that contained all binary strings with an even number of zeroes and L2 the language that contained all binary strings with an odd number of ones.

We did not see a proof of the correctness of the DFSA but it's something we will see next week. The professor felt that it was too late for that proof and that it was better suited for the first hour of next week's lecture. Couldn't agree more!

Week 9 - Thursday Nov 07, 2008

2008-11-11T15:44:00.000-08:00

Test 2!

We had test #2 this week and I found it very fair. There were three problems all of them not hard. Professor Heap really knows how to write fair tests. It's as simple as that.

Of course, I ran out of time and didn't have time to finish Problem 3 but that's pretty much the case with all of my tests. I really need to learn how to: 1) manage my time during a test more efficiently and 2) leave out the extra details from my answers.

Other than the test, we started on Chapter 7 that deals with Languages, Regular Expressions and FSAs. Problem Set #5 is due this week and it has to do with the new material. I read the notes and I find the subject very interesting but a little bit confusing too. We will see how things will evolve. I am looking forward to the next lecture.

Week 8 - Thursday Oct 30, 2008

2008-11-04T22:10:00.000-08:00

This week we continued looking at the correctness of algorithms. We moved from recursive correctness to iterative correctness. I don't have much to write today. I would just like to say that I found the iterative case much harder than the recursive case. I don't know why the idea is very similar. Just go through the code line by line and prove it works, prove that it does what we want it to do.

Test 2 is on Thursday and I am a little worried because I do not feel well prepared. I still have a day to study but with three other assignments due in the next two days I am trying to juggle everything and so far I seem to be terrible at juggling...

Week 7 - Thursday Oct 23, 2008

2008-10-27T21:36:00.000-07:00

Week 7 is gone. Time flies, that's for sure. I survived the worst week of this semester so I am happy about that.

The deadline of Assignment 2 was approaching and I was glad I solved the ternary trees question a long time ago. It seemed that it was the hardest problem and it took everybody quite some time to figure it out.

In the lecture we saw the correctness of algorithms. We looked at the binary search algorithm and we proved it's correct and we did the same with Euclid's algorithm for the gcd.

Test 2 is coming up (in about a week) so I need to review the material.

Week 6 - Thursday Oct 16, 2008

2008-10-19T18:10:00.000-07:00

Week 6 is already gone. Time really flies and that's not a bad thing as this week, i.e week 7, I have 4 midterms in three days, I have and three assignments.Too much work!

Anyways, the lecture was shorter this week because the morning section missed the Monday lecture, it was Thanksgiving day. No complaints there, it was nice to finish at 20:00 instead of 21:00.

We talked about two things:
1) The time complexity of merge sort (n*log(n)).
2) The master theorem.

The master theorem basically gives the time complexity for divide-and-conquer algorithms. If you can write the time complexity of an algorithm in a specific recursive way then you can use the master theorem to get a bound on the time complexity of the algorithm.

We also got Test 1 back and handed in Problem Set 3. Problem Set 3 was not hard, you just needed to follow an example we saw in class and then you could get the closed form that was needed. I learned that a finite sum is not considered closed form if it grows in n. I was wrong to think that infinite sums are not considered closed-form but finite are.

Test 1 went OK. I made a stupid mistake that I now realize I was doing often when I was using the principle of complete induction. Need to be more careful from now on. Other than that, I was happy with my test.

I think I am writing just to avoid studying for CSC260 so I better stop here.

Week 5 - Thursday Oct 09, 2008

2008-10-10T08:42:00.000-07:00

Attempt #2

Firefox crashed on me and took my post with it to the realms of the unknown. This re-post is going to be significantly shorter than the previous one because I am still mad at Firefox...

Week 5 ended and Test 1 is a thing of the past. This week we looked at structural induction, a flavor of induction that I found both more challenging and more interesting. We also looked at more recursive formulas and their closed forms. Specifically we saw how the Fibonacci sequence is related to the golden ratio. Interesting stuff I tell you! It makes me want to see Pi again...

As for test 1, I found it fair. I finished just on time but it was mainly because of the way I function which is not the optimal way a human being should function.

I solved one of the questions using combinatorics and I am sure it was because of the ternary trees problem on the Assignment. For a couple of weeks now all I do is count stuff and make sure I subtract the duplicates! I think I did well, I will see if the TAs agree with me sometime soon.

Have a great weekend and happy thanksgiving to all!

Week 4 - Thursday Oct 02, 2008

2008-10-05T10:56:00.001-07:00

This week was all about recursion and how it's related to induction. We looked at the Fibonacci sequence, a very interesting sequence that appears pretty much everywhere: in nature, in the golden ration etc.

We looked at the sum of n Fibonacci numbers and found that it's given by F(n+2) - 1. The interesting thing is that when defining the Fibonacci numbers, you need two base cases, but when we proved the formula above we only used one.

Test 1 is coming next Thursday so it's time for a quick review of everything we covered so far in the course. I should have done that over the weekend but I decided to just rest and spend some time with my family.

Week 3 - Thursday Sep 25, 2008

2008-09-27T13:33:00.000-07:00

Week 3 is gone already. We had to hand in Problem Set 2 on Thursday. It wasn't hard, the problem was very similar to one of the examples we saw in class last week.

Assignment 1 is due this coming Monday and I am done. Problem 4 on the assignment is now due sometime in October. The assignment in general was a little bit challenging but Problem 4 is giving me some trouble. I have been thinking about it pretty much every day and I still can't figure it out.

For those who are interested, we are asked to find a (recursive) formula for the number of ternary trees with n nodes. I started drawing trees on paper (I always start drawing pictures, it helps me understand the problem and gives me an idea of how to proceed, though in this case the picture did not help me with the latter...

So for n=5 I was getting 300 trees instead of 273 and I until last night, I was unable to see where I was generating the duplicates. Talk about frustration...I was ready to explode until I spotted the duplications...Anyways, I am happy I figured where I was making the mistake but now I need to come up with a way to count them without producing duplicates. I am done with drawing trees for at least a couple of weeks!

In class this week as continued with induction and the Principle of Well Ordering (PWO). We saw that if you believe one of PSI, PCI or PWO then you should accept all three because they are somewhat equivalent you can show that PWO implies the PSI that in turn implies the PCI.

During the last hour of the lecture professor Heap presented three proofs that were all wrong and we had to spot the subtle mistakes. The most interesting for me was the one with the hexagons. The professor told us that it was similar to a famous false proof that all horses are of the same color. If you are like stuff like this, google: proof + "all horses are" and you will find the proof.

Hm, a long post this week. I think it's because I am trying to avoid thinking about ternary trees...

Week 2 - Thursday Sep 18, 2008

2008-09-18T20:17:00.000-07:00

Hm, I got home from class and I am really tired. I used to be a night person but I guess not anymore...I am considering switching to the morning section.

The first problem set was due today and I found it to be on the easy side. The first homework is already out and I started working on it. It's definitely harder than the problem set but at the same time way more interesting. I really like the second and (especially) the third problem.

In the lecture today we talked about complete induction. I understand that for certain problems it makes more sense to use complete induction but I don't like it as much I like the PSI. I find simple induction more logical. I am sure most of the people will disagree with me.

I was having a hard time following the example with the trees. I consider myself green but for some reason I always have a hard time with trees. I really need to sit down and get more familiar with trees because I am sure I will see them again soon...

Week 1 - Thursday Sep 11, 2008

2008-09-13T20:11:00.000-07:00

We had the first lecture and since I attend the evening section, the class is three hours long. I like the new style of the lectures with Professor Heap using his tablet.

We went over the course information stuff and then we started with the principle of simple induction. We saw a couple of examples, like the one that we had to prove that the units digit of 3^n belongs to the set {1,3,7,9}.

In my opinion the most interesting was the one with the number of subsets of odd size of a set with n elements.

Excluding zero, you can use induction to show that we have 2^(n-1) subsets of odd size. There was another clever approach to the proof that was suggested by one of our classmates. It used the 1-1 correspondence of the subsets of odd size to the subsets of even size.

Problem Set 1 is due next week so I have to start this weekend!

Welcome!

2008-09-13T19:49:00.000-07:00

Hello everybody and welcome to my SLOG. For those who are wondering, SLOG comes from selectively picking letters from the following two words: course log.

This is my second time slogging as I did the same thing last year for CSC165. I have to admit that in the beginning I was not looking forward to having to write about the class. By the end of the year I came to appreciate it.

Well, once again, welcome to my SLOG . I am looking forward to the new school year and to all the interesting stuff we will discuss in CSC236.