Tushar's CSC236 SLOG

The Last Entry...

2008-12-05T12:57:00.000-08:00

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!

12th Entry

2008-12-04T11:18:00.001-08:00

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.

11th Entry

2008-12-01T08:06:00.000-08:00

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!

Polya Problem Solving Question

2008-11-30T15:30:00.001-08:00

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.

10th Entry

2008-11-20T13:23:00.000-08:00

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!

9th Entry

2008-11-12T18:19:00.000-08:00

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.

8th Entry

2008-11-06T17:39:00.000-08:00

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.

7th Entry

2008-10-31T06:58:00.000-07:00

This has probably been the busiest week of my entire life...

Let's see, Monday I had a 236 Assignment, 236 Problem Set, 207 Excersise ... Wednesday I had a 207 Midterm, Thursday a MAT137 Problem Set, and today Phase II for 207. Jeeeeeeeeeeeze, oh well, at least I managed to survive through it...(so far anyway)...

Assignment 2 went pretty well I guess. The ternary tree question was by far the toughest and took the longest to finish. I think my recursive formula works though, which is a good sign. I think after doing that question I can now solve similar type questions for all types of trees (binary, ternary, quanary(sp?)... because they're all sort of the same type of question.

I'm just really tired. I can't wait to just be finished with today and catch up with all the sleep I missed out on during the week. I'm going to write up a longer entry over the weekend just to summarize everything we've been learning in lecture throughout the week. Basically we're focusing more on analyzing code, proving it works, and other sorta stuff like that... But yeah, I'll write more later, cya!

6th Entry

2008-10-19T07:58:00.000-07:00

So I managed to finally figure out the solution for Problem Set 3! It took some work, but with the help of my friends and some time to think it over, I realized I was a lot closer then I thought!

I unwound G(n) to the point where I found the geometric sequence -- I just wasn't sure if this was a "closed form" of G(n). A friend of mine spoke to Danny and realized that we had it down, it was just a matter of manipulating the closed form to get the equation: (1 - r^n+1 / 1 - r) -- which I then used simple induction on to prove for the n and the n+1th term. So yeah, at least I think I did it right!

Next week is going to be really busy. We have started our first "sprint" in CSC207, so balancing that out with a Problem Set and Assignment in 236 is going to be tough. Once everything gets rolling it should be ok, it's just a matter of getting things to "roll" in the first place...

I'm happy with my mark on the first midterm. I expected to do a little better, but I totally messed up the Fibbonacci question. I used complete-induction like we were supposed to, but I don't think I "used" it efficently enough to prove the question. Oh... and I only used 1 base case instead of 2. I should've known Danny was going to put a question in with 2 base cases!

So yep, week 7 starts tomorrow and I'm ready for it. I want this recursive stuff to be over with soon... I'm curious to see what we're going to learn about next!

... And now I'm all up to date on my Slog posts too. Yesssssss.

5th Entry

2008-10-16T08:55:00.001-07:00

Yikes, two late entries in a row..

So, the midterm? Honestly.. it went pretty well. I find all of Danny's midterms and finals to be extremely fair. I hate walking into a midterm after studying very hard weeks prior, and then not knowing how to answer even one question. With CSC165 and CSC236 so far.. that's never been the case. I might not always do extremely well on them, but I always walk out confident and happy with the way it went.

I'm working on Problem Set 3 as we speak and I'm trying to figure out some sort of conjecture after unwinding of G(n) to its limit. I think I'm really close.. we'll see, I saw a topic on the bulletin board that Danny posted about a hint, so I'm going to check that out as soon as I'm done with this entry to see if it helps me out in any way. I did extremely well on the first assignment, and thats really kept me motivated to keep on top of my work and try to understand everything that's going on in lectures and on the assignments. I just noticed that A2 was posted, and I'm going to get to work on that this weekend..

Anyway I better go finish this Problem Set.. Other then that, everything is going awesome.. I feel like some of this recursive stuff is a little over my head, but like I said.. I'm sure after working on A2 things will start to make a bit more sense!

4th Entry

2008-10-07T08:31:00.001-07:00

It's been a very very busy last couple of days. That explains why I haven't been able to update this thing 'til now.. Let's just say my workload has picked up. And I'm not just talking about 236, I'm talking about all of my classes. I hate it how for a week or two you could have absoultely nothing to do, and then all of a sudden you're bombarded with a million things at once! Oh well, I guess that's school..

We have our first midterm for 236 this Friday ... Matter of fact, it's my first midterm of the new school year. I'm kind of nervous.. though I can't say I've spent too much time studying yet, and I'm sure once I dive into my notes and the text-book I'll feel more confident. Now that induction is almost behind us, I'm having more trouble understanding the material in lectures now-a-days.. It's all *kind-of* new stuff to me, so it'll definitly take some getting used to. My goal for today is to make sure I know how to do that "unwinding" technique that Danny used in lecture last week, and of course get more comfortable with the different types of induction.

I hate midterms! - I wish everything was based on problem-sets and assignments. Then again, I guess midterms and exams really show if you understand the material or not. I used to be terrible at taking tests, but I can say in the past two years I've been at UofT I've improved a lot.. I'm just hoping that this one on Friday goes well...

I'm really looking forward to getting A1 back... Other then that, I can't wait for the long weekend! I think I need a little break, juggling math problem-sets, comp sci projects and 236 problem-sets along with my other course-work has started to take it's toll on me.. Haha, oh well, only another 7 months of school left! I plan on updating this on Friday after the midterm just to give my thoughts about it..

So until then, cya!

3rd Entry

2008-09-28T18:13:00.000-07:00

Whew.

I've finally finished my first 236 assignment! As of around 2'0clock this afternoon I've been stress free, as I was able to submit the assignment quite earlier then I would've expected. Usually at this time I'd be either struggling to finish one of the tougher questions, or proof-reading some of my answers - but nope! I'm done.

The question that gave me the most difficulty was #3. Now I don't want to say too much about the answer, since the deadline hasn't officially passed yet, but if it wasn't for those TA hours I'd probably still have no clue what to do. The whole thing just really confused me. Even after I re-read it a couple of times, it just never really clicked as to what I was supposed to do. After brainstorming with some friends and countless visits to the aid center, I was able to piece everything I leared together and come to some final solution.

The thing that confused me the most was implementing the POW into it all -- I really really don't like using the POW technique, mainly because I still don't really see what's so significant about it. I'm sure Danny has a lot to say about that, and don't get me wrong I'm not saying POW is useless -- its just I find that Simple/Complete induction is a lot more straight forward. Maybe I just don't like it because I can't really figure out when to use it .. or how to use it .. or why I'm using it .. I just don't like it!

This week is going to be really brutal in terms of work. I have a lot to do and I'm expecting another Problem Set will be due this Friday, so yeah, it just keeps piling on. I'm glad I got A1 out of the way and I feel confident with all of my answers, so we'll see how it goes. I usually never do as well as I expect on assignments (or at least that was the case in 165) so I'm crossing my fingers! Oh well, like I said, we'll see!

Anyway that's it for this week, expect more next Saturday.. I looked at my calendar and realized that the first test is approaching -- kinda scared, not gonna lie. So yeah, 'til next time, cya..

2nd Entry

2008-09-20T21:36:00.000-07:00

Wow, I can't beleive it's already been two weeks! I've made it through my first 236 Problem Set, and I've gotta say, I'm really happy the way it turned out. I was initially scared after reading the questions, but then after I took a breath and calmed myself down, I realized that they were extremely similar to examples we did in class. In the first question I had to prove (using simple induction) that the right-most unit digits of 4^n (n being from the set of all natural numbers) were either a 1, 4 or 6. I used the example from class with 3^n to help me set up and structure the proof, but more importantly, I understood everything I was doing and why I was doing it. The second question on the other hand, took a little bit more thinking..

I'm not going to retype the entire question because I'm sure whoever is reading this knows what it was about haha, but I stumbled on this proof for a few unexpected reasons. I figured out the induction step pretty easily after doing some scratch work, but trying to explain the reasoning behind the induction step is where I had trouble. I went to Danny's office hours this week and overheard him talking to another student about how some proofs can consist of just writing, and that mathematical mumbo-jumbo isn't always neccessary. I think the way a person expresses themselves and conveys their thoughts into writing is super important, and it's actually one of the hardest parts of the proof. The math part is either right or wrong and is entirely based on whether you understand what you're doing -- but proving something using nothing but words? That's tough. I mean, what really makes a well-written, clear and concise proof?

What I realized is that it takes a lot of time and rough-drafts to get a proof exactly the way you want it. I swear I wrote up the answer to question two a million times before it met all of the TA's and Danny's requirements. What I thought were such little, trivial things actually constituted as major parts of the proof. I had everything written down, but in a somewhat unorganized and unclear manner. I didn't properly convey the connection between the claim and the Induction Step, and not because of what I had written down, but the way it was written down. However with some help and a little rephrasing I was able to write up a proof I couldn't have been happier with -- and now that I know the importance of "techincal writing", I think I'll be more prepared for future problem-sets, tests, quizzes and assignments.

Anyway, this is already turning out to be too long of a post so I'll try to wrap it up as quick as I can. The use of the tablet in lecture is awesome - I love it. Makes everything a lot easier to read and we have access to all the notes online, which is really cool. The 1st Assignment is coming along slowly but surely haha, I'm going to try to spend a lot of tommorow working on it. Other then that I'm just trying to grasp the concept of Complete Induction and figure out a strategy to know which one to use (Complete vs. Simple). Anyway I'm going to stop writing now because this is turning into a novel, but yeah, I'll be writing more next week.. so.. cya!

1st Entry

2008-09-13T21:07:00.000-07:00

I've been searching through my old notes and trying my best to get back on track, seeing how four monthes of a very relaxing summer has finally caught up with me. Regardless, I was really happy with how I did in CSC165 last semester and I've actually been looking forward to being in CSC236. Using proofs and logic is something I never thought I'd enjoy, but now that I've finally got it, I love it. I'm now able to understand and solve problems that I never think I would've before. Last year's class also helped me relearn the fundamental rules of math that I chose to ignore throughout highschool, which is why instead of being scared and unsure like I was at the beginning of CSC165 -- I'm confident and excited to see how I do in 236.

Now I'm not going to lie, simple induction isn't really my thing. I understand all of the examples in class, but finding the forumla for the induction step is what seems to give me trouble. I worry that I won't be able to get to the answer without Danny up at the board going step by step through the solution. Eventually I'm sure I'll be able to find some sort of pattern or strategy, but for now it's just somewhat of a struggle. The same thing happened to me last year with proofs, so I guess in the end all it takes is time and a lot of practise.

I'm going to begin working on Problem Set 1 tommorow and then take a look at the 1st Assignment at the beginning of the week. The questions in the first problem set seem familiar to what we've been doing in class. Finding the base case is usually straight-forward for me (...until Danny mentioned the possibiliy of more then one, or in some cases none ... haha) it's just using all the cases to form the formula ... or equation ... the Induction step, basically.. that's we're the trouble comes in.

I'm sure the course-work will pick up a lot this week with more examples and topics to learn. I'll probably be posting in this blog once a week, like I did last semester. Maybe a couple of in-between posts too. I think that worked out pretty well. Anyway, better get to work! Cya.