Summer in CSC236

General Thoughts

2008-12-05T21:46:00.004-05:00

Given what we heard about this course from older students, my colleagues and I were really worried how things will turn out with CSC236. After thirteen weeks, I can say that CSC236 was a great course; the material was not too hard nor too easy, and the work load was a bit above average but fair. I think the solid background we have from CSC165 plus the enthusiasm and professionality of professor Danny played a key role in making things smooth for us.
I know we are not asked to do this, but I thought it would be useful if I give some feedback on the course. I am using three of the questions professor Danny used when evaluating CSC207.

What are the top three things you like about CSCS236?

The lectures: I found them very useful. Also, the black and green slides really managed to draw one's attention at 10 in the morning.
Generous office and TA hours: No matter how early my partner and I started to work on the assignments, there were always some bugs appearing at 7:30 pm before the assignment is due. Knowing that there is a TA available for help till 8 pm gave us great confidence and relief.
Doing assignments in partners: it is nice to work with other people. Besides, when you explain to your partners how you did a particular question, you get to understand it even better.

What are the top three things you hate about CSCS236?

Emphasis on the use of expressions: Assignment 1, and the later assignments, kind of shocked us because if we used expressions that were not clear enough for the grader, we would lose significant amount of marks. I know I am wrong in this point, but this is what I think.
Having a test on the last day of school.
hmmmm.. I could not think of anything else I hate about CSC236

Did your first year here prepare you well?

More than well (in terms of the materials themselves and the general atmosphere of the university).

I would like to conclude my journal by saying thank you professor Danny and I really hope if you teach us CSC263/ fall 2009.

Problem Solving Episode

2008-12-05T20:15:00.010-05:00

***
I will be doing Question 3 /Assignment 2 using Polya's method which we learned in CSC165
****

QUESTION: Let G(n) be the number of ways a grasshopper can perform the climb when there are n stairs. Prove that for n >= 1, G(n) <= F(n), the nth Fibonacci number.

Step One: Understand the Problem
The main task in this question is to find a formula for G(n) and use it to prove that G(n) <= F(n) using complete induction. Since professor Danny does not require a closed formula for G(n), I will just try to find a recursive one.

Step Two: Devise a Plan
The first plan that came up to my mind is to try and find G(n) for some small values of n, and then by comparing these values with each other on one hand, and with n on the other hand, come up with a formula. After finding the formula, establish a predicate, a claim, then start the inductive proof.

Step Three: Carry out the Plan
Let's make a table for 1 <= n <= 8 and write down all the possible configurations of hops that the grasshopper can make to reach the nth step:

*****I do not know where did this space come from*****

n	Possible Configurations	G(n)
1	1	1
2	11	1
3	111, 3	2
4	1111, 31, 13	3
5	11111, 311, 113, 131	4
6	111111, 33, 1113, 1131, 1311, 3111,	6
7	1111111, 331, 313, 331, 11131, 11131, 11311, 13111, 31111,	9
8	11111111, 3311, 3131, 3113, 1133, 1331, 111113, 111131, 111311, 113111, 131111, 311111,	13

Looking at the previous table, we can tell that G(n) will depend on the addition and subtraction of other values of G(n) becaue G(n), like F(n), does not seem to increase fast. (so we do not have exponential powers for example). Other than this observation, there does not seem to be a clear pattern that can be used. For example, for 2 <= n <= 4, G(n) = G(n-1) + G(n-2). For 5 <= n <= 7, G(n) = G(n-1) + G(n-2) -1. This does not seem to work; I need another plan. I know that the formula is there but I cannot seem able to derive it. I will work on another plan tomorrow.

Step Two (b): Devise an alternative Plan
The previous plan did not seem to work out well so I had to come up with something else. This time, in stead of finding a formula that works for small values of n and then generalizing it, I will try to come up with something directly general.

Step Three (b): Carry out the Plan
1) Suppose that the grasshopper wants to get to step m. Then, the grasshopper must be at step m -1 since it can an hop 1 step. But since it can hop 3 hops as well, then it can be at step m - 3 as well. Because this is a recursive formula, we know that there are some number of configurations that make the grasshopper get to step m-1 . There is also another set of configurations that make it get to step m-3. Since G(n) is about the order of steps used to climb the stairs, then we can get to m by the number of configurations for m-1 (with 1 added to the end of each configuration) plus the number of configurations for m -3 (with 3 added to the end of each configuration).
Then, G(m) = G(m-1) + G(m-3); and this formula actually works for the values of n in the table.
We have to make a special consideration for the values of n <= 3 since (n-1) and/or (n-3) might no be defined. Then: G(n) = {1, if n=1 or n = 2
2, if n = 3
G(n -1 ) + G(n -3) if n > 3

2) Before we start the proof, we need to prove that the Fibonacci Sequence is non-decreasing.

Predicate P(n): ∀ n,g ∈ ℕ, g < n \implies F(g) <= F(n)
Claim: ∀ n ∈ ℕ, P(n)
Use complete induction; then we need to prove the following:
∀ n ∈ ℕ, [P(0)\and P(1) ..... \and P(n-1)] \implies P(n)
Base Cases:       
      When n = 0, then there is no smaller natural number. Hence, we cannot find a g such that g <> F(n). Hence, P(0) is true.
      When n = 1, then the only smaller natural number is 0 and P(0) = 0 <  1 = P(1).    
      Hence, P(1) is true. 
Induction Step:
Assume n ∈ ℕ  
   Assume P(0)\and P(1) ..... \and P(n-1) are true # Induction Hypothesis     
   If n <= 1, then P(n) holds as shown in the base cases      
   Else if n > 1
      Then F(n - 1) = F(n-2) + F(n-3) <= F(n-1) + F(n-2) = F(n) # By IH 
      Then F(n - 1) <= F(n) \and (n-1) < n     
      Then P(n) holds  
Then [P(0)\and P(1) ..... \and P(n-1)] \implies P(n)
Then ∀ n ∈ ℕ, [P(0)\and P(1) ..... \and P(n-1)] \implies P(n)
Conclude: ∀ n ∈ ℕ, F(n) is non-decreasing

3) Now that we have a formula for G(n) and we know that the Fibonacci Sequence is non-decreasing, we can establish a predicate and claim.
Predicate P(n): if n ∈ ℕ - {0}, G(n) <= F(n) Claim: ∀ n ∈ ℕ - {0}, P(n) We will use complete induction. Then we need to prove the following: ∀ n ∈ ℕ - {0}, P(1) \and P(2) ............... \and P(n -1) \implies P(n) Base cases: When n = 0, then P(0) holds automatically.
When n = 1, then G(1) = 1 <= F(1) = 1
When n = 2, then G(2) = G(1) = 1 <= F(1) <= F(2) When n = 3, then G(3) = 2 <= G(2) = 1 <= F(1) <= F(2) Then P(n) holds in all base cases.

Induction Step:

Assume n \in N and n > 0
 Assume P(1)\and P(2) ..... \and P(n-1) are true # Induction Hypothesis
   If n <= 3, then P(n) holds as shown in the base cases.          Else if n > 3:
    Then G(n) = G(n-1) + G(n-3) <= F(n-1) + F(n-3) # By IH and definition of G(n), F(n)       Then F(n-1) + F(n-3) <= F(n-1)+ F(n-2) = F(n)  # Since the Fibonacci Sequence is non-decreasing      Then G(n) <= F(n)            Then P(n) holds

Then ∀ n ∈ ℕ - {0}, [P(1)\and P(2) ..... \and P(n-1)] \implies P(n)
Conclude:  ∀ n ∈ ℕ - {0}, G(n) <= F(n)

Step Four: Look Back
So we have found a formula for G(n),and we explained how we derived it. We proved that the Fibonacci Sequence is non-decreasing and used this property in out inductive proof. Then we can conclude that ∀ n ∈ ℕ - {0}, G(n) <= F(n).

Week Thirteen

2008-12-01T11:03:00.005-05:00

Monday,
--------- Dec. 1, 2008

Today, we discussed "Push Down Automate"; the last topic in CSC236 this fall. The idea is very simple; how to express an FSA as a CFG. Each terminal is either \epsilon, or is preceded by one symbol.

Last week, we discussed examples of non-regular languages. Since these languages cannot be expressed by normal FSAs, we can use PDA to express them. We did an example of a language that has a similar number of 0s and 1s. The idea is to use stacks to determine how many 0s have been seen so far and compare them to the number of 1s.

Wednesday,
--------- Dec. 3, 2008
I could not attend today's lecture because I had a project for architecture due at 1 pm and I was working till 11 am (usual scenario). I am really thankful because Professor Danny posted the exam review approach on the bulletin board. I hope this will compensate for the lecture.
B the way, I did not know that professor's Danny's full name is Daniel. Very interesting :)

Friday,
--------- Dec. 5, 2008
We wrote test 3 today. Of course, today was the last day in school so I had like 4 assignments due plus this test. I did not study and I was not surprised to see that most students have not studied either. Anyway, I think the test was fair; I answered everything so I hope I will get a good mark. I thought there would be a question about pumping lemma and another question about proving DFSA invariant, but none of that showed up :)

Week Twelve

2008-11-26T23:53:00.006-05:00

Monday.
--------- Nov. 24, 2008
I was really excited about today's lecture because it answered the question I had in mind since the first time I learnt about languages denoted by regular expressions. The question is, or “was” actually, "are all languages regular?" if not, how can we prove that?
The pumping lemma is a powerful tool that takes a segment of a language, usually called v, and copies it 0 or more times. If the resulting strings maintain the properties of L, then L is regular. Another thing that makes the pumping lemma really useful is that it can be used, through proof by contradiction, to show that a language is regular or not regular; depends on what we need.
Professor Danny showed how the language that has the same number of 0s and 1s, and the language with strings of prime lengths are not regular.

Assignment Three.
--------- Nov. 24, 2008
According to all my friends, this assignment is much easier than the previous two. The loop invariant and termination proof in question 1 were pretty straightforward. Question 2 was much trickier and longer but it gave us good practice in proving the equivalence of regular expressions and languages. Question 3 was really easy; we even found three ways to solve it. One way was by structural induction (just assuming that a regular expression has no Kleene star and that it is either the concatenation or union of other two regular expressions). The other two ways were through contradiction. I am glad we had more than one approach; but we went with the first way because it is the shortest. Question 4 was fair. I kind of misunderstood the meaning of "represent the DFSA textually" and I ended up drawing it in python using arrows and dashes. Of course the resulting machine was pretty nasty but after asking Danny, he explained that we need to mention the different transition functions instead. What a waste of three precious hours!

Wednesday.

--------- Nov. 26, 2008

So far, we have talked about alphabet and languages. Today we talked about grammars. I wonder what is coming next, may be Shakespearian programming?
Anyway, we define CFG as a tuple (V, \Segma, P, S). So it is just like a DFSA machine but with a set of variables and productions rather that states and transitions.
Professor Danny said that CFG is a powerful tool; I did not see why. But after using it to generate languages (and union and concatenation of languages), my doubts instantly faded away.

Friday.
--------- Nov. 28, 2008
Professor Danny ended Wednesday's lecture with a CFG that represents, as the lecture claims, binary strings with even number of 0s and 1s. We used simple induction to prove this. Just like the proof of merge sort, the proof was lengthy but not complicated. We need to consider all possible cases.
The only thing that freaked me out was the use of the Intermediate Value Theorem. In cases when zeros(x) = ones(x) + 1 and x = 1y, then zeros(y) = ones(y) + 2. There is no such antecedent in the induction hypothesis so we use IVT to show that for some y, zeros(y) = ones(y).
If I encountered such a proof in the exam, I know I would not be able to solve it. How did it ever come up to the people who solved this question to use IVT?

Week Eleven

2008-11-23T00:26:00.001-05:00

Monday.
--------- Nov. 17, 2008
We returned back to the DFSA that accepts strings that are multiples of 3 (when evaluated in base 2) which we designed last week. Because we are dealing with strings, we used structural induction. The proof was easy though lengthy because there were so many cases to consider.
We also talked about using \epsilon transitions to concatenate or add two machines and concluded the lecture with the definition of Nondeterministic Finite State Automate (NFSA).

Wednesday.
--------- Nov. 19, 2008
We finished off on Monday with the definition of NFSA. The main difference between DFSA and NFSA is that in the former, the current input symbol uniquely determines the next state of the automaton, while in the latter, a symbol (or even \epsilon) moves the machine to one of several possible states. Hence, a string x inputted to an NFSA might result in several paths. Determining if the NFSA accepts x or depends on finding at least one path that goes from the initial state to an acceptance state.
The bottom point in this lecture is that every NFSA has an equivalent DFSA! This can be done just by replacing each state in the DFSA states with sets of states (easier said than done).
We concluded the lecture by discussing Cartesian product of languages and FSAs. I modestly think that this tool will be a very useful in and beyond this course. I am happy because we will practice it in assignment 3.

Friday.
--------- Nov. 21, 2008
So far, we have shown that every regular expression has an equivalent NFSA and every NFSA has an equivalent DFSA. We will finish this circle by showing that every DFSA has an equivalent regular expression. So we start with a machine, add a new start and a new acceptance states, and add an \epsilon transition between the original and new start state, and between the original and new acceptance state. Finally, start removing states to get a machine that is one-state smaller every time. You will end up with a very long expressions going from the start to the acceptance state.
We used this method with a DFSA that accepts strings with odd lengths and even number of 0s. I think that the resulting regular expression was cool but long; (00+01(11)*10)*(1+01(11)*0)[0(11)*0(1+0(11)*10)(00+01(11)*10)(1+01(11)*0)]*

Week Ten

2008-11-19T18:09:00.002-05:00

Monday,
---------- Nov. 10, 2008
We discussed different operations on regular expressions and how to use these rules to, I do not know if I can put it this way, "simplify" regular expression. Then Professor Danny mentioned that finding the intersection of two languages (or regular expressions) can be really tricky, but to solve this issue we use FSAs.
DFSA, Deterministic Finite State Automata, is a machine designed to represent a regular expressions. When given a string input, it determines whether this string is denoted by the regular expression or not.

Wednesday,
---------- Nov. 12, 2008
We talked more about DFSAs today and how to represent them in terms of their states and transitions. There is not much to write about; DFSAs looked to me like a code with if statements instead of states. The example we did in today's lecture was a really simple DFSA but I know things will get much complicated pretty soon.

Friday,
-------- Nov. 14, 2005
We learned how to design a DFSA today by establishing a state invariant which lists all states and explains each one of them.

Week Nine

2008-11-03T18:06:00.006-05:00

Monday,
---------- Nov. 3, 2008
Today, we started chapter 7 which discusses strings and regular expressions. We began by defining alphabets, strings, and languages and the various operations that can be applied to them. Everything sounds okay except for the Kleene star. At first I thought it is something like the Cartesian product of the language itself, but it turned out to be infinite. I guess I can think of it as "infinite Cartesian products of the language itself"??

Wednesday,
---------- Nov. 5, 2008
Today's lecture was about regular expressions. This term is familiar from CSC207. We have three main operations; "or" (I do not know why is it + rather than |), "concatenation", and again, "Kleene star". Good thing to keep in mind when doing proofs related to RE, is to use the inductive definition itself. Consider three base cases, \phi, \epsilon, and (a) for some a \in \Segma. Then use structural induction in the induction step.
Finally, we discussed how to prove that two languages are equivalent. It is a two-way proof. Prove the first is a subset of the second, then prove the second is a subset of the first, and conclude that they are equivalent.

Friday,
-------- Nov. 7, 2005
We had term test 2 today. The test was fair, I honestly expected something harder. There is one thing is bugging me though. In the last question, I did not need to prove a loop invariant; I just showed that there is a decreasing non-empty sequence of natural numbers. I hope this is enough.

Week Eight

2008-10-28T01:10:00.004-04:00

Monday,
---------- Oct. 13, 2008
After talking about the correctness of recursive programs last week, we moved to iterative programs. The tricky part in codes with “for” and “while” loops is that you have to prove that the code eventually terminates; and when it does; it satisfies the postcondition.
So we might need to find a loop invariant first; something that demonstrates how the loop is progressing towards the goal. Then, we need to find a non-empty decreasing sequence of natural numbers to prove that the loop actually terminates. Finally, we use the information we gathered from the first and second part to conclude that if the preconditon holds then the postcondition is satisfied when the loop exists.

Assignment 2,
---------- Oct. 13, 2008
WOW! that was one hard assignment. I have to admit that although I started to read and think about the assignment a week ago, I did not do any real work till yesterday. The result? I was typing till 9:50 pm today.
Question 4 was okay because it is similar to the one we did in lecture (I hope so). Question 3 was fine. The sequence of G(n) was easy but I do not know why it took my partner and I a long time to figure it out. For question 2, I did exactly as we did in lecture; I found T(n), found its closed form, proved it holds for powers of 7, proved T(n) is non-decreasing, and finally squeezed non-powers of 7 between powers of 7. It was a long proof, but this is how I understood it in lecture and I could not risk trying some other method 5 hours before the assignment was due.
Question 1; oh what can I say. My partner and I used an approach which we thought was promising (we got T(n) = 3T(n-1) + other stuff). We wanted to push our formula further but we neither had the time nor the nerve, so we used a method that includes summation. I guess I should drop by Professor Danny's office and discuss that first formula with him; I am sure he will figure something out.
In conclusion, I have spent around, without the time my partner's time, around 17 hours working on this assignment, and I think this exceeds the weekly 8 hours for CSC236. I should have started earlier, and I should have given more credit to the difficulty of question 1. I really need to do well in the up-coming test because I think I will get 60 or something in this assignment.

Wednesday,
---------- Oct. 15, 2008
I could not make it to class today; but I checked the lecture and course notes. Professor Danny did another example of iterative correctness; this time with a tricky termination.

Friday,
---------- Oct. 17, 2008
We concluded out discussion about program correctness by doing an example of nested loops. The first impression I had was "Oh my God...that looks nasty." But Professor Danny broke the nest loop into an inner and an outer loop. Then he proved the inner one normally and then the outer one. Pretty simple, huh? I just love the way in Danny manages to break down the most complicated proofs into smaller, simpler, and familiar problems. But anyway I do not think I would like to see a double-loop question in the exam.

Week Seven

2008-10-20T00:35:00.002-04:00

Monday,
---------- Oct. 23 2008

Today's lecture was presented by Nick Cheng from UTSC because Danny was at UTM doing some kind of a survey regarding CSC207. We discussed the meaning of program correctness. One of the definitions we came up with was; “a program is correct if it produces the correct output given that the input was correct."
From this definition, we started talking about pre-and-post conditions. It is interesting how careful we should be when defining them. For example, if you have a function that returns the index of the first occurrence of some x in a list L, you have to say in the postcondition that L remains unchanged. Otherwise, doing something like L[0] = x and then returning 0 will be perfectly right.

Wednesday,
---------- Oct. 25 2008
We proved the correctness of binary search. The proof was long but difficult. There are several cases which we need to trace as follows: If the value at the middle(call it L[m]) is less that x and x is in L, if L[m] is less that x and x is not in L, if L[m] is greater than x and x is in L, and finally, if L[m] is greater than x and x is not in L.
Doing Question 4/Assignment 2 was a great practice because it requires a very similar kind of proof.

Friday,
---------- Oct. 27 2008
We worked on gcd(n,m) and pow(n, m) as examples of divide and conquer algorithms.

Week Six

2008-10-17T11:31:00.005-04:00

Monday,
---------- Oct. 13, 2008
A holiday :)

Wednesday,
---------- Oct. 15, 2008
We worked on the time complexity of merger sort. I knew that its complexity is (nlgn) from CSC165 but I could never figure out how to prove such a complicated thing. After we did the proof I find it to be lengthy more than complicated.

Friday,
---------- Oct. 17, 2008
The master theorem... I need to go to the course notes and read through it again because I kind of lost track by the end of the lecture (not because it is that hard but 4-hours of sleep is never enough for me).

Week Five

2008-10-10T00:13:00.002-04:00

Monday,
---------- Oct. 6, 2008
Today, we talked about the closed form of recurrence. We started with Fibonacci Sequence. Although the formula seemed so strange, Professor Danny explained that it is very necessary. Writing a recursive code for F(n) is not something wise especially if n is greater than 25. I remember professor Paul Gries doing this example in CSC148 last year. When he called F(30), a continuous flow of integers kept appearing on the screen, just like a matrix. It was cool, but it taught me that even nice useful things like Fibonacci sequence can be lethal.
Moreover, using while loops instead of the closed form is not a good option if n is larger, because F(n) is a linear function and you have to keep adding till you reach that larger n.
The second example we did was H(n) and we used a similar approach to find the closed form.
Finally, we talked about defining sets with induction. The example about proving that the number of nodes in a binary tree is less than or equal to 2^(H(T) +1) - 1 was really easy but I did not get the part that defining a property can be derived from the definition itself.

Wednesday,
---------- Oct. 8, 2008
We continued with defining sets with induction and the example of the binary tree. We did a second example about matching parentheses, it is easy but I am so confused. What I did to prove that P("(s1)") holds was just proving that 1+L(s1) >= 1 + R(s1). It is pretty simple and straightforward. According to professor Danny's solution, we need to consider s^ = s^^ * s^^^ where s^ is a prefix of s1, s^^ is a prefix of "(" and s^^^ is a prefix of s^^. Then by induction hypothesis, L(s^) >= L(s^^) +L(s^^)>= R(s^^) + R(s^^).
I do not really get it; why should we break them like that? I guess I have to take another look at the lecture slides and the course notes.
Another thing that is bugging me is that it has been more than 24 hours since A1 marks have been posted, and I still did not get my mark. I cannot use the online marking tool because my partner was the one who submitted the assignment. I cannot use cdf/students because the marks are not up on cdf students either, and my partner did not email me with the mark :(

Friday,
---------- Oct. 10, 2008
We had our first test today. I did not find a problem in studying induction because the examples in the lecture slides and course notes were thorough and easy to follow. However, it was not until 8:30 pm when I discovered that materials from chapter 3 will be on the test as well. I did not know where to stop; so I studied everything even Monday's and Wednesday's lectures and I went to the test praying that nothing outside induction will show on the test.
The test was neither easy nor hard, but I spent the whole 50 minutes writing. For question 2, we had to find a number k such that \forall n>k, 3^n <>

Week Four

2008-10-06T23:57:00.003-04:00

Monday,
---------- Sept. 29, 2008
All right, it is recursion time. Dealing with running times of recursive functions is something I was avoiding since last year. Of course, we did not start directly with time complexity or efficiency of recursive codes. Rather, we started with my favorite sequence ever, the Fibonacci Sequence. We used complete induction to prove that the sum of the first n Fibonacci numbers is f(n+2) -1.
I am happy because we did this example because it corrected a misunderstanding I had. Although we are done with the induction chapter, I still instinctively assume P(n-1) then use P(n) to prove P(n+1) in complete induction (I guess I have mis-learned this point in MAT137). So when I did the scratch work and compared it to the professor's solution, I was a bit shocked for the silly mistakes I made because P(n) is not assumed to be true; we have to prove it.

Wednesday,
---------- Oct. 1, 2008
I could not attend today's lecture because I stayed awake working from Tuesday, 10:30 am to Wednesday, 11 am on a project for my architecture course.
I think they talked about something called unwinding, I am not sure. I will have to read the course notes and the lecture slides.

Friday,
---------- Oct. 3, 2008
Unwinding turned out to be really interesting. You start with a recursively defined sequence, then keep applying the definition and recording the number of steps done so far, till you get to n = 0 or 1 or whatever base case you have. Unwinding is used for finding closed form for recursive formulas.

Week Three

2008-09-22T13:53:00.005-04:00

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

2008-09-18T22:39:00.004-04:00

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

2008-09-16T17:30:00.006-04:00

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.