Last Post

So, I'll make this my last slog post. This course made me realize how much I enjoy the theoretical and mathematical aspect of computer science and overall, I really enjoyed this course. I plan on focusing more on this aspect of computer science and taking upper year courses on computability, algorithms, and what not. And, although I may sound like I'm fawning, I'm honestly not.

Well, later.

Floating Point Numbers and Knights and Knaves III

This week, we seemed to have moved to a slightly unrelated topic regarding floating-point numbers and how numbers are represented in computers. It's sort of interesting and it certainly explains a few questions I've had regarding how arithmetic is done in computers. However, it seems unrelated to everything else that we've covered. All the logic that we learned at the beginning of the semester, that was necessary in order to do proofs in a rigorous manner and to understand mathematical symbols. So, the topic on proofs followed naturally from the topic on logic. Likewise, the topic on Big-Oh also followed naturally from the topic on proofs, since proving that a function is in Big-Oh of another function is just, well, a more specific type of proof. For now at least, the topic on floating point numbers seems unrelated to everything else we've learned this year.

This is not to say that the current topic isn't interesting, because it is. I've certainly never learned something like this in math before. Originally, after the first week, I thought this course would be all about mathematical logic. Obviously, it isn't, but that would have still been great. In any case, I realize now that this course is mostly an introduction to the mathematical and theoretical aspects of computer science. This includes numerical analysis, which seems to be what we are working on right now.

As I've predicted, the assignment was pretty easy. On the first assignment, I wasn't too sure about the necessary and sufficient conditions, and so I had to go to the CSC help center to get that figured out. On the second assignment, I wasn't too sure about the delta-epsilon proofs, so I had to go to office hours and the CSC help center to get those figured this. This time, however, there isn't a single thing I'm confused about. Everything is fair and straightforward and is similar to what we covered in lecture. Hopefully, I'll do well on this assignment.

So anyways, back to knights and knaves:

5. A and B are guarding two doors, one leading to treasure and one leading to a ferocious lion which will surely eat you. You must choose one door. You may as one guard on yes/no question before choosing a door. What question do you ask? Is it easier if you know one is a knight and one is knave (but you don't know which is which)?

Understand the problem: First, the answer to the last question is yes. I don't know how I can possibly solve this question if I didn't know some fact about the two guards. If I know one is a knight and the other is a knave, I can take advantage of that fact and phrase my question is such a way so that a knight and a knave will return the same answer, and such a question would involve me asking a question to one guard about the other guard. Otherwise, if I know nothing about the guards, then I would somehow have to phrase my question so that a knight and knave would return the same answer, independent of the other. And, I'm not really sure how to do that.

Planning a solution: Basically, my plan is to just come up with a list of possible questions and see what the answers would be if the guard is a knight and if the guard is a knave. If the answers are the same, then that would be question I would ask.

Carry out your plan: This took a while to figure out. Eventually, I realized that this would work as a solution: point to a random door and ask the guard, "Would the other guard say this door leads to the treasure?" If the guard is a knight, then the other guard is a knave. And, since knights tell the truth, if that random door does lead to the treasure, then he would say no, since he would know that the other guard, being a knave, would lie. If the door leads to the lion, then he would say yes, since that would be what the knave would say. Likewise, if the guard whom you are asking the question to is a knave, then the other guard is a knight. So, if the door does lead to the treasure, the knave would realize that the knight would say yes, and since knaves lie, then the knave would say no. If the door leads to the lion, then that means that the other guard, being a knight, would say no, leading to the knave saying yes. Basically, in the end, if the guard says yes, go through the other door. If the guard says no, go through that door.

Review: I was fairly difficult to come up with the right question to ask. I tried other possible questions, such as "Is the other guard a knave?" Eventually, I settled on the one above, since it was the first question that I found to work. There might be other ones that work. Notice how my question assumes that the guards know what the other guard is. Maybe that is not the case, in which I case I would have to come up with another answer to this problem. So, after all, my solution might not be that great after all. Oh well...

Algorithms, Knights, and Knaves II

So, we have moved on from just Big-O to Big-Omega and Big-Theta. There isn't much difference between the three (in terms of proof structure). Proofs regarding one of these are just as easy as proofs regarding others. We have also moved on to talking about steps and timing in an algorithm, which isn't all too bad. However, the definition given for the worst case run-time, in symbolic form, as well as finding the lower and upper bounds for that run-time, is a little bit confusing, but I have to get that confusion sorted out, at least before the test. It usually works out in the end, so I'm not too worried.

The third exercise, like the other two, is decently easy. The third assignment seems deceptively easy. In the past, on assignments, there were usually a few problems that I could not figure out, so I had to go to office hours, CSC help center, or stay behind after lecture. This time, all the problems seem completely do-able. I've done a few of them, and they were pretty easy. I'll just have to see if the rest of the assignment is just as easy.

So, back to knights and knaves:

3. Person A says: "If B is a knave, then I am a knight". Person B says: "We are different." What are A and B?

Understand the problem: We see here A stating an implication, not a bi-implication. That might be important. Also, it would probably help to know how to negate implications.

Plan a solution: In this case, as in all cases, it would be helpful to consider the different possible cases and the logical implications of such cases. In other words, if A is a knight, then certain things must hold true. If we get a contradiction between what must logically be true and what is the case in the question, then we know that that case is false, and we move on to another case.

Carrying out the plan:

For the first case, suppose A is a knight. Then, he would be telling the truth and the implication would be true, but the implication does not tell us what B is. Suppose B is a knave. In this case, A and B are different, so B would be telling the truth, but knaves lie. So, B can't be a knave. Suppose B is a knight. Well, in this case, B would be lying, so B can't be a knight. Hence, A being a knight leads to contradictions, so A must be a knave.

Case 2: A is a knave. Then, A would be lying, so the negation of the implication is "B is a knave and A is a knave." Well, if B is a knave, then B would be lying and everything makes sense. If B is a knight, then that would be going against the negation of the implication, which we know to be true. Hence, both A and B are knaves.

Review: It was helpful to consider each case and figure out the one that makes sense (logically). It's also helpful to have a good understanding of logic, which allows us to solve these puzzles.

4. You ask A: "Are you both knights?" A answers either Yes or No, but you don't know enough to solve the problem. You then ask B: "Are you both Knaves?" B answers Yes or No, and now, you know the answer. What are A and B?

Understanding the problem: the last three problems could have been done mentally, but this one would be difficult to keep track of without a pencil and a piece of paper. A few things to keep in mind for this one: Just knowing A's answer is not enough and knowing B's answer after A's answer is enough. Hence, it's can't be the case where knowing A's answer is enough to solve the problem, nor can it be the case where knowing B's answer in addition to knowing A's answer is not enough to solve the problem. If I run into any of these two cases, then I can disregard them. Additionally, the negation of "A and B are both knights" is not "A and B are both knaves."

Planning: I'll write out the various cases, consider the various knights/knaves combinations that can arise out of those cases, and figure out which ones are logically consistent with the problem as a whole (there should only be one, otherwise you can't really solve this problem), and pick that one. That should be the solution.

Carrying out the plan:

The question posed to A: Are you both knights?

The question posed to B: Are you both knaves?

Case 1: A says yes and B says yes. If A is a knight, then A is telling the truth, so B must necessarily be a knight. But, B would be lying by answering yes, so we have a contradiction, meaning A can't be a knight. If A is a knave, then he would be lying. In this situation, if B is a knight, by answering yes, he would be lying, since they are obviously not both knaves. If B is a knave, then both A and B are knaves, so B would be telling the truth by answering yes. Yet again, we get a contradiction. Hence, considering the possible arrangements of knight and knave, we can conclude that the case "yes, yes" is not logically possible.

Case 2: A says yes and B says no. If A is a knight, then B is also necessarily a knight (as previously explained). And, B would be telling the truth by answering no. So, this works out, but we are not done. If A is a knave, then A and B are obviously not both knights, so A would be lying. If B is a knight, then B would be telling the truth by answering no. So, it also works in this case too. Consider also if B is a knave. Then, both A and B are knaves, so by answering no, B would be lying. Once again, it works out. Hence, we see that the case "yes, no" leads to three different knight and knave arrangements. Hence, A and B's answers are not enough to figure out what they are. So obviously, the solution is not here.

Case 3: A says no and B says no. If A is a knight, then he would be telling the truth, so B would necessarily be a knave. But, by answering no, B would also be telling the truth, since they are not both knaves. Hence, B can't be a knave in this situation and A can't be a knight. If A is a knave, then A would lying. So in reality, both A and B are knights, but we get a contradiction. So, A can't be a knight. Hence, the "no, no" case is also not logically consistent.

Case 4: A says no and B says yes. By process of elimination, this is probably the right case. But, we'll double check to be sure. If A is a knight, then B is necessarily a knave. And, by answering yes, B would be lying, since they are obviously not both knaves. So, it's consistent in this situation. If A is a knave, then in reality, both A and B are knights. And, as previously shown, we get a contradiction. So, in this case, there is only one logically consistent combination: A is a knight and B is a knave. And, since there is only one logically consistent combination, that means A and B's answers are enough, so this is the right combination.

Review: As predicted, it would be difficult to solve this puzzle without writing out the possible combinations on a piece of paper. There might have been a faster way to solve this, but whatever. Essentially, this is just a matter of using truth tables. This shows that for problems that involve more extensive thinking, it's easier to write it out.

Algorithms, Knights, and Knaves

So, as I predicted, we did start talking about algorithms this week. So far, we are only talking about algorithm analysis, and not so much about algorithm design and proving (or disproving) algorithms. Essentially, we are talking about the order that an algorithm runs in, but we haven't actually looked at algorithms themselves. Maybe this is more of an upper-year topic.

Proving that a function belongs to some order isn't actually very difficult, and neither is proving that a function does not belong to some order. For the former, you are allowed to pick B and C to be whatever you want, so long as you don't express them in terms of n (and so long as you pick them from their respective domains). That essentially gives you two powerful tools to work with, one to bound n and the other to increase g. Additionally, inequalities allow for more manipulation that equalities would not. For instance, if you have n <= q, you can add 5 to the RHS and still preserve the inequality. However, if it were an equality, you would not be able to preserve it. Inequalities allow for more flexibility.

As for the latter, although in this case you are only allowed to pick n, you can express it in terms of B and c, so that n can be greater than B while also greater than cg(n). So far, I haven't had trouble with these either during tutorial or with the exercise (I don't plan on looking at the assignment until I have handed in my exercise).

I might as well use this opportunity to detail the solving of another problem/puzzle: the knights and knaves puzzle contained in the first chapter. Since the puzzle is in three parts, I'll solve the first two parts today. As you know, knights always tell the truth and knaves always lie.

1. Person A says, "I am a knave or B is a knight." What is A or B?

Understand the problem: Basically, all I know is that A is a knave or a knight, and the same goes for B. So, A is either lying or telling the truth, and apparently, all that A says is enough to figure out what A is. I feel in this case (and in all the other knights and knaves problems), it helps to draw a truth table, but that's pretty hard to draw in a blog. I also have to keep in mind that this is not an exclusive "or".

Plan a solution: Basically, I'll draw a truth table were A is a knave and B is a knight, A is a knight and B is a knave,... and then I'll try to figure out which one of these possible options does not lead to a contradiction, and that would be the answer.

Carrying out the plan: If A is a knight, then he is telling the truth, so that means that B is also a knight (since A is clearly not a knave). And, that doesn't lead to any contradiction. If A is a knave, then he is lying. Hence, the negation is true: that he is not a knave and B is not a knight (By De Morgan's laws). This obviously contradicts the premise that A is a knave.

Review: This shows how useful Boolean algebra can be. This isn't too difficult of a problem, so I don't there is much to review. There weren't many things that "blocked progress" or lead to "breakthroughs".

2. Person A says, "We are both knaves." What are A and B?

Understand the problem: Again, we are not sure at first who is lying and who is not. Also, apparently, all that A says is enough to tell what A and B are. What Person A is essentially saying is that "I am a knave and B is a knave." I don't think I really even need to draw out a truth table. I can just solve this by using Boolean algebra.

Plan: Boolean algebra.

Carrying out the plan: A cannot be a knight, since he would be lying by saying that he is a knave, and we would have a contradiction. Hence, A can only be a knave, and the negation of "A is a knave and B is a knave" is "A is not a knave or B is not a knave" (thanks again to De Morgan's laws). We know that A is a knave, so the only possible option is that B is not a knave. Hence, A is a knave and B is a knight.

Review: Once again, we see the usefulness of Boolean logic.

I'll post my solutions to the next two problems next week.

Induction

So apparently, we aren't starting our unit on algorithms... yet. Instead, we are taking some time to talk about proof by induction. When I first learned about the proof by induction, I was a little skeptical. But, when I later thought about it, intuitively, it makes perfect. Of course, you can't really prove it since it is supposed to be axiomatic (however, I have read that in some logical systems with different definitions of natural numbers, you can prove the proof by induction). The way we went over it in class, with the symbols showing how one implies the other, seems to make things much more clear (I might be one of the few who finds symbols easier to understand than words). So far, the proof by induction examples aren't too bad. In calculus, I found proof by induction useful when it comes to proving a statement about a series, usually some sort of sum or product. The funny thing about the proof by induction is that it doesn't actually use inductive reasoning, but deductive reasoning, otherwise it would be disastrous if we based an a priori discipline such as mathematics on inductive logic. Inductive logic (which is more useful in the natural sciences) would be more along the lines of : (1) This piece of ice is cold. (2) Therefore, all ice is cold.

Algorithms are an interesting case because I can't really say whether or not they belong to mathematics. The study of algorithms seems to be an a priori study. I can easily imagine how you can prove or disprove algorithms. For instance, if you follow an algorithm and do not obtain a desired result (essentially providing a counter-example), then that would be a disproof of an algorithm. How would you prove one? Maybe by induction. Maybe using a proof by contradiction. This, I'm not too sure. However, you probably don't prove it by running hundreds of test cases, just like how you don't prove mathematical statements by providing hundreds of examples. However, I think test cases are still useful when it comes to implementation. If an algorithm is proven to be correct, you would still have to run test cases when it comes to actually implementing that algorithm in a specific language. The algorithm might be correct, but that doesn't mean that your implementation is.

However, I'm still not sure whether or not the study of algorithms goes under mathematics. I tend to see mathematics as dealing with quantities, and algorithms don't really have anything to do with quantities.

One of the most interesting subjects (for me at least) is the foundations of mathematics. I don't think U of T actually offers a course in that topic, and I wish it does (that, along with game theory).

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.