Comp Sci 236 H1

Post # 11. LAST PIECES OF WORK!!!

2008-11-16T08:22:00.000-08:00

So, now we have only 2 last pieces of work to go. One problem set and one assignment. Semester is going to end very soon. Actually, the time passed so fast...

"Time is a great teacher, but unfortunately it kills all its pupils." Louis Hector

Post # 11. Test

2008-11-16T08:13:00.000-08:00

Test was really fair. The first two problems took little time to solve and write down solutions, since we have gone through some similar problems in class. The last problem, where we were asked to find loop invariant and prove termination of the loop, required more time to think over. Overall, I am satisfied with the mark I got.

Post # 10. Languages and Regular expressions.

2008-11-16T07:57:00.000-08:00

When we first started learning about formal languages, I was asking myself whether this material is directly related to Computer Science. However, after doing some research (actually research is way too strong word for the thing I did) I found out that formal languages are of high importance. One of the most practical applications is defining syntactically correct programming languages. There is also a branch of mathematics and computer science that studies different aspects of such languages, and is called Formal Language Theory.

Post # 9 Assignment #2

2008-11-16T07:42:00.000-08:00

Hello everyone! To begin with, let me aplogize for my absence. I want to share my thoughts about assignment #2. Well, I have to say that question #1 had been bugging me for some time. Since I was kind of sure that I had to use induction, the problem that did not fit in any of induction types, gave me some headache. However, later it turned out that we had to provide only logical proof for the problem. Other problems in assignment were in some ways similar to stuff we did in class, so solving them was not a big deal.

Post # 8 Test - 1

2008-10-16T18:38:00.000-07:00

I think that Test #1 was fair. It did not include anything that had not been covered in lectures. However, I felt that I did not have enough time. Some questions required writing long proofs. I do not intend to say that they were too tough. I just did not have enough time to finish up writing the proofs.

Post # 7 Problem Set # 2

2008-10-16T18:34:00.000-07:00

Well, what can I say... Problem Set # 2 was fairly easy. Since solutions are posted on the course web-cite and my solutions are kind of similar, there is no point to publish them here.

Post # 6 - Well-ordering Principe & Well-ordering Theorem

2008-10-09T18:06:00.000-07:00

You might consider this post kind of irrelevant, since it is not related to the course material directly. I accidentally happened to know that the Well-ordering Principle and Well-ordering theorem are different things, even though they are often taken to be synonymous.

The Well-ordering Principle states that that every set of natural numbers has its smallest element, while the Well-ordering Theorem states that every set can be well-ordered.

Post # 5-Problem Set # 1

2008-10-06T18:08:00.000-07:00

Well, to begin with, problem set # 1 was easy... I thought that I would need to use one of two famous techniques: wishful thinking or thoughtful wishing. However, it turned out that eaxmples we did in class were in many ways similar to problems included in the problem set. Anyway, since deadline passed long time ago I want to publish my solutions in case if you want to go through.

Q#1

No need to go into details. After going through several cases for n=1, 2, 3, 4 I found that there is a pattern. Each time when we multiply a number by 4, we multiply each digit of that number. For example, if we multiply 45 by 4 we know that the last digit of resulting number must be 0, since 5*4=20. Next step is to write out a proof based on simple induction. So, piece of cake, I would say.

Q#2

Again, I did some scratch work, so see for yourselves:

case1: n=1, {1}, there are 0 pairs

case2: n=2, {1, 2}, there is one pair, 2*(2-1)/2=1

case3: n=3, {1, 2, 3}, possible pairs {1, 2}, {2, 3}, {3, 1}, 3*(3-1)/2=3 pairs

And again, pattern! The great news, sounds like music to my ears, meaning that scratch work had not been done vainly! Any set {1, 2, ..., n-1, n} contains all pairs of different numbers from set {1, 2, ..., n-1}. The rest of the pairs of different numbers are formed just by taking each element of {1, 2, ..., n-1} and adding to it the last element of {1, 2, ..., n-1, n}. So each time when n increases by one, the number of pairs of different numbers increases by n.

n*(n-1)/2+n=n((n-1)/n+1)=n(n+1)/2, simple algebra and simple induction.

Post #3 - Strong or Complete Induction

2008-09-22T17:46:00.000-07:00

While we learned principle of Complete or Strong Induction, I was wondering about the name of the principle. How come mathematicians decided to name it Strong or Complete Induction? We have to make more assumptions rather than when we use the principle of Simple Induction. Anyway, it's just a name of the principle.

Post #2 - Getting Started

2008-09-22T17:33:00.000-07:00

We started this course with different flavors of induction. After solving some problems I realized that Induction is powerful tool to solve some really hard and complex problems. Even though the concept itself seems easy, the range of problems which could be solved using Induction is very wide.

Post #1

2008-09-22T17:03:00.000-07:00

Hello everyone! I hope that my thoughts and ideas that I am going to reflect on this blog will be somehow helpful and useful to students who is taking CSC 236 course. If you happened to read my posts and want to leave comments, you are very welcome to do that! In actual fact I would appreciate any feedback I can receive. I just want to finish my first post with one of my favorite quotes:
“Anyone who has never made a mistake has never tried anything new.”
Albert Einstein