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).