The end is nigh

As the school year builds towards its climax (i.e. exams), I feel almost overwhelmed with work, school, and my upcoming trip to California. There is a lot to do in the next few weeks, and it seems not enough time to do it! I won't get into the specifics of my personal life though, since this is after all the course log for CSC165.

One consequence of my monolithic work load is that the current assignment in this course seems more intimidating than ever, especially the last two questions. Calculus was always my worst subject in high school (and at U of T), so I anticipate quite a struggle in solving these. I have the first three questions done, but the nature of the last two feels alien to me, and I have avoided even trying to solve them for 24 hours now, using my work in other courses as an excuse. However, with the assistance of the course notes and my black belt in Google-fu, I am confident that I will be able to work out how to solve both problems before Wednesday night.

My primary concern is with question #4, where you have to make use of limit techniques to prove a statement involving variable powers. I barely managed to figure out how to use the definition of a limit to solve question #3, so I anticipate it will be even tougher to wrangle the answer out of question #4.

To start, I would have to figure out whether I need to prove or disprove that 3^n is in O(2^n). Intuitively, it seems that the claim is true, since both 3^n and 2^n are within the same order n, so some value c should be able to make 2^n greater than 3^n. Therefore, it would seem that (1/c)(3^n/2^n) would always be less than 1. This is about as far as I have gotten on creating an action plan to solve the problem, and I don't yet know where limits come into play. Hopefully looking at it tomorrow with fresh eyes will yield some epiphany.

Big Oh!

Thanks to all the proofs we've been having to do, I think I'm actually getting better at them! "Big O" and "Big Omega" are interesting concepts, and proofs involving them seems like a natural extension of what we were doing the weeks before. Most proofs involving Big O/Omega seem very formulaic, and not too difficult so long as you know what steps to take. In tutorial, it took me a long while to figure out the algorithm for building this new breed of proof, but once I figured it out, I realized how simple it was. The same goes for general proofs about functions. As interesting as I find the concept of Big O and its cousins to be, I am not really sure how it is related to the field of computer science, beyond being a convenient model for running time. I can see some connection to steps taken by a computer program, but the relationship is hazy in my mind and I don't quite understand.

The due date for the third assignment is coming up, and I still haven't figured out how to use Texmaker. I've installed LaTeX and everything, but the editor is still not working. Oh well, I guess it's back to MS Word for me.

I am not sure what I think of computablity and the halting problem yet. At this stage, the self-referential nature of a lot of halting problem still has my brain fried at times, but I think I'll get it eventually.

Assignment Two PROVED to be difficult!

Assignment 2 was, in my opinion at least, a lot harder than the first one. When it comes to proofs, I am often flabbergasted by the sheer number of options I have to approach it. I don't find it as intuitive as some people to know when to factor, or square both sides, or multiply by a constant. It feels to me like I'm grasping around in the dark for something that might have some potential to get me where I want.

That being said, I do think that the way proofs are approached in this course is a lot more my style than, say, high school math. Maybe it's because the course material was effective in introducing the foundations, but I generally feel more warmly towards proofs in this course than ones I previously encountered. Assignment 2 was still pretty hard, though.

In particular, I could not come up with a solution for question #4, so I simply wrote the structure, did the first step that I was sure was right, then wrote "I cannot solve this past this step." Hopefully the "substantial part marks" given to incomplete proofs really are substantial. Looking at the solutions, however, the answer seems almost embarrassingly obvious.

I had managed to get to the step where I squared both sides of the equation n = 11q + 5, and I knew that the only thing I could do from there was expand it into n^2 = 121q^2 + 110q + 25. After that, I couldn't figure out how to manipulate that polynomial into the form 11p + 3. The solution was to separate 25 into 22 + 3 then pull 11 out of each of the terms except 3. Unfortunately, I was just as dense solving this problem as I was during the tutorial quiz on February 26, where I ran into a similar situation and was unable to perform the simple arithmetic required to split an integer into two other integers. At least now I am aware that this is something I often overlook, so I (hopefully) won't make the same mistake in the future. 

Also, interestingly, we were allowed to write all of the proofs for the assignment in plain English! I didn't realize that until I had already completed (er, almost completed) the assignment, but I think if I had written some of the proofs in English it would have helped me get a better grasp on what was required, and maybe I would have finished it sooner and with fewer mistakes. 

Ah well. I will have to make sure I do the next assignment well in advance.

It's been awhile since my last SLog post, and quite a bit has happened since then. The new topic we're covering is on proofs, although in the tutorial quiz last Tuesday all we had to know was the structure of a proof, not how to actually create one. I'm not complaining, though, since I have never had a amicable relationship with mathematical proofs. I generally find that the more open a question is and the more tools we have at our disposal, the more difficult it is for me to choose the right one to use, especially when it comes to algebra.

Regarding the midterm, I think it went pretty well. I spent more time than I would have liked on some of the questions and just barely finished on time, although I was fairly confident in my answers. As Danny revealed in his overview of the test, there was a quicker and more elegant solution to the questions than the brutish path I took.

The assignment was also due in the period between my last post and this one. It took me ages to get everything the way I wanted, but I am overall pretty pleased with the result. I took the time to make it presentable and even, dare I say, organized: something I almost never do. There is just something about mathematical notation liberally sandwiched between paragraph blocks that is so aesthetically pleasing, but maybe I'm just weird. In any case, I'm hoping for a good mark but saying that is probably redundant since I doubt anyone would assume I were looking to fail. So, thanks for visiting, hope you have a great day, dear reader.

Solving a Problem with Polya (and why it killed me)

In this second SLog post I will write about a "problem-solving episode" using Polya's method, despite my reservations against using "catch-all" problem solving blueprints. The problem I want to tackle is one presented in the second tutorial handout, problem 1(g). The problem asks:

Let C be a set of courses, and let P(x, y) mean course x is a prerequisite for course y.  Rewrite the following symbolically:

(g) "Some courses have the same prerequisites."

I chose this problem because it presented me with the greatest difficulty in tutorial; I must have spent half the tutorial time thinking about it.

I will start with the first step, according to Polya, which is to understand the problem. Our objective is to rewrite the English statement given in (g) in symbolic notation, using what we have learned in the course so far. The data we are given is that C is a set of all courses and that P(x, y) describes a relation between two courses. The statement in (g) also gives us some more data. "Some courses have the same prerequisites" can be interpreted to mean that at least two different courses share one prerequisite. This immediately tells us that three objects are needed to express (g) in mathematical notation.

Now that we have identified the relevant information, let us assign variables to the objects:

• Let x be one course with at least one prerequisite
• Let y be a second course with at least one prerequisite
• Let z be a course that is a prerequisite of some other course(s)

If we are visual problem solvers, we could also draw a Venn diagram at this point consisting of two interlocking circles contained within a box. The box would represent C, the set of courses, and the two circles would represent the sets "prerequisites of x" and "prerequisites of y," for some x and y. The intersection of the sets contains all the possible values of z that are prerequisites of both x and y. In other words, our solution should be true if and only if the intersection is not empty.

With just these facts in mind, we do not yet have enough information to translate the phrase into notation, so we should move to Step 2 of Polya's problem solving model: Devising a Plan. 

First, we should determine the general structure of our symbolic statement. From previous questions (a) to (f), we know that these statements should always be introduced by quantifiers, either ∀ or ∃. The term "some courses" in (g) immediately tells us that the "courses," x and y, must be existentially quantified because of the use of the word "some." To determine the quantifier used to introduce z, we can think about the nature of the problem. Our final solution will be a statement that is true if and only if there exists some x and some y such that a certain condition is met. This means that the existence of a specific x and a specific y is needed to fulfill the condition, so we use the existential quantifier. However, the truth value of the statement does not depend on the existence of a specific z. The identity of z can be any value in set C, and is only specified if we assign actual values to x and y. Therefore, we must use the universal quantifier ∀ to introduce z.

Now that we know which quantifiers to use for x, y, and z, we must solve the bulk of the problem: how do we represent the condition in (g) using mathematical notation? We know that in order for the courses x and y to have the same prerequisite z, both P(z, x) and P(z, y) must be true. At first, this might lead us to conclude that the condition could be represented as P(z, x) ∧ P(z, y), but this means something different. P(z, x) ∧ P(z, y) would only be true if there exists some x and some y such that all possible values of z are prerequisites of both. This is clearly very different from what we want, and is a mistake I initially made. If we don't want to imply that the statement is true if and only if x and y share every possible prerequisite, we need to use an implication. Using an implication would ensure that our statement is true only so long as at least one possible z is a prerequisite of both y and x. Which direction should the implication go? If the implication went in only one direction [ P(z, x) → P(z, y) ] then there could be the case where z is a prerequisite in the consequent but not in the antecedent. Since the antecedent is false, the implication is true and the statement will be true even if z is an element of only one of the two courses. Therefore, the implication must go both ways; if z is a prerequisite for one course it must also be a prerequisite for the other course for the implication to be true. 

We finally have all the parts we need to construct our mathematical representation of the phrase "Some courses have the same prerequisites." This marks our transition into Part 3 of the Polya model, Carrying Out the Plan. To summarize, here is the plan so far:

1. The statement begins with three quantifying statements, ∃x ∈ C, ∃y ∈ C, ∀z ∈ C
2. The statement makes the double implication that if z is a prerequisite for x, then z is a prerequisite for y and that if z is a prerequisite for y then z is a prerequisite for x. Written as P(z, x) ↔ P(z, y)

The implementation of this plan is simply the combination of the two steps, into the statement:

∃x ∈ C, ∃y ∈ C, ∀z ∈ C, P(z, x) ↔ P(z, y)

To check our solution, we should try using test cases. For example:

If x, y both have a prerequisite z

• P(z, x) is True and P(z, y) is True, P(z, x) ↔ P(z, y) is True.

If x has a prerequisite z but y does not

• P(z, x) is True and P(z, y) is False, P(z, x) ↔ P(z, y) is False.

If y has a prerequisite z but x does not

• P(z, y) is true and P(z, x) is False, P(z, x) ↔ P(z, y) is False. 

Here ends my explanation of how I solved problem 1(g) from last tutorial, organized by Polya's model. However, I have to express some annoyance because only now after I have finished writing my SLog do I realize that I have run into the same problem I did last week. Despite being able to arrive at the solution using Polya's method, I was still rather uncomfortable with the answer. Some part of it didn't seem to make sense to me, and I couldn't figure out why, until I just realized that I had misunderstood the phrasing of the question again. This miscommunication has been the sole root of my frustration for the past 7 hours, and I can only describe my emotional state as "mortified." I had spent so long trying to understand a question I thought was difficult, only to realize that it wasn't complicated, just ambiguous. Again. 

I suppose I could have asked for clarification on the question, but I know at least one other person in my tutorial was confused by this as well, and I am sure there are many others. "Some courses have the same prerequisites" can be taken to mean two very different things, that "Some courses share the exact same prerequisites" or that "Some courses share some of the same prerequisites" depending on how you look at it. For example, if I say that "some people have the same pants" I mean that some people have at least one pair of pants in common, not that they all have the same set of pants in their wardrobe. If I say "some people like the same movies," however, I am much more likely to mean that some people have the exact same taste in movies. 

In closing, English is one of the most unpredictable languages in the world, and it has more exceptions to its rules than any other European language. While I started off writing about a problem I had solved, I am going to end my post with an appeal to the CSC165 teaching team. I like this course, and I know that Danny, the TAs, and the rest of the staff work hard to make sure the students learn as much as they can, but there is absolutely nothing more frustrating in a logic course than finding out that you chose the wrong interpretation of an ambiguously worded question. I hope that in the future greater care can be taken to ensure that each question has only one possible meaning. especially on the graded portions of the course. 

January 16th, 2013 - "Why is my answer wrong?!?!?!"

CSC165 SLog Post - January 16th, 2013

The first week of CSC165 sneaked by quietly. With no assignments (except this one) having been assigned yet, I had been focusing most of my attention on my other courses. However, contrary to my expectations for a course called "Mathematical expression and reasoning", I now find myself enjoying CSC165. I am planning on taking PHL245, Modern Symbolic Logic, next year, and I really think CSC165 will give me an opportunity to acclimatize myself with the mode of thinking required of courses on logic. This course is surprisingly independent of programming languages and I can already see how I can apply the material learned to other facets of my life. Logic and reasoning play very large roles in my decision making process as well as my personality.

I met Maria, my TA, in tutorial on Tuesday. It feels strange to write about someone when you know they will be reading what you wrote in the near future. After we had worked through the tutorial handout and the answers had been put up, I realized that the answer my partner and I had for the last question was the only one that was different than what was on the board. I tried to find where I went wrong but the more I examined the question the more convinced I became that our answer was right. I asked Maria about the question but our initial discussion did not provide me with a satisfactory answer, and I still did not understand why my answer was different. A friendly colleague sitting in front of me tried to explain to me the answer we were given, and after he explained his reasoning I shared mine. In my argument I made use of counterexamples, quantifiers, and sets and I realized that just a week into the course I had already absorbed enough information for me to verbally illustrate my points using what I learned. After we mulled over the question some more, the other student agreed that my answer was right.

Knowing now that I wasn't crazy or just stupid and emboldened by the support of my fellow student, I approached Maria again to continue our discussion. Another student who had apparently reached the same conclusion I had went up as well and together we debated what the answer to the last question was. Eventually, the three of us agreed that the mistake was not in our answers but in the question itself; it was not phrased the right way.

The question asked for a Venn diagram of the False condition of the statement "There is one of the three python programs that fails all three test suites." However, no set was given for programs that "fail all three test suites." This set is not complementary to the set of programs that pass all three test suites (T), since there exist cases where a program does not fail all three but does not pass all three either, passing either one or two of the test suites. Therefore, in the Venn Diagram of the False condition of that statement, Q can be occupied if some program passes 1 or 2 test suites or empty if all three programs pass all three test suites. T can be occupied or unoccupied as well since there may or may not be programs in set P that pass all three tests and are not in Q. The intersection of Q and T can be occupied if there is a program of Q that passes all three tests (is also in T), or unoccupied if all three programs in Q only pass either 1 or 2 tests. Therefore, it is impossible to know whether any of the three regions of this Venn diagram are occupied, and the identity of all three regions should be "?." My conclusion was later verified when Danny sent the class an email with corrections made to the last question.

In the hours after, I thought more about the question and I now believe that the statement the last question had intended to convey is "There is one of the three python programs that does not pass all three test suites." Thanks to the murky ambiguities of the English language, the meaning of "fails all three test suites" is subtly (but importantly) different from "does not pass all three test suites." To "fail all three test suites" requires that the program fail all three of t1, t2, and t3. To "not pass all three test suites" requires that not all of t1, t2, and t3 are passed by the program, i.e. the program fails at least one test suite. If we use this statement for the question instead, the answer does indeed work out to be the one given, [X - O - ?]

The frustrations of lexical miscommunication aside, I rather enjoyed working through why the question didn't match the answer. Figuring out what the question actually meant was much more difficult of a puzzle than the questions given in tutorial. I think my experience working on this problem made me realize one great thing about CSC165: the material it covers and the language it uses leaves absolutely no room for ambiguity and uncertainty when it comes to writing and grading assignments and exams. So long as you understand the question, you already have everything you need to write down the answer; it's just a matter of putting everything in the right place. I can't believe I'm saying this, but I think I'm actually looking forward to our first test.