Proofs and Algorithms

After the assignment, which was decently difficult, I feel much more confident about epsilon-delta proofs. I feel like I understand the whole limit definition concept much better. At least now, it is much more clear how you can pick your variables and on which variables you can make them dependent. Hopefully, I'll be prepared for whatever epsilon-delta proof that may (probably) come up on the test. I really feel like this assignment has greatly increased my understanding of proofs, particularly epsilon-delta ones.

The unit on proofs is pretty interesting, but still not as interesting as the one on logic. Too bad it is coming to an end.

According to the syllabus, the next topic should be on complexity and program running time, which I suppose is related to algorithms. I didn't know what algorithms are until I took a psychology class in high school, where I learned that algorithms are a series of finite steps that always generate a consistent and desired result. Compare that to heuristics, which generate a desired result most of the time. This is obviously all related to problem solving. For instance, an algorithm for unlocking a four-digit lock would be to try every possible four-digit combination out there. If you know the person whom the lock belongs to, a heuristic would be to try the year s/he was born, favorite number, graduating year, etc.

Obviously, algorithms are helpful in programming and for this reason, they are probably of great interest to computer science. Algorithms are all about computation after all, and computers just follow algorithms. Since computer science is about the theoretical aspects of computation, algorithms are probably one the most important aspects of computer science. I have more to say about algorithms next time.

(On a slightly random note, I feel that many first-year students in the computer science program don't realize how theoretical computer science is. I remember walking with two friends the other day. Person A is a first year computer science student and person B is a first year software engineering student. We were talking about programming and person B told us how he knows C, Java, Ruby, Scheme, etc, which is great. Then, person A said, "It's so stupid how computer science here is really theoretical." WTF? That's what computer science is all about. Computer is theoretical and mathematical, and that's why I love it. For those of you who are in the CS program to learn lots of programming so that you can make lots of money working for some company in the software industry, please drop out and transfer to Waterloo or some other school and study software engineering instead.)

Assignment 2 and proofs in general

The second assignment is turning out to be fairly difficult. The first part is not too difficult and neither is the third part. It's the second part that's pain. I spent a lot of time trying to figure out what the statements even mean. Now I think I might have figured out what they mean, but I'm still not sure whether or not they are true. I think epsilon-delta proofs are the only type of proofs where you can get away without entirely understanding how they work. When I first learned about them, I spent a lot of time trying to understand exactly how the proofs work and why you can set delta to be the minimum of two values. In the end, I never really understood them, but I still managed to get by in tests without truly understanding them entirely. Eventually, doing limit proofs becomes really mechanical. It's just a matter of expressing epsilon in terms of delta and finding a delta that works. You don't really need to understand the thought process behind it. Well, I think that's coming to haunt me now.

So far, I feel this course hasn't really provided me with many tools in doing proofs. All I've really learned is how to write proofs in a more rigorous manner and what you have to show for the different quantifiers. But doing the proof itself isn't any easier. I guess you can't really teach proofs. The part in the middle of the proof, the part that requires a lot of brainpower and creativity, can't really be taught. At most, I think all this course can do is help us expand our thinking when we actually come to that middle part.

On a related note, I think I like logic more. It's fun to work with those symbols and it's easy to understand and it isn't very hard either. My cousin told me that logic courses tend to be fairly easy, and I can see why that's true. This also applies to proving the equivalence of two sentences. All it involves you doing is using a bunch of laws of logic until you can turn one sentence into the other, and hence show equivalence. It's also pretty fun to play around with those symbols.

There are still a few things about proofs that I'm not entirely sure. For instance, you can make delta dependent on epsilon, but why not x? After all, you are saying that for every x, for every epsilon, there is a delta. Hence, shouldn't it also be okay to make delta dependent on x? Also, I'm not entirely sure when I am supposed to indent and leave an indentation block. I'll have to get these straightened out before the test.

Proofs and Puzzles

These past few days, this course has only been concerned with proofs. Although the proofs so far are not difficult, I predict they will eventually become fairly difficult. Proofs have always been one of the hardest aspects of mathematics. As opposed to calculations, which eventually become fairly mechanic, proofs require a high level of intelligence and understanding. It is not simply a matter of following the same algorithm over and over again. Usually, the middle part is the most difficult. It's the part that requires some intuition, some intense reasoning, and (excuse the cliche) the ability to think outside the box.

It's not that proofs are particularly difficult for me. Not to say that I am particularly good at proofs, but I tend to get along on math test. The way I've always studied for math is to do lots of problems. Even when it comes to proofs, to study for those, I would do a lot proof problems. So far, it's working pretty well, but maybe this course can give me more effective methods at tackling proofs.

Anyways, I might as well use this opportunity to record a problem solving scenario. The problem I had to solve was the tutorial 3 office hour puzzle. Since this puzzle was decently easy, in the future, I will probably post another problem solving scenario.

Anyways, the link to the tutorial can be found here: http://www.cdf.toronto.edu/~heap/165/W10/Tutorial/t3/t3.pdf

Understand the problem:

This problem is fairly straightforward to understand. Basically, you are given a bunch of information, and from that information, you have to figure out the order the students came to the office and what each students wants to do.

The second step is to plan a solution, and for this fairly simple problem, there isn't going to be a complex plan of any sort. Basically, I am going to list all the given information one by one and try to deduce further information from the given information. Basically, the plan is to just connect the dots.

So, we know that the last two are not interested in computer games and one of them is interested in designing programs to create music. We also know that Alex came to office hours first, so he could be interested in computer games, but he is not interested in computer generated music. We know that Kim did not arrive second and did not arrive first either, and is not interested in video games, which makes sense given what we know. Since someone came after Lee, we know that Lee could be second or third. And finally, we know that the last person wants to study bioinformatics.

Now, from this, we know that Lee could not have been third, since the person who came after him wants to design databases, and the last person wants to study bioinformatics. Hence, Lee could only have been second. We also know that the last person is female and that Kim is male, and hence, Kim could not have been fourth. Hence, Kim is third and that leaves Robin to be fourth.

Since Robin is fourth, she is interested in bioinformatics. Since the person who came after Lee is interested in databases, that means that Kim is interested in databases. And, since Alex is not interested in computer generated music, that means that Lee is, and that Alex is interested in video games. Thus, we have:

Alex: first, computer games

Lee: second, music

Kim: third, databases

Robin: last, bioinformatics

However, I guess it can be argued that we don't know what Alex is interested in. All the problem says is that the last two are not interested in computer games and that neither is Alex. That does not necessarily mean that anybody is interested in computer games. But, I guess it is implied.

Looking back, I realize that this problem is just a matter of connecting the dots. Next time I'm faced with a similar problem, I'll also begin by listing all the given information and try to deduce further information from that. Now, I get my opiods.

Law of Excluded Middle

Hmm, so we're doing proofs now. I sort of liked logic more, but maybe we'll start doing logic proofs. So far the proofs are pretty easy, so I'll have to see. I sort of find the indenting and commenting and necessity of introducing very obvious statements somewhat tedious. In Calculus, the proofs are less formal without all that indenting and I don't have to explain so many steps.

I was recently getting distracted by Wikipedia and read the article on the law of excluded middle: either P or not P. Basically, a statement is either true or false, and obviously can't be both. This reminded me of an essay I read about Bertrand Russell. The essay started with the statement: "The king of France is bald." Clearly, this statement is not true, which according to the law of excluded middle, means that the opposite must be true: "The king of France is not bald." However, this does not seem to be any more true, since France does not have a king. Yet, we can't just discard these statements and call them meaningless. They do have a clear logical form. Logic seems so much more clear when you are only using symbols. When applied to natural language, logic seems to screw up a lot of times. In any case, Russell's solution to treat sentences of the form "The F is a G" as three separate claims: "There is an F", "no more than one thing is the F", "and if anything is an F, then it is G." Basically, he tries to treat it as universally quantified. In the case of the king of France, this resolves the problem, because there is no king of France. But, what if I made the statement: "Santa Claus is jolly." Once again, there is no Santa Claus, but intuitively, even though there is no Santa Claus, this seems to be a true statement to me, especially in contrast to its negation. In any case, Russell's solution appears in an essay On Denoting, which I have never read. Maybe he addresses the issue of fictional characters. I would have to read his essay to find out.

Another thing that is also bugging me is this pair of sentences: "The next sentence is false. The previous sentence is true." If every statement is either true or false, then which one of these statements is true and which one is false? Or, is it meaningless to assign truth and false values to these statements; that these statements are neither true nor false? Even if it is meaningless to do assign truth and false values, I don't think these statements themselves are meaningless.