Week 3 - Thursday Sep 25, 2008

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

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

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!

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.