Week Three

Monday,
-----------Sept,. 22, 2008
In today's lecture we compared the three methods of proof we learned so far. Namely: simple induction, strong induction, and well ordering. We talked about the difference in their definitions as sets and the general ways to use them. Then we proved that if we believe in well ordering then we must believe in simple induction, and if we believe in simple induction then we must believe in complete induction. These two proofs were easy though weird. We will be doing the proof of complete induction to well ordering on Wednesday using the contrapositive.
Nothing else happened, probably because many students were absent, I do not know why; there were no rain or snow storms today :)

Wednesday,
-----------Sept,. 24, 2008
We talked about inductive proofs with bases cases other than zero. I cannot exactly say that today's lecture was about a different flavor of induction; but more of a special case. An important thing to notice is that because base cases can be greater than zero, we need to double check when a predicate holds if the question does not specify a domain. For example, in proving 2^n > 10n, zero does work, but {1, 2,.....,5} do not work. So we need to be careful. Other than that, base cases are fairly straight forward (at least this is what I think and I hope I will not have to change my opinion after a test or assignment).

Friday,
-----------Sept,. 26, 2008
Today, we concluded our long, though interesting discussion about induction by presenting examples where wrong things were done but the overall proof seemed perfectly true. I specifically liked the first example of \segma 2^i = 2^(n+1) -2 because it reminded me with Wednesday's lecture. In this type of questions, it turns out that mistakes do not only happen in determining the base cases, but also in the structure of the statement itself; \segma 2^i = 2^(n+1) -1 rather than \ 2^(n+1) -2.

Here is a summary of what I learned so far in the previous lectures:

• Induction is a powerful tool and it is well suited for us, lazy computer scientists. That is because you only need to establish a predicate, (a) base case(s), and a logical transition from p(n) to p(n+1), and induction will do the rest for you.

• In strong induction, it is not necessary to have base cases.
• In strong induction, base cases can be inside or outside the induction step.

• The principle of well ordering is usually used to set proofs by contradiction on sets of natural numbers.
• Always check if the given statement makes sense of not. Moreover, testing a couple of base cases is very useful.
• Be careful when setting lists that contain the first n items, and the lists containing from, say second to n+1 item. Sometimes, these lists do not overlap at certain values of n.
• Induction may not work quite smoothly with full binary trees because if a FBT has n nodes, then a tree with n + 1 nodes is not full.

Week Two

Monday,
- - - -- - - Sept. 15/2008
Today, Professor Danny presented strong induction as a "new flavor" in induction. I was surprised by the fact that base cases are not essential in this kind of proofs. We did an example about the prime factorization of natural numbers greater than one. Although I did not believe my MAT137 instructor back then, I am now totally convinced that strong induction can work magic!
I am happy because I grasped today's materials; but having to work with binary trees again is making me furious. I hope I would be more comfortable by Wednesday when we do the tree example in class.


Problem Set # 1
This problem set is not due till Friday but I am already done, what a joy!
I went to see Professor Danny today because I am not comfortable with my answers having "English" more than "mathematical notations." The professor told me to rest assured because using complicated symbols is not the only way for a proof to be correct.


Wednesday,
- - - -- - - Sept. 17/2008
I had to submit a project for a course called Architectural Representation (other than ARC213). I have not been getting enough sleep since three days and my flue is getting worse. Of course after working till 7:00 am, I did not have even have the power to set my alarm o’clock. The result was missing all today's lectures and project submission, and paying a visit to the doctor.
At this point of time, I am thinking if studying CS and Architecture together was a wise decision. I remember my instructors and advisers “literary” warning me of doing these two majors at the same time. But I cannot just give up, I really like them. But on the other hand, I have a submission due every Wednesday; does this mean I will be missing Wednesday's lectures because I stayed up all night working? I will have to wait and see; and I might even drop a course or two.


Friday,
- - - -- - - Sept. 19/2008
In today's lecture, we did two examples about induction. One of them was about 4 and 5 cents stamps that are can used to generate any postage greater than 12. I remember a similar example from CSC165 (with 3 and 5 cent stamps), so I used simple induction in my proof. It turned out that using complete induction is more interesting and it can be done in several ways depending on the base case.
Professor Danny encouraged students to use the other approaches they came up with for solving this problem. He explained that we should stick to we thought of first unless the other approach is twice as good as ours. I was happy to hear that because I have always tried to use my own ways in solving problems or expressing opinions.

Week One

Monday,
- - - -- - - Sept. 8/2008

I think that the first impression I had when I entered the class was “oooh… am I in CSC165 again?” Professor Danny, the other CS students, the unique marking scheme, and of course, mathematical induction; it is like nothing has changed. However, the small classroom and Professor Danny's up-to-date stylus helped me realize I am now in a different course.

I am a bit concerned about the large number of problem sets, but having partners for assignments is a relief. My biggest source of concern right now is the conflict I have between CSC236 and ARC213 On Friday’s. Soon, I will have to decide which course has a higher attendance priority. Since CSC236 has three lectures versus one lecture for ARC213 each week, I think that I would be missing Fridays' lectures for this term.

Wednesday,
- - - -- - - Sept. 10/2008

In this lecture we talked about the principle of simple induction. Our main example was to prove that every set of n elements has exactly 2^n subsets. I think we did a similar example in CSC165. The proof was clear but I still do not get why does the number of subsets containing the element x [(n+1) th element] equal the number of subsets that do not include x. I should have asked Professor Danny to clear this point. Well, I guess I should be more initiative next time.

Friday,
- - - -- - - Sept. 12/2008

Of course, I could not make it to class today. But the good news is that I have made my sister take ARC213 with me so that she can attend the lectures and take the notes for me!

I checked the pre-and-post lecture slides and I think they pretty much filled me with today's example about simple induction.