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.