We had our final lecture today which included the 3rd and the final term test. I dont remember much about it now though question 2 seemed a little tricky, though it was probably me procrastinating and not looking over the assignment solutions in due time. The positive to take out of this is that it was the last test of the course so its rosy days ahead... until the final comes anyway.
Looking back in this course, it has been a thoroughly entertaining one. We started off learning simple induction, proceeded to learn couple of more flavors in induction, namely complete induction and structural induction. Complete induction was particularly interesting as it was horribly difficult to understand when we first saw it in mat137 last year. Now after three months of csc236 its almost second nature to me.
We followed that by learning how to prove that a program works again by using induction techniques in our proof. This particularly caught my fancy as i would not have thought that there is a mathematical model to proving algorithms. Overall perhaps the most enjoyable part of the course.
This was followed by 3 weeks of regular expressions and languages. Unfortunately i struggle to understand what exactly could be the point of this area of computer science in fields like bioinformatics, AI etc. I do see a strong connection of it with a programmer since i have myself used a little bit of in csc207. I hope the future courses make it more clear about its real deal. It was however a good learning experience and DFSA's were in particular useful to know about.
Danny did a great job of this course overall. He was also my course instructor in csc165 and its been a great learning curve for me with him over the last one year. I was in his office today morning and expressed my wishes that he teaches csc343 again next fall. I really hope he does!
CSC236 ruleeeeeeeez!!
Friday, December 5, 2008
Wednesday, December 3, 2008
Problem Solving Episode
In this section of the slog, i have decided to write out my solution for question 4 in assignment 1. This was perhaps one question in all the questions we did in all lectures/assignments which caused me the most confusion and took the most time so i think it is worthy of being given a detailed planned solution for.
1) How i Understood the problem:
I had to read the question multiple times to understand the gist of it. I am a visual learner so its very difficult for me to grasp a concept until i can visualize it and make neat diagrams of. I was to soon realize in next couple of weeks that this was perhaps the best example of a question where drawing diagrams is your enemy!
The problem seemed to be revolved around ternary trees, an unheard of term for me. We are told that an empty tree /\ is an element of this ternary tree. This immediately rings bells for a base case in the making. Next it described a typical element in a ternary tree where (T_L, T_r,T_m, R) would combine together in a unique way to set up a tree. R is also given to be a node which is not common to either of T_L, T_r, T_m so i was thinking of it as a root node.
We are also given the definition of equivalent ternary trees, and told that there is one ternary trees with zero nodes and one ternary trees for one node. This seems to be leading to 2 base cases.
We are to find a recursive formula for the number of non-equivalent ternary trees for n nodes and prove that our formula is correct. It was here where i had a hunch that this would be a classic example of a complete induction proof since :
a) Complete induction wasn't tested for in any of above 3 questions in A1
b) It looks like our formula will account for the number of nodes of each subtrees which will naturally be smaller than the number of trees in the entire ternary tree. So complete induction is a perfect tool for a proof of such a case where a problem is non-uniformly dividing into many sub-problems.
2) How i devised a plan.
As i mentioned above, the most natural thing for me to do was to immediately start drawing diagrams. And so i began. Within half an an hour i was able to draw 3 non-equivalent trees for two-node, 12 non-equivalent trees for three-node. A 4-node tree was much more complicated but i eventually drew out a model which counted up to 55 trees. I was hoping i hadn't ran into the famous off-by-one computer science error. And it added to my anxiety when i caught a discussion on the bulletin boards where a group of students were switching back and forth between 55 and 54 trees. Danny soon cleared the air and let it be known that there indeed are 55 trees. I was glad i got it right in the first shot!
And then i got worked on making pictures for 5-node trees. I wished one of the imaginary angels i had learnt about in high school poems had descended down on the earth and whispered a piece of wisdom in my ears warning me against heading this direction. It sure would have helped me save ton of time. I wont walk through my process of devising pictures and bore the already bored reader of this episode but i did wind up somehow making around 350 different trees which shamefully contradicted Danny assertion that there exists only 273 trees for 5-node ternary trees.
After 3 days of annoyance and head-beating against my table i decided to change my course of action, devise a new strategy, think out of the box. I reduced the problem from a ternary tree question to a binary tree question and again started on ill-advised long and arduous task of drawing pictures. But drawing pictures for binary trees turned out to be much more sweeter than for the ternary trees and immediately i was staring to see a pattern. However it was combinatorial and not recursive so i did not help my cause.
I went to see Danny in his office hours and whined about his evil genius mind and how he can devise such problems. He was kind enough to realize the gravity of the difficulty of the question and announced a new due date. It was much appreciated but i was sure not going to leave this problem until later. So i went back to work later that night.
This time, i had convinced myself to not spend 3 hours in drawing pictures only. Danny mentioned that the number of nodes in left, middle and right subtrees will add up to be n-1 (quite obvious since we don't account for the root node). After playing around with this number for a while, i finally had my "ah-ha" moment. Suddenly i was kicking myself at not getting this at the first attempt. I had a plan.
3) Carrying out the plan
I noticed that since the sum of the three subtrees will add up to be n-1, the left subtree can at most have n-1 nodes ( since by the definition of the question, if the right and middle trees are empty then left tree is not then we have non-equivalent subtree). This property was critical at realizing the solution to the problem. If the middle and right subtrees were empty, the left most could have at most n-1 nodes so i formed the first part of my equation
T(n) = n-1
Immediately after this i snapped that even if the middle and right subtrees are not empty, the left tree can still not have more than n - 1 nodes. I was starting to smell a summation equation here
T(n) = \Sigma(from i=Zero to i=n-1)T(i)..........
Then it was easy to notice that if the left subtrees have any nodes, then the middle subtree can have at most (n-1-(total number of nodes in left subtree) ) so i could further develop my equation above and get :
T(n) = \Sigma(from i=Zero to i=n-1)\Sigma(from j=Zero to j=n-l-i)T(i)T(j)
And then the right most subtree will end up with n-1-i-j nodes from basic math so the total equation was finalised to be
T(n) = \Sigma(from i=Zero to i=n-1)\Sigma(from j=Zero to j=n-l-i)T(i)T(j)T(n-1-i-j)
It was important for all terms to be multiplied by each other since for each i, there would be different pair of nodes for j and hence the nodes for right subtree ( I must mention that i would not have realized this easily if i had not taken STA257 this semester)
4) Now i of course had to prove this equation as well.
First my preposition,
P(n): n For n=0,1 T(n)=1
For all n>1, T(n)=Sigma(i;0;n-1)Sigma(j;0;n-1-i)T(i)T(j)T(n-1-i-j)
As i had a hunch, the question did turn out to be a complete induction proof. (Duh!!)
Proof by using complete induction:
Assume j is a natural number such that 0<=j
Case 1: If n=0, 1.
If ternary tree T has zero node, then there is only one ternary tree with zero nodes. The number of non-equivalent ternary will be one. Alternatively, if n has one node then there will be one ternary tree. The number of non-equivalent ternary will be one as well. As our preposition states, so P(0),P(1) holds.
Case 1 can easily go down as our base case as well but since Danny likes to break down his complete induction proofs on cases, i am following the in-class method to proof this question
Now our induction Step:
Case 2: If n>1, then there is at least one node in this ternary tree T.
Then T must have a root node and subtrees or subtrees. We call them L,M,R, namely, left subtrees, middle subtrees, right subtrees, respectively.
* Then the ternary tree with n nodes will have n-1 nodes in its subtrees.
* Then number of nodes in L (denoted as i), will be in range of [0,n-1], so by induction hypothesis, P(L) holds.
* Similarly, the number of nodes in M (denoted as j) will be in range of [0,n-1-i], since L occupies up to i nodes. So by induction hypothesis, P(M) holds.
* So the remaining number of nodes (denoted as k) in this ternary tree must be in R with it holding up to n-1-i-j nodes.(range[0,n-1-i-j] where L and M will occupy i+j nodes.) So by induction hypothesis, P(R) holds.
If we have i nodes in the Left subtree, j nodes in the middle subtree, and k in the right, then one of the possible tree, say, denoted by T[i,j,k]. Since we know by induction hypotheses, P(i), P(j), P(k) holds. Thus, for the tree T[i,j,k], the number of non-equivalent subtrees will be T(i)*T(j)*T(k). Moreover, i,j and k all having the possible values in their ranges as mentioned above. The non-equivalent tree will n nodes will be the sum of all the possible T[i,j,k] trees.
Since T(i),T(j),T(k) holds as proven above, the sum of product of these subtrees give us total number of non-equivalent trees for nodes n. The formula is presented as Sigma(i;0;n-1)Sigma(j;0;n-1-i)T(i)T(j)T(n-1-i-j) holds for n nodes ternary tree.
By the prove above, we conclude that for n /in N, P(n) holds
The above case 2 basically follows from our discussion above.
Looking back
Woah. In my two years in university, i guess this is the first question which has really exercised the hell out of my brain. It was however very enjoyable to think about a tree question in such an analytical way. It perhaps taught me a lesson on how to systematically connect every step to one another and devise a neat proof by putting it all together. A Perfect assignment question!
1) How i Understood the problem:
I had to read the question multiple times to understand the gist of it. I am a visual learner so its very difficult for me to grasp a concept until i can visualize it and make neat diagrams of. I was to soon realize in next couple of weeks that this was perhaps the best example of a question where drawing diagrams is your enemy!
The problem seemed to be revolved around ternary trees, an unheard of term for me. We are told that an empty tree /\ is an element of this ternary tree. This immediately rings bells for a base case in the making. Next it described a typical element in a ternary tree where (T_L, T_r,T_m, R) would combine together in a unique way to set up a tree. R is also given to be a node which is not common to either of T_L, T_r, T_m so i was thinking of it as a root node.
We are also given the definition of equivalent ternary trees, and told that there is one ternary trees with zero nodes and one ternary trees for one node. This seems to be leading to 2 base cases.
We are to find a recursive formula for the number of non-equivalent ternary trees for n nodes and prove that our formula is correct. It was here where i had a hunch that this would be a classic example of a complete induction proof since :
a) Complete induction wasn't tested for in any of above 3 questions in A1
b) It looks like our formula will account for the number of nodes of each subtrees which will naturally be smaller than the number of trees in the entire ternary tree. So complete induction is a perfect tool for a proof of such a case where a problem is non-uniformly dividing into many sub-problems.
2) How i devised a plan.
As i mentioned above, the most natural thing for me to do was to immediately start drawing diagrams. And so i began. Within half an an hour i was able to draw 3 non-equivalent trees for two-node, 12 non-equivalent trees for three-node. A 4-node tree was much more complicated but i eventually drew out a model which counted up to 55 trees. I was hoping i hadn't ran into the famous off-by-one computer science error. And it added to my anxiety when i caught a discussion on the bulletin boards where a group of students were switching back and forth between 55 and 54 trees. Danny soon cleared the air and let it be known that there indeed are 55 trees. I was glad i got it right in the first shot!
And then i got worked on making pictures for 5-node trees. I wished one of the imaginary angels i had learnt about in high school poems had descended down on the earth and whispered a piece of wisdom in my ears warning me against heading this direction. It sure would have helped me save ton of time. I wont walk through my process of devising pictures and bore the already bored reader of this episode but i did wind up somehow making around 350 different trees which shamefully contradicted Danny assertion that there exists only 273 trees for 5-node ternary trees.
After 3 days of annoyance and head-beating against my table i decided to change my course of action, devise a new strategy, think out of the box. I reduced the problem from a ternary tree question to a binary tree question and again started on ill-advised long and arduous task of drawing pictures. But drawing pictures for binary trees turned out to be much more sweeter than for the ternary trees and immediately i was staring to see a pattern. However it was combinatorial and not recursive so i did not help my cause.
I went to see Danny in his office hours and whined about his evil genius mind and how he can devise such problems. He was kind enough to realize the gravity of the difficulty of the question and announced a new due date. It was much appreciated but i was sure not going to leave this problem until later. So i went back to work later that night.
This time, i had convinced myself to not spend 3 hours in drawing pictures only. Danny mentioned that the number of nodes in left, middle and right subtrees will add up to be n-1 (quite obvious since we don't account for the root node). After playing around with this number for a while, i finally had my "ah-ha" moment. Suddenly i was kicking myself at not getting this at the first attempt. I had a plan.
3) Carrying out the plan
I noticed that since the sum of the three subtrees will add up to be n-1, the left subtree can at most have n-1 nodes ( since by the definition of the question, if the right and middle trees are empty then left tree is not then we have non-equivalent subtree). This property was critical at realizing the solution to the problem. If the middle and right subtrees were empty, the left most could have at most n-1 nodes so i formed the first part of my equation
T(n) = n-1
Immediately after this i snapped that even if the middle and right subtrees are not empty, the left tree can still not have more than n - 1 nodes. I was starting to smell a summation equation here
T(n) = \Sigma(from i=Zero to i=n-1)T(i)..........
Then it was easy to notice that if the left subtrees have any nodes, then the middle subtree can have at most (n-1-(total number of nodes in left subtree) ) so i could further develop my equation above and get :
T(n) = \Sigma(from i=Zero to i=n-1)\Sigma(from j=Zero to j=n-l-i)T(i)T(j)
And then the right most subtree will end up with n-1-i-j nodes from basic math so the total equation was finalised to be
T(n) = \Sigma(from i=Zero to i=n-1)\Sigma(from j=Zero to j=n-l-i)T(i)T(j)T(n-1-i-j)
It was important for all terms to be multiplied by each other since for each i, there would be different pair of nodes for j and hence the nodes for right subtree ( I must mention that i would not have realized this easily if i had not taken STA257 this semester)
4) Now i of course had to prove this equation as well.
First my preposition,
P(n): n For n=0,1 T(n)=1
For all n>1, T(n)=Sigma(i;0;n-1)Sigma(j;0;n-1-i)T(i)T(j)T(n-1-i-j)
As i had a hunch, the question did turn out to be a complete induction proof. (Duh!!)
Proof by using complete induction:
Assume j is a natural number such that 0<=j
Case 1: If n=0, 1.
If ternary tree T has zero node, then there is only one ternary tree with zero nodes. The number of non-equivalent ternary will be one. Alternatively, if n has one node then there will be one ternary tree. The number of non-equivalent ternary will be one as well. As our preposition states, so P(0),P(1) holds.
Case 1 can easily go down as our base case as well but since Danny likes to break down his complete induction proofs on cases, i am following the in-class method to proof this question
Now our induction Step:
Case 2: If n>1, then there is at least one node in this ternary tree T.
Then T must have a root node and subtrees or subtrees. We call them L,M,R, namely, left subtrees, middle subtrees, right subtrees, respectively.
* Then the ternary tree with n nodes will have n-1 nodes in its subtrees.
* Then number of nodes in L (denoted as i), will be in range of [0,n-1], so by induction hypothesis, P(L) holds.
* Similarly, the number of nodes in M (denoted as j) will be in range of [0,n-1-i], since L occupies up to i nodes. So by induction hypothesis, P(M) holds.
* So the remaining number of nodes (denoted as k) in this ternary tree must be in R with it holding up to n-1-i-j nodes.(range[0,n-1-i-j] where L and M will occupy i+j nodes.) So by induction hypothesis, P(R) holds.
If we have i nodes in the Left subtree, j nodes in the middle subtree, and k in the right, then one of the possible tree, say, denoted by T[i,j,k]. Since we know by induction hypotheses, P(i), P(j), P(k) holds. Thus, for the tree T[i,j,k], the number of non-equivalent subtrees will be T(i)*T(j)*T(k). Moreover, i,j and k all having the possible values in their ranges as mentioned above. The non-equivalent tree will n nodes will be the sum of all the possible T[i,j,k] trees.
Since T(i),T(j),T(k) holds as proven above, the sum of product of these subtrees give us total number of non-equivalent trees for nodes n. The formula is presented as Sigma(i;0;n-1)Sigma(j;0;n-1-i)T(i)T(j)T(n-1-i-j) holds for n nodes ternary tree.
By the prove above, we conclude that for n /in N, P(n) holds
The above case 2 basically follows from our discussion above.
Looking back
Woah. In my two years in university, i guess this is the first question which has really exercised the hell out of my brain. It was however very enjoyable to think about a tree question in such an analytical way. It perhaps taught me a lesson on how to systematically connect every step to one another and devise a neat proof by putting it all together. A Perfect assignment question!
Tuesday, December 2, 2008
road to the exams
I emailed Danny yesterday and inquired on the list of his final exams for csc236. I would first like to complete all of his exams before i get my hands on any of the other exams. One thing i learnt from csc165 was how solving tons of past exams from other instructors was almost useless as compared to solving one past exam made by the current instructor of the course! I also feel doing related questions from regular expressions might be great practice for the coming up test.
Also since part marks for the blog will be given on writing a concrete detailed proof for any one of the questions from lectures/assignments, i should soon be returning to the old lectures and assignments again to pick one question which troubled me the most. I do a lot of these kind of proofs in my head which traditionally has been called a bad mathematical practice. I also reluctantly agree to such a thought as there is nothing like actually putting the web of ideas in your head out on the paper and link the "nodes" of the web together coherently.
Also since part marks for the blog will be given on writing a concrete detailed proof for any one of the questions from lectures/assignments, i should soon be returning to the old lectures and assignments again to pick one question which troubled me the most. I do a lot of these kind of proofs in my head which traditionally has been called a bad mathematical practice. I also reluctantly agree to such a thought as there is nothing like actually putting the web of ideas in your head out on the paper and link the "nodes" of the web together coherently.
Wednesday, November 26, 2008
test 2
The mark for test 2 were given in the class and i was pretty disappointed with my results. I guess i am ultimately to be blamed for unrealistically expecting too much (and normally i would be quite satisfied with a similar mark in a math test ) but i really thought i did well enough to get something in the range of 21-24. I realize i should have spent some more time practicing and less time procrastinating, and a glance at some complete induction proofs for recursive functions would definetly have given me an edge, i still feel bitter about it. I have to go all-out on a full drive to do well in test 3 in a couple of weeks.
assignment completed
I just had a nice session with my partner and we wound up neatly typing up our very informal solutions to whats now a very presentable proofs to our TA's. I believe we have done a decent job in all the questions. I however feel skeptical about how assured a potential skeptic might feel about our proofs to question 2. In particular proving that language L with even number of 1s is also a subset of the regular expressions was personally very hard to prove. I guess i in general struggle to prove theorems or lemmas which seem intuitively obvious at the first glance and cant automatically generate proofs for then at the top of my head. Having had Danny as a course instructor for 2 courses now, i realise how anal he is about simple intermediate steps ( for example, we always have to mention that addition is closed!! ) so i wont be surprised if we loose a couple of marks on question 2.
road to assignment 3
The last few days have been spent working on assignment 3. I did first 2 questions with relative ease. The course slides on lecture were of great aid in assisting me solve question 1. The loop invariants, preconditions and they both lead to post condition and its termination were better explained in 2 slides than in 5 pages of course notes!
I am currently unsure about question 3. My intuition is to proceed solving it using operations of union and concatenation and prove that a finite number of strings can be generated if a language is derived using those operations. I should talk to Danny in office hours regarding it.
Question 4 is a give away. :p
I am currently unsure about question 3. My intuition is to proceed solving it using operations of union and concatenation and prove that a finite number of strings can be generated if a language is derived using those operations. I should talk to Danny in office hours regarding it.
Question 4 is a give away. :p
Subscribe to:
Comments (Atom)