As the last term test came and gone, I felt compelled to blog my experience with the course and lecturer. I have never been the "theory-guy", but more like the "coding-guy". That's why I have enjoyed all the programming courses up until now, CSC108, 148 & 207 and I also did full time database programming for the last 4 years for my employer. My interpretation of theory has always been this one word, "math", which I admit, is not my strongest subject. But I think my experience in the past 2 terms undertaking PHL245 and CSC236 have changed that a bit. PHL245 focused more on predicate and sentential logic and drew my interest to theories for the first time. And I will now attempt to describe my thoughts on various topics covered by CSC236 this term.
The twins: Simple induction and Complete induction. They were like twins to me at first, I couldn't distinguish between them and didn't know how to choose the correct "flavor" of induction for the questions in hand. So I used mostly Simple induction and that caused me some trouble in test 1 where complete induction where needed for to prove the Fibonacci series. I lost style marks for using Simple induction format when the actual technique used was complete induction. After trying out many examples, I finally got the hang of it, I think.
PWO(Principle of Well-ordering): My lack of understanding of this principle and misunderstanding of the concept of the round-robin tennis game confused me for a whole week before Danny got through to me during one of his office hours. I would say this principle is handy but specific only to proving least element in a set.
Recursive functions: one of my favorite to write when I'm actually coding. So I understood the concept right away(I'm pretty sure so did rest of the class), and I think Danny took it to a higher level with programs such as RecBinSearch, who could forget.
Program correctness, pre-condition, post condition: I have always thought what the program does can be proved in a couple of sentences. But the course taught me by using the concept of pre- and post- condition, we can break a program down to its definition and prove its correctness . I first had trouble on proving the program terminates. But after reading examples in the book, I realized how the conditions when the program terminates help in conjunction with the postconditions to prove the program's correctness.
Formal-languages, RE and FSAs: I have to say my favorite part of the course. Not only were diagrams introduced, which I found entertaining, this section explores the linguistics of a programmer's favorite numbers, 0s and 1s. Which reminds of a joke. "There are only 10 kinds of people in this world, those who understands binary and those who doesn't." I got to prove first hand equivalence of languages and REs. And to create new languages and REs by binary string operations. I also enjoyed coming up with various DFSAs and NFSAs for various invariants. And then using Cartesian product to construct a combination of 2 FSAs.
Context-free grammars(CFG): from what I have read so far, this section explores the world of linguistics, better study this before the final exam. =p
Overall, this course along with a great lecturer in prof. Danny Heap who I owe a great big "Thank You", has showed me that theories in computing need not to be boring math and can be interesting once you learn the tricks and mastered the skills.
Last thing. Sorry Danny, but I'm still not a blogger. I don't know why but when I sit down in front of a screen and try to blog, complete sentences carrying my train of thoughts are just beyond me some of the time and it takes me literally hours to write out something useful. Maybe I should submit an actual diary next time you are teaching a course requiring sLOGs and I'm in it, lol
ps, every time I think of the words, theories of computation, I keep remembering how prof. Jim Clarke use to tell the story in CSC207 of the "earlier years", when all programms were developed on paper, then punch the appropriate holes on data cards and running them through THE COMPUTER. Every time I think of this, I keep picturing myself doing that and it brings me a smile to my face =)
Friday
The Problem Solving Episode
Here is a very classic math problem revisited using the problem solving techniques presented. I've written out the scratch work earlier but it has been laying at the bottom of my binder for quite some time.
Here is the problem, I have a scale as following and I have 12 balls with identical appearance, so you can't tell one from the other from just looking at it. All the balls have identical physical weight except 1 ball which is slightly lighter in weight than the others. Question is how can you weigh these 12 balls to guarantee to find the slightly lighter ball in fewest attempts with the scale provided?
The data provided to given to us is simple, 12 balls, 1 is different, find it using a scale. The scale plays the most important part in the question as the scale can weigh 2 group of balls at a time and tell if the lighter ball is in one of the group or not. Since the scale is symmetric, the real question is then how to divide the 12 balls into groups and weigh them to achieve the result in the fewest attempts. It is very tempting to just get out a piece of paper and pencil and start simulating the experiments. But that technique may be rigorous and easy to miss a case.
As we follow the problem solving techniques presented, suppose we have N natural number of balls, the question is then to find the following:
(1)find the fewest number of attempts before you are guaranteed to find the different ball
(2)prove that number of attempts is the fewest possible
Using the fact that the scale is symmetric, we know that we'll be weighing the balls in groups. The number of balls in each group can either be factorials of 12 such as 6vs6 or 4vs4vs4 or 3vs3vs3vs3 or even smaller groups. Or the groups can be numbers such as 5vs5. But one thing is for sure that is we'll have to weigh groups consisting of same number of balls, otherwise, it'll be pointless since we won't know if the different in weight is caused by the lighter of ball or the less number of balls on the lighter side. And we'll have to weight in groups less or equal to N/2 which is 6. So we are left with options such as 6vs6 which then can be divided in to 2 groups of 3vs3, or we can have 4vs4vs4 which then can be divided into groups of 2vs2 and we can have 5vs5 as well, which can then be divided into 2vs2 with 1 odd ball out. After we know if the lighter ball is in the group of 2 or 3, we will weigh them either 1vs1 or 1vs1vs1, in which we are guaranteed to find the lighter ball. So now the question is how to divide.
The fact that we are required to guarantee to find the lighter ball limits us from taking chances and required to consider the worst case scenario where applicable. It is natural to want to weigh the balls in groups of 6s because we'll be able to find the lighter group in 1 try. But upon investigation, it takes 2 attempts in total to find the group of 3 balls where the lighter ball resides, either the 12 balls are divided into 6vs6 or 3vs3vs3vs3. And it will take 2 tries to find the lighter ball once the group of 3 balls that contains it is found. Where as if we able to find the group of 2 balls which is lighter than the other groups, it only takes 1 more try to find the lighter ball. Upon discovering this, we look at 1 level up in which the lighter group of 2 balls can be found . 2x2=4 comes into mind.
In fact, upon some brainstorming, one can arrive at the conclusion that we can narrow down the group of 4 containing the lighter ball with one try. If the two groups on the scale show equal weight, then the group left out contains the lighter ball. So upon finding the group of 4s that is lighter, it takes at most 2 tries to find the actual lighter ball, which is a grand total of 3 attempts. 1 less than the 2+2 attempts if the 6vs6 or 3vs3vs3vs3 approach is used.
It seems like a simple question, the correct solution may come to mind right away, or you may work out all the cases and maybe miss a case and not GUARANTEE to find the different ball. But using the above thinking approach, the solution can be derived easily from extending the facts given in the question.
That question seemed all too easy, so I'm going to level it up and change the question so that we don't know if the different ball is lighter or heavier.
The question arises that we have to find a standard ball or a group of standard balls and weigh it against groups that shows different weighs.
Assuming we haven't achieved the above solution, the question's new condition eliminates the 6vs6 attempt since we won't know which group contains the different ball and we will have to eventually break them up into 3vs3vs3vs3 so the initial 6vs6 attempt is wasted.
Since we have to find a standard ball of group of standard balls, we'll attempt 3vs3vs3vs3 and 4vs4vs4 with this fact in mind. If we weigh the first 2 groups of 3 or 4 balls in the first situation, 2 cases are possible. Either the scale is equal and either group can be used as the standard group or the scale shows a difference and the left over group(s) can be used as standard. It seems that we'll have to find the standard group first and then weight it against other groups to find the different group first then divide that group up and weigh against same number of standard balls to find the different ball. Eventhough that seems to be the most straight forward solution, there is a better way that can be achieved through some clever thinking.
Here is a solution that I came up with by weighing in groups of 4 and substituting 3 standard balls to find the different ball.
Again, my solution takes advantage of finding out the group of 3 that contains the different ball, because we only have to weigh 2 out of the 3 to find the different ball.
Number balls 1-12
For the first time, 1-4, on the left side, 5-8 on the right side.
1. If the right heavier then the different ball in the No. 1-8.
2nd step. 2-4 will be removed, 6-8 move to the left from the right side, take 9-11, and place on the right. In other words, on the left side of the 1,6,7,8, 5,9,10,11 on the right side.
1a. If the right is heavier then the different ball have not been touched, either No. 5 or it is No. 1 . If 1 is different, then it is lighter than the standard; if it is 5, then 5 is heavier than the standard weight.
Third step No. 1 on the left side, 2 on the right side.
If the right is heavier, then 1 is the bad ball and the ball lighter than the standard;
If balance, then 5 is the bad ball and the ball is heavier than the standard weight;
This result will not have left as heavy side.
1b, If balance, then bad ball is in 2-4, and lighter than the standard ball.
Third step will be 2 on the left side, No. 3 on the right side.
If the right is heavy, then 2 is a bad ball and the ball is lighter than the standard;
If balance, then 4 is bad ball and the ball is heavier than the standard;
If the left is heavy, then 3 is the bad ball and lighter than the standard ball.
1c. If the left is heavy, then the different ball is in 6-8, and the ball is heavier than the standard weight.
Third attempt, put 6 on the left side, 7 on the right side.
If right is heavy ,then 7 is the bad ball and the ball is heavier than the standard weight;
If balance, then 8 is the bad ball and the ball is heavier than the standard weight;
If left is heavy, then 6 is the bad ball and the ball is heavier than the standard weight.
2. If the scale balance, then the different ball in the No. 9-12.
Second step, 1-3 on the left side, 9-11 on the right side.
2a. If the right is heavy then different ball is in 9-11, and heavier than standard.
Third step will be No. 9 on the left side, 10 on the right side.
If right is heavy, then 10 is the bad ball and the ball is heavier than the standard weight;
If balance, then 11 is the bad ball and the ball is heavier than the standard weight;
If left is heavy, then 9 is the bad ball and the ball is heavier than the standard weight;
2b. If the scale balance, then the difference ball is the 12th.
Third step No. 1 on the left side, 12 on the right side.
If right is heavy, then 12 is the bad ball and the ball is heavier than the standard weight;
The scale cannot balance this time
If left is heavy, then 12 is the bad ball and the ball is lighter than the standard weight;
2c. If left is heavy, then different ball is in 9-11 and lighter than standard weight.
Third step will be No. 9 on the left side, 10 on the right side.
If right is heavy, then 9 is the bad ball and the ball is lighter than the standard weight;
If balance, then 11 is the bad ball and the ball is lighter than the standard weight;
If left is heavy, then 10 is the bad ball and the ball is lighter than the standard weight;
3. If the left were heavy then the different ball is in the No. 1-8.
Next two steps are symmetric to case 1.
Here is the problem, I have a scale as following and I have 12 balls with identical appearance, so you can't tell one from the other from just looking at it. All the balls have identical physical weight except 1 ball which is slightly lighter in weight than the others. Question is how can you weigh these 12 balls to guarantee to find the slightly lighter ball in fewest attempts with the scale provided?
The data provided to given to us is simple, 12 balls, 1 is different, find it using a scale. The scale plays the most important part in the question as the scale can weigh 2 group of balls at a time and tell if the lighter ball is in one of the group or not. Since the scale is symmetric, the real question is then how to divide the 12 balls into groups and weigh them to achieve the result in the fewest attempts. It is very tempting to just get out a piece of paper and pencil and start simulating the experiments. But that technique may be rigorous and easy to miss a case.
As we follow the problem solving techniques presented, suppose we have N natural number of balls, the question is then to find the following:
(1)find the fewest number of attempts before you are guaranteed to find the different ball
(2)prove that number of attempts is the fewest possible
Using the fact that the scale is symmetric, we know that we'll be weighing the balls in groups. The number of balls in each group can either be factorials of 12 such as 6vs6 or 4vs4vs4 or 3vs3vs3vs3 or even smaller groups. Or the groups can be numbers such as 5vs5. But one thing is for sure that is we'll have to weigh groups consisting of same number of balls, otherwise, it'll be pointless since we won't know if the different in weight is caused by the lighter of ball or the less number of balls on the lighter side. And we'll have to weight in groups less or equal to N/2 which is 6. So we are left with options such as 6vs6 which then can be divided in to 2 groups of 3vs3, or we can have 4vs4vs4 which then can be divided into groups of 2vs2 and we can have 5vs5 as well, which can then be divided into 2vs2 with 1 odd ball out. After we know if the lighter ball is in the group of 2 or 3, we will weigh them either 1vs1 or 1vs1vs1, in which we are guaranteed to find the lighter ball. So now the question is how to divide.
The fact that we are required to guarantee to find the lighter ball limits us from taking chances and required to consider the worst case scenario where applicable. It is natural to want to weigh the balls in groups of 6s because we'll be able to find the lighter group in 1 try. But upon investigation, it takes 2 attempts in total to find the group of 3 balls where the lighter ball resides, either the 12 balls are divided into 6vs6 or 3vs3vs3vs3. And it will take 2 tries to find the lighter ball once the group of 3 balls that contains it is found. Where as if we able to find the group of 2 balls which is lighter than the other groups, it only takes 1 more try to find the lighter ball. Upon discovering this, we look at 1 level up in which the lighter group of 2 balls can be found . 2x2=4 comes into mind.
In fact, upon some brainstorming, one can arrive at the conclusion that we can narrow down the group of 4 containing the lighter ball with one try. If the two groups on the scale show equal weight, then the group left out contains the lighter ball. So upon finding the group of 4s that is lighter, it takes at most 2 tries to find the actual lighter ball, which is a grand total of 3 attempts. 1 less than the 2+2 attempts if the 6vs6 or 3vs3vs3vs3 approach is used.
It seems like a simple question, the correct solution may come to mind right away, or you may work out all the cases and maybe miss a case and not GUARANTEE to find the different ball. But using the above thinking approach, the solution can be derived easily from extending the facts given in the question.
That question seemed all too easy, so I'm going to level it up and change the question so that we don't know if the different ball is lighter or heavier.
The question arises that we have to find a standard ball or a group of standard balls and weigh it against groups that shows different weighs.
Assuming we haven't achieved the above solution, the question's new condition eliminates the 6vs6 attempt since we won't know which group contains the different ball and we will have to eventually break them up into 3vs3vs3vs3 so the initial 6vs6 attempt is wasted.
Since we have to find a standard ball of group of standard balls, we'll attempt 3vs3vs3vs3 and 4vs4vs4 with this fact in mind. If we weigh the first 2 groups of 3 or 4 balls in the first situation, 2 cases are possible. Either the scale is equal and either group can be used as the standard group or the scale shows a difference and the left over group(s) can be used as standard. It seems that we'll have to find the standard group first and then weight it against other groups to find the different group first then divide that group up and weigh against same number of standard balls to find the different ball. Eventhough that seems to be the most straight forward solution, there is a better way that can be achieved through some clever thinking.
Here is a solution that I came up with by weighing in groups of 4 and substituting 3 standard balls to find the different ball.
Again, my solution takes advantage of finding out the group of 3 that contains the different ball, because we only have to weigh 2 out of the 3 to find the different ball.
Number balls 1-12
For the first time, 1-4, on the left side, 5-8 on the right side.
1. If the right heavier then the different ball in the No. 1-8.
2nd step. 2-4 will be removed, 6-8 move to the left from the right side, take 9-11, and place on the right. In other words, on the left side of the 1,6,7,8, 5,9,10,11 on the right side.
1a. If the right is heavier then the different ball have not been touched, either No. 5 or it is No. 1 . If 1 is different, then it is lighter than the standard; if it is 5, then 5 is heavier than the standard weight.
Third step No. 1 on the left side, 2 on the right side.
If the right is heavier, then 1 is the bad ball and the ball lighter than the standard;
If balance, then 5 is the bad ball and the ball is heavier than the standard weight;
This result will not have left as heavy side.
1b, If balance, then bad ball is in 2-4, and lighter than the standard ball.
Third step will be 2 on the left side, No. 3 on the right side.
If the right is heavy, then 2 is a bad ball and the ball is lighter than the standard;
If balance, then 4 is bad ball and the ball is heavier than the standard;
If the left is heavy, then 3 is the bad ball and lighter than the standard ball.
1c. If the left is heavy, then the different ball is in 6-8, and the ball is heavier than the standard weight.
Third attempt, put 6 on the left side, 7 on the right side.
If right is heavy ,then 7 is the bad ball and the ball is heavier than the standard weight;
If balance, then 8 is the bad ball and the ball is heavier than the standard weight;
If left is heavy, then 6 is the bad ball and the ball is heavier than the standard weight.
2. If the scale balance, then the different ball in the No. 9-12.
Second step, 1-3 on the left side, 9-11 on the right side.
2a. If the right is heavy then different ball is in 9-11, and heavier than standard.
Third step will be No. 9 on the left side, 10 on the right side.
If right is heavy, then 10 is the bad ball and the ball is heavier than the standard weight;
If balance, then 11 is the bad ball and the ball is heavier than the standard weight;
If left is heavy, then 9 is the bad ball and the ball is heavier than the standard weight;
2b. If the scale balance, then the difference ball is the 12th.
Third step No. 1 on the left side, 12 on the right side.
If right is heavy, then 12 is the bad ball and the ball is heavier than the standard weight;
The scale cannot balance this time
If left is heavy, then 12 is the bad ball and the ball is lighter than the standard weight;
2c. If left is heavy, then different ball is in 9-11 and lighter than standard weight.
Third step will be No. 9 on the left side, 10 on the right side.
If right is heavy, then 9 is the bad ball and the ball is lighter than the standard weight;
If balance, then 11 is the bad ball and the ball is lighter than the standard weight;
If left is heavy, then 10 is the bad ball and the ball is lighter than the standard weight;
3. If the left were heavy then the different ball is in the No. 1-8.
Next two steps are symmetric to case 1.
Tuesday
Reflection on Evaluation methods
Sorry for the long due updates, I wanted to update this long time ago but kept putting it off. Now I find myself not only not a blogger, but also a blog procrastinator. =p
After completing/in the process of completing a dozen or so of courses at this University, I can honestly say that I would rate the evaluation method for CSC236 #1 among the rest. It not only ties in a student into the course with constant evaluation, letting the student find out where he/she stands currently and what he/she needs to work on, the method also a very tolerant and humane way of keeping a student in the ball game even if he/she had a bad fallout with a piece of term work or two.
I have had courses where the final exam could be worth 75~100% depending on how good you do in them, also courses that have only 2 exams(midterm and final) as the only means of evaluating a student. I do not think those are suitable ways for two types of students. 1) Students who keep up with the term work, does most of the exercises but was in very bad shape writing the exams or something just doesn't click for them on those days. They end up receiving considerably lower marks than type 2) where the students doesn't not go to lectures/keep up with term work, but cram their brains out a couple days before the exams. They could possibly received much better marks than type 1) if they have good short term memories and just memorize the questions from previous exams and hoping their appearance this term. Type 2) students will probably forget everything associated with the course a couple months or even weeks after the exam because the contents never entered their long term memory where type 1) students actually remember the material but don't have the mark to show for them.
I like the evaluating methods for CSC236 because it has everything built into it. 3 term tests and a final as long term evaluation for students. Assignments as mid-range and also encouraging students to brainstorm, exchanging ideas and thus possibly learn from each other. And also short-term evaluation in shapes of problem sets where it is a direct reflection of material being taught in recent week or two. The marks are spread out and encouraging as your top pieces of term work would be worth the most among the rest. As a fundamental course for many upper level CS courses to come, I bet the students who sees and takes advantage of this evaluation system will have the materials locked in their brain for years to come and also get a satisfying mark to show for it. Hooray!
After completing/in the process of completing a dozen or so of courses at this University, I can honestly say that I would rate the evaluation method for CSC236 #1 among the rest. It not only ties in a student into the course with constant evaluation, letting the student find out where he/she stands currently and what he/she needs to work on, the method also a very tolerant and humane way of keeping a student in the ball game even if he/she had a bad fallout with a piece of term work or two.
I have had courses where the final exam could be worth 75~100% depending on how good you do in them, also courses that have only 2 exams(midterm and final) as the only means of evaluating a student. I do not think those are suitable ways for two types of students. 1) Students who keep up with the term work, does most of the exercises but was in very bad shape writing the exams or something just doesn't click for them on those days. They end up receiving considerably lower marks than type 2) where the students doesn't not go to lectures/keep up with term work, but cram their brains out a couple days before the exams. They could possibly received much better marks than type 1) if they have good short term memories and just memorize the questions from previous exams and hoping their appearance this term. Type 2) students will probably forget everything associated with the course a couple months or even weeks after the exam because the contents never entered their long term memory where type 1) students actually remember the material but don't have the mark to show for them.
I like the evaluating methods for CSC236 because it has everything built into it. 3 term tests and a final as long term evaluation for students. Assignments as mid-range and also encouraging students to brainstorm, exchanging ideas and thus possibly learn from each other. And also short-term evaluation in shapes of problem sets where it is a direct reflection of material being taught in recent week or two. The marks are spread out and encouraging as your top pieces of term work would be worth the most among the rest. As a fundamental course for many upper level CS courses to come, I bet the students who sees and takes advantage of this evaluation system will have the materials locked in their brain for years to come and also get a satisfying mark to show for it. Hooray!
Monday
That's right, I'm not a blogger
For years, I have enjoyed reading other people's blogs yet managed to post 0, that's right, 0 blogs of my own. Why?
First reason is that I'm lazy, I only managed to keep a few daily essential routines to survive and there is not one single other thing that I kept doing for more than a year, unless you count the two cats I was forced to keep upon till now.
Second reason is that I'm a private person online. I mean, I have a lot of friends in real life and managed to stay in touch with most of them over the years, but I just can't bring myself to write about my daily life and post it online and have random friends posting a comment once in a year or so. I would rather place a phone call and chat for a while.
Third, fourth and fifth reason, please refer back to #1.
So thanks to this great course and great professor, here I am posting my first ever blog. I'll try to keep this updated with intellectuals thoughts and what not. I said TRY. And who knows, maybe this will become my next hobby, or until I find that tennis ball I lost under the sofa the other day :)
Cheers.
First reason is that I'm lazy, I only managed to keep a few daily essential routines to survive and there is not one single other thing that I kept doing for more than a year, unless you count the two cats I was forced to keep upon till now.
Second reason is that I'm a private person online. I mean, I have a lot of friends in real life and managed to stay in touch with most of them over the years, but I just can't bring myself to write about my daily life and post it online and have random friends posting a comment once in a year or so. I would rather place a phone call and chat for a while.
Third, fourth and fifth reason, please refer back to #1.
So thanks to this great course and great professor, here I am posting my first ever blog. I'll try to keep this updated with intellectuals thoughts and what not. I said TRY. And who knows, maybe this will become my next hobby, or until I find that tennis ball I lost under the sofa the other day :)
Cheers.
Subscribe to:
Posts (Atom)