week 13 -- test 3, final entry

Today I wrote test 3, and found no problems with it; it seemed fairly straight forward. I thought there might be a pumping lemma question on it, but it was mostly material covered in the last assignment.

I think the exam might be more tricky than anything we've been exposed to so far (just a hunch). I plan on looking over all material covered in assignment, problem sets and lecture. I think my weaknesses lie within the last section (CFGs) and maybe correctness and structural induction.

As this is my last post, I thought I might reflect back upon the course in general. I actually found it to be a little challenging at first. I made some mistakes in the approaches I initially took and did not have good vision for what the proofs should look like. I think I've gone a good distance towards developing a bit of that vision. Rather than getting scared at the thought of writing induction proofs, I enjoy trying to construct them. Of course, I realize this course might be relatively easy compared to other more advanced math/CS courses. But its definitely peaked my interest in the field. I thank Danny and the T.A.s for helping guide me through my initial troubles and showing me different ways to approach a given problem.

week 12 -- exam review, test 3

I've started studying for the exam and also getting ready for test 3. I was surprised to learn that test 3 was going to be only on regular expressions (ch7) and not on context free grammars (ch8). But I guess ch8 will be saved for the exam.

I'm finding languages to be very interesting, especially with context-free grammars being tied in with programming languages. I find that the automata models that are presented offer a good visualization of what strings may be accepted within a specified language. I imagine that this has big implications within computer science, given that much of it deals with parsing certain regular and non regular languages.

For the exam, I plan on looking through past exams and working through those problems. Right now, I feel confident about general induction proofs (ch2), as well as correctness proofs. I need a bit of work with languages, in order to feel confident. I'll probably feel better after having studied for test 3.

After looking at the partial solutions for A3, I'm curious as to how my question 4 will be marked. On the solutions, there are only 5 states; but for my solution I had 10 states. I still think my solution works, but I guess that having fewer states would probably be a better solution. I wonder how it might be marked, and if there will be deductions.

week 11 -- a3

Well, after just having finished a3 (literally), I'm feeling good about regular expressions and finite state automata. I didn't find any of the material too difficult and found the assignment (fairly) straightforward. Most of the definitions and proofs in regular expression are defined using structural induction, which I feel that I am already familiar with.

Question 4 on the assignment did pose me a bit of trouble. I initially took the approach of analyzing entire strings that were multiples of 5, trying to find a pattern, which I felt would help me nail down which states a corresponding machine might take. In going to TA office hours, I found out that this was the wrong approach. I found it was better to look at each individual symbol as it was being inputted into the machine, where a 0 would multiply that number by 2 and a 1 would multiply that number by 2 and then add 1. To find the machine I then just looked at the last digit (in base 10) and made 10 states accordingly.

week 10

I am currently working on assignment 3 and am not finding it too difficult (although I've retracted that statement in the past on previous assignments). There doesn't seem to be any questions that are very abstract and that would require many hours of laboring (ahem, a2 question 1). Or maybe I am just becoming more comfortable with induction proofs (hopefully!).

I've studied the course notes for regular expressions quite a bit now and find them to be fairly intuitive. We've already encountered a few questions in the course involving strings, but I suppose now it is simply more formal, together with different sets of alphabets.

For problem set 5, it asked to prove that for a finite set of strings there would be a regular expression that would denote the respective language. For my answer I first showed that it would be defined over some finite alphabet and then showed that by definition there would then be a regular expression to denote that alphabet. Now thinking back, it may have been good to give more details about the first step of the proof and actually show by induction that there would be a finite alphabet.

week 9

After writing the test this past week, I feel I did fairly well. I believe my biggest stumbling block at the moment is converting a proposed solution into formal notation. I feel I can grasp the content of the material fairly well, I just do not feel very comfortable with the precision and detail given by my answers. I think that with time that I may gain confidence in the format of my answers.

One example that surprised me was the one given on the past tests. It was a problem that involved a 'zigzag' function and asked to prove that if the precondition holds, then the program terminates. My answer did not use induction and seemed fairly informal when compared to the model solution, which had three claims, one of which was proven through induction. I am beginning to see mathematics as more of a language, so hopefully, as with any other languages, the more I speak it the more fluent I will become.

week 8

I'm currently getting ready for test 2 and waiting for the solutions for assignment 2.  I feel that I did fairly well on assignment 2.  Question 2 had me slightly confused at moments, as I overcomplicated things.  In the course notes, for the mergesort example, they make the assumption that n is a power of 2 in order to get rid of the floors and ceilings.  I hadn't realized that this assumption was only necessary for that purpose, but had thought (for some strange reason) that is was necessary in order to obtain the closed form, and that it would apply to the assignment question.  As I found out in the TA office hours, this wasn't necessary.  I believe the correct solution only calls for a closed form found through repeated substitution and then reduction with a floor of log7n.  The last question in the assignment, on correctness, was very similiar to what we learned in lecture and in the course notes.  I believe the only difference was that we had to show that m was between b and e, where m = sqrt(b*e)

For the test, I plan on practicing some of the extra problems in the course notes and reviewing the assignment.  Hopefully, there won't be any extra tricky problems in the test that ask for some sort of complicated assumptions.  From what I've seen so far, correctness doesn't look to be too difficult.  I'll review what's in the course notes and lecture notes.

week 7

Thankfully, q4 in the assignment does not deal with complexity, and is on correctness, which I find much easier.  I'm finding q1 to be difficult, everytime that I think I'm close to coming up with a formula, I end up stuck (and frustrated).  I'm also finding it difficult to express q3 in the assignment without using the stats combination formula, but I think that its fine that I use it, even if it isn't the model solution.  For q2, I think I have an answer, but it seems almost too easy.  We'll just have to wait and see...

As I mentioned, program correctness looks to be much easier (at least for now).  Rather than having to find induction formulas, or manoeuvre through some tricky proof in complexity, its more like providing an analysis of an already complete algorithm.

week 6

Right now I'm currently busy with assignment #2.  In general, I'm finding divide and conquer recurrences kind of tricky.  Proving a conjecture based upon a more simply defined function such as Fibonacci sequence looked to be much more straightforward.  Trying to deal with complexity, as well as the ceilings and floors looks to add a new degree of difficulty.  But I suppose its a matter of working through it.  The last question on the assignment looks tough, and deals with a divide and conquer recurrence.  I imagine it will be a lot of work to tackle proving a tight asymptotic bound.  I'll write up another post later in the week, after I really get into the assignment.  

after test 1

Well, I found out that the reason q3 was so troubling for me was because of an error in my math.  It was a simple arithmetical error that gave me -phi for n3/n4.  And as a result, I thought that n4 was negative.  I now see (and it makes perfect sense) that the cycle of natural numbers will proceed indefinitely, and that a contradiction can be found by trying to find a smallest number.  I guess the only thing that can be learned from this is to be more careful, and double check all my results.  Also, more time (and help sought) for the next assignment would be advisable.

I had just went through test 1 last week, and found it to be fair, yet challenging.  My last question, was where, if I remember correctly, I had to show that a set of natural numbers {1, ..., n}, which was missing either 1 or 2, or both, had 3*2^(n-2) subsets.  I initially took the wrong approach, where, for some reason, I tried to directly prove this.  I realized, with 5 minutes left, that this question was exactly like the ones seen in the PS and assignment.  I didn't need to show that it works for P(n), but only show that P(n)=>P(n+1).  I will probably get part marks for this, but again, lesson learned.  Hopefully, or eventually, I'll get quicker at seeing what kind of problem is in front of me, and then taking the right approach :).

A1 over with, next up -- test 1

Well, after trying to work through A1, and understanding it better, it proved to be much tougher than I initially thought.  I think I answered the first two questions correctly, but had trouble with the third, and ended up giving a partial solution.

Next time I'm going to start working at the assignment much sooner, so that I can visit office hours and get help, if I need it.  I now have just over a week until the first test and am going to start preparing for it right away.  I'll go through all the exercises in the textbook and maybe go through previous terms questions/tests as well.  Maybe also do some csc165 proofs, just to rehash everything.

First post; difficulties with induction

This is the first post in my CSC 236 Slog, and I welcome anyone who has given their time to read it.  Over the next few months, I will keep an active record of all the challenges that I face in CSC 236, as well as my plans on overcoming them, and my expressions of relief and happiness if or when I do overcome them.  So far, I've found the course to be fairly challenging and have spent a fair bit of time looking at the given proofs and then looking them over again.  I hope, and believe, that with time and effort they will eventually seep into my head and I will gain a greater understanding for the material.  I realize I am late to the game, and I should have started this blog a week ago, so this post might be quite long just to catch up. 

It's been a couple of years since I last took CSC 165, and unfortunately this course looks like it is heavily dependent upon it.  Thankfully, I began refreshing material, as well as looking at the past year's version of CSC 236 during the summer and I believe I am ready for this course.  I remember doing induction in high school, but of course the problems were nowhere near this level.  The preliminaries section at the beginning of the course notes helps immensely in learning and refreshing the basics of the set theory used in this course.  Many of the terms such as superset, proper superset/subset, and intensional/extensional I had never heard before.

So far, after week 1 and 2, we have gotten nearly through the first chapter on induction.  I feel as though we've gone through a lot material in the first 2 weeks, but I guess that might be expected from such a demanding course.  I'm currently at the point where I have a decent grasp of simple induction, and am currently getting a better understanding of complete induction, as well as its differences from simple induction.  I'm still a little unsure of when to use base cases (and how many), and when not to.  I think I will have a better understanding after problem set 2 and assignment 1.  I've started assignment 1, and have a pretty good idea of how to go about the first 3 questions.  To be honest, I'm finding it pretty easy, and am hoping that it will be enough to prepare everyone for the first test.  I will probably go to the help center or one of the office hours just to make sure that I'm on the right track.  There are also a few problems in the course notes that I'm unsure of why they took the approach they did.