Well, there goes another semester...
My overall experience in 236 was a great one. I've learned so much from Danny over the past two semesters (165 + 236) that I don't know what I'm going to do without him as my prof next year. Knowing me I'll probably still go to his office hours for help in upper-year theory courses, regardless if he's my teacher or not... Haha...
All the assignments and problem-sets went well. All of the tests were fair. Now all that's left is the final exam.
It's gonna be weird not writing in this slog anymore. I don't know if it's a good or bad weird either... I mean, sometimes it's good to let go of your thoughts and frusterations by writing in this thing. Other times you have nothing to say, and you struggle for words... It just depends on the day I guess...
I'm looking forward to the break, and to understanding and learning about the next level of computer science theory... So I guess that's it!
Friday, December 5, 2008
Thursday, December 4, 2008
12th Entry
Is it just me or can converting a DFSA to an NFSA get really complicated really fast? I've been in Bahen for the past couple of hours now, somewhat struggling to turn DFSAs into NFSAs. And no, not for fun... but to prepare for tomorrow's midterm haha.
If the DFSA is somewhat complicated to begin with, then trying to convert it into a NFSA is just... crazy. I mean it's so easy to get thrown off by just removing ONE state, let alone all of them. I'm slowly getting the hang of it by trying to make my DFSA as simple compact as possible, which makes it easier to follow when removing states and what not. Otherwise it's really really easy to make a small error that will throw off the entire machine. All those inner-loop Kleene Star things... Ugh. Oh well, at least I'm making some progress.
If the DFSA is somewhat complicated to begin with, then trying to convert it into a NFSA is just... crazy. I mean it's so easy to get thrown off by just removing ONE state, let alone all of them. I'm slowly getting the hang of it by trying to make my DFSA as simple compact as possible, which makes it easier to follow when removing states and what not. Otherwise it's really really easy to make a small error that will throw off the entire machine. All those inner-loop Kleene Star things... Ugh. Oh well, at least I'm making some progress.
Monday, December 1, 2008
11th Entry
We've been learning all about context-free grammars for the past couple of weeks and it's pretty interesting stuff. At least to me anyway. I don't find this topic difficult to understand at all, and like I said before, I think it's actually quite enjoyable (well maybe not enjoyable, but you know what I mean)...
I've been experimenting with trying to make different DFSA/NFSA machines for different languages to practice for the upcoming test, and so far so good. Also last week A3 was due, which my partner and I managed to finish and hand in on time. I think it went pretty well. The only thing that I have to reflect on is loop invariants, and proving that RE's can/can-not represent a particular language. I think that's probably the hardest part of this entire topic.
Other then that, the semester is winding down and we're just about entering the exam period. It's been a heavy work-load this semester but all in all I think I pulled through and did well. The test this Friday is all about regex, languages, context-free grammars and all that other fun stuff.
I'm going to begin studying tomorrow... If I come across anything that really confuses me, or that I just find interesting, I'll be sure to post in my SLOG about it... That's it for now!
I've been experimenting with trying to make different DFSA/NFSA machines for different languages to practice for the upcoming test, and so far so good. Also last week A3 was due, which my partner and I managed to finish and hand in on time. I think it went pretty well. The only thing that I have to reflect on is loop invariants, and proving that RE's can/can-not represent a particular language. I think that's probably the hardest part of this entire topic.
Other then that, the semester is winding down and we're just about entering the exam period. It's been a heavy work-load this semester but all in all I think I pulled through and did well. The test this Friday is all about regex, languages, context-free grammars and all that other fun stuff.
I'm going to begin studying tomorrow... If I come across anything that really confuses me, or that I just find interesting, I'll be sure to post in my SLOG about it... That's it for now!
Sunday, November 30, 2008
Polya Problem Solving Question
I think the toughest question we've been given all year was from Assignment 1/Assignment 2. Yep, I'm talking about the ternary tree question. The question can be found here
http://www.cdf.toronto.edu/~heap/236/f08/A2/a2.pdf (It's the very first question on the assignment). Anyway, I looked back and realized that many of the methods I used on my way to coming up with a solution to this problem were from Polya himself. So I've decided to go back and reanswer the question using the Polya Problem Solving techniques.
1. Understanding the Problem
To understand this problem, you have to first understand certain characteristics of a ternary tree. I know that all trees in general (whether it be binary, ternary, quatrenary (sp?), etc.) all comprise of a root node. In this case, a ternary tree will have a root node plus at least 3 child nodes. The only exception to this rule is the empty tree. Also when I say that a ternary tree must have at least 3 child nodes, I mean that in kind of an "abstract-way". Don't get me wrong, a ternary tree could just have the root node with zero children, but when drawing ternary tree it`s easy to look at it as if there are exactly three spots available from the root node. Whether these be empty or not is totally dependent on the question.
My goal is to form some sort of algorithm that finds the number of non-equivalent ternary trees with n nodes, where n /in N. The defn. of a non-equivalent ternary tree could be found in the question.
2. Devise A Plan
First things first, I'm going to completley forget about the mathematical mumbo-jumbo and think of this question in a much simpler form. I know that every ternary tree has exactly ONE root node no matter what, so given n nodes I can make things simpler by breaking the question down to "the # of non-equivalent ternary trees with n-1 nodes, where n /in N."
Then I will treat the number n-1 as a "budget" of nodes I'm allowed to spend on any ternary tree, T. I also know that any T will have at least 3 child nodes connecting from the root. I will call these left (TL), middle (TM), and right (TR). Then I have n-1 nodes to spend between L, M, and R. Thinking about this question in a straight-forward, logical form should produce the right answer. So, let's give it a try:
3. Carry Out The Plan
Let T be an arbitary ternary tree with n nodes. Then when n >= 2 I know T must have three sub-trees. Let TL, TM, and TR be defined as the left, middle and right subtrees of T respectively. Then minus the root, R, I know that TL, TM, TR are comprised of n-1 nodes. Then I have a "budget" of n-1 nodes to "spend" on either TL, TM or TR.
First I will consider TL. Assume k is the number of nodes I choose to spend on TL (\exists k \in N). Then I have n-1 nodes to choose from, so k can be any number of nodes within n-1 and k must be less then or equal to n-1. Then I have k=0Zn-1 F(k). Now I must consider TM and TR. Assume n is the number of nodes I have left to spend on TM and TR (\exists m \in N). Then I have n-1-k nodes to choose from, since I originally had n-1 nodes and I've already spent k nodes on TL. Then m is dependent on k, m can be any number of nodes within n-1-k, and m <= n-1-k. Then I have m=0Zn-1-k F(m). Then I have n-1-k-m nodes left to spend on TR. I can treat TR as being fully dependent on k and m, because all the nodes left in my "budget" must ultimately be "spent" in the end. Then the total number of nodes in TR must be equal to n-1-k-m, so I have F(n-1-k-m).
Adding together all of the possible combinations formed by each k and m will give you the total number of non-equivalent ternary trees of n nodes. Then k=0Zn-1 F(k) * m=0Zn-1-k F(m) * F(n-1-k-m) is true!
4. Conclusion
Sometimes looking at the question in a purely logical and simplistic way is very helpful in figuring out the solution. In this case, I used the number of nodes available to me as a "budget" and applied it to any arbritrary ternary tree. In the end, it worked out perfectly! Obviously you would use induction to prove this sort of thing, but I was simply just showing the "method" I used to base my induction around.
http://www.cdf.toronto.edu/~heap/236/f08/A2/a2.pdf (It's the very first question on the assignment). Anyway, I looked back and realized that many of the methods I used on my way to coming up with a solution to this problem were from Polya himself. So I've decided to go back and reanswer the question using the Polya Problem Solving techniques.
1. Understanding the Problem
To understand this problem, you have to first understand certain characteristics of a ternary tree. I know that all trees in general (whether it be binary, ternary, quatrenary (sp?), etc.) all comprise of a root node. In this case, a ternary tree will have a root node plus at least 3 child nodes. The only exception to this rule is the empty tree. Also when I say that a ternary tree must have at least 3 child nodes, I mean that in kind of an "abstract-way". Don't get me wrong, a ternary tree could just have the root node with zero children, but when drawing ternary tree it`s easy to look at it as if there are exactly three spots available from the root node. Whether these be empty or not is totally dependent on the question.
My goal is to form some sort of algorithm that finds the number of non-equivalent ternary trees with n nodes, where n /in N. The defn. of a non-equivalent ternary tree could be found in the question.
2. Devise A Plan
First things first, I'm going to completley forget about the mathematical mumbo-jumbo and think of this question in a much simpler form. I know that every ternary tree has exactly ONE root node no matter what, so given n nodes I can make things simpler by breaking the question down to "the # of non-equivalent ternary trees with n-1 nodes, where n /in N."
Then I will treat the number n-1 as a "budget" of nodes I'm allowed to spend on any ternary tree, T. I also know that any T will have at least 3 child nodes connecting from the root. I will call these left (TL), middle (TM), and right (TR). Then I have n-1 nodes to spend between L, M, and R. Thinking about this question in a straight-forward, logical form should produce the right answer. So, let's give it a try:
3. Carry Out The Plan
Let T be an arbitary ternary tree with n nodes. Then when n >= 2 I know T must have three sub-trees. Let TL, TM, and TR be defined as the left, middle and right subtrees of T respectively. Then minus the root, R, I know that TL, TM, TR are comprised of n-1 nodes. Then I have a "budget" of n-1 nodes to "spend" on either TL, TM or TR.
First I will consider TL. Assume k is the number of nodes I choose to spend on TL (\exists k \in N). Then I have n-1 nodes to choose from, so k can be any number of nodes within n-1 and k must be less then or equal to n-1. Then I have k=0Zn-1 F(k). Now I must consider TM and TR. Assume n is the number of nodes I have left to spend on TM and TR (\exists m \in N). Then I have n-1-k nodes to choose from, since I originally had n-1 nodes and I've already spent k nodes on TL. Then m is dependent on k, m can be any number of nodes within n-1-k, and m <= n-1-k. Then I have m=0Zn-1-k F(m). Then I have n-1-k-m nodes left to spend on TR. I can treat TR as being fully dependent on k and m, because all the nodes left in my "budget" must ultimately be "spent" in the end. Then the total number of nodes in TR must be equal to n-1-k-m, so I have F(n-1-k-m).
Adding together all of the possible combinations formed by each k and m will give you the total number of non-equivalent ternary trees of n nodes. Then k=0Zn-1 F(k) * m=0Zn-1-k F(m) * F(n-1-k-m) is true!
4. Conclusion
Sometimes looking at the question in a purely logical and simplistic way is very helpful in figuring out the solution. In this case, I used the number of nodes available to me as a "budget" and applied it to any arbritrary ternary tree. In the end, it worked out perfectly! Obviously you would use induction to prove this sort of thing, but I was simply just showing the "method" I used to base my induction around.
Thursday, November 20, 2008
10th Entry
2 more weeks left of school and we're outta here... I honestly can't wait! As good as this semester has been, I'm exhausted and in definite need of a break. It's been problem-set after assignment after midterm after lab after who knows what --- so yeah ... not doing ANYTHING for a little while sounds kind of nice.
I'm really interested in what we've been learning for the past couple of weeks in lecture. I find the regular expression stuff fun to do, especially constructing the DFSA's/NFSA's. It was complicating at first, but now that I've gotten the hang of it everything seems to come naturally. I was able to complete #4 on A3 with ease, and I'm quite proud of myself because of it considering I usually need help (even if it's just a little) for practically every question on a 236 assignment.
Other then that, the 6th and final Problem Set is due tomorrow and I was JUST able to finish it. It wasn't too-too bad, just a little a long.
Everything else is good. I'm planning on doing a Polya question over the weekend, so I'm gonna look a problem that catches my eye and attempt it over the weekend. Until then, cya!
I'm really interested in what we've been learning for the past couple of weeks in lecture. I find the regular expression stuff fun to do, especially constructing the DFSA's/NFSA's. It was complicating at first, but now that I've gotten the hang of it everything seems to come naturally. I was able to complete #4 on A3 with ease, and I'm quite proud of myself because of it considering I usually need help (even if it's just a little) for practically every question on a 236 assignment.
Other then that, the 6th and final Problem Set is due tomorrow and I was JUST able to finish it. It wasn't too-too bad, just a little a long.
Everything else is good. I'm planning on doing a Polya question over the weekend, so I'm gonna look a problem that catches my eye and attempt it over the weekend. Until then, cya!
Wednesday, November 12, 2008
9th Entry
This week we've begun looking more in-depth into Languages and Reglar Expressions. Now I've got to be honest, up until this morning's lecture I was pretty lost -- I didn't even really know what a "regular expression" was...
However after Danny's example in class today, I think I've grasped a somewhat understanding on the subject. Of course like everything else, it's going to take some practise and getting used to before I feel totally comfortable with the whole "regex" thing, but at least I kind of know what I'm doing now!
Assignment 3 was released yesterday so I'm gonna get cracking on that asap. I can't beleive we're already down to the last assignment/test/problem-set! This semester seriously just flew by.
However after Danny's example in class today, I think I've grasped a somewhat understanding on the subject. Of course like everything else, it's going to take some practise and getting used to before I feel totally comfortable with the whole "regex" thing, but at least I kind of know what I'm doing now!
Assignment 3 was released yesterday so I'm gonna get cracking on that asap. I can't beleive we're already down to the last assignment/test/problem-set! This semester seriously just flew by.
Thursday, November 6, 2008
8th Entry
I had some time so I thought I'd post a quick entry before I continue studying for the midterm tomorrow..
The only thing that has me worried right no is the time-complexity/closed-form/monotonic stuff -- it's so confusing!! Well, not all of it, but for the most part I'm just sitting here going "Wow...that's a lot of numbers..." Haha. I went to Danny's office hours today and he helped me understand a lot of it, but after reading through my notes and examples from class I'm still kind of lost. I mean I know where the numbers are coming from, but when it comes to sitting down and writing the test on my own -- that's where I run into trouble.
Anyway I hope it goes well tomorrow! This week (like the past couple of weeks before it) has been super busy. I'm trying to balance studying for this midterm, a CSC207 assignment and a MAT137 midterm next week ... oh well, after that, things should get a bit less crazy.
That's it for now.. so until next week, cya.
The only thing that has me worried right no is the time-complexity/closed-form/monotonic stuff -- it's so confusing!! Well, not all of it, but for the most part I'm just sitting here going "Wow...that's a lot of numbers..." Haha. I went to Danny's office hours today and he helped me understand a lot of it, but after reading through my notes and examples from class I'm still kind of lost. I mean I know where the numbers are coming from, but when it comes to sitting down and writing the test on my own -- that's where I run into trouble.
Anyway I hope it goes well tomorrow! This week (like the past couple of weeks before it) has been super busy. I'm trying to balance studying for this midterm, a CSC207 assignment and a MAT137 midterm next week ... oh well, after that, things should get a bit less crazy.
That's it for now.. so until next week, cya.
Subscribe to:
Posts (Atom)