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.
Subscribe to:
Comments (Atom)