After having done two quizzes, I now know the general way to approach them. This being do the tutorial problems as best as you can and then if you have problems, create an instance of the Tutorial class in order to call the haveTheTaExplainProblem() method. The method is extremely valuable. It takes the problem as a parameter and automatically computes the solution, returning valuable experience and knowledge. Since we know that the quiz will consist of one of the several tutorial problems, we can store the return value of the method in a variable so we can use it during the quiz. Neat!
Assignment 1 was very useful. Not only did it allow me to gauge my comprehension level in the course, but it forced me to apply several strategies from previous courses (CSC165). It was not terribly difficult, especially since we had such a long time to do it and many hints along the way.
With the midterm imminent, I have prepared myself by creating a small text file differentiating the types of induction and strategies for each of them. I have found this quite useful (at least for me) and I have even shared it with the closest of my friends (if you want a copy, you should get closer to me ;) ). Knowing when and how to use each style of induction based on the problem will enable me to take multiple perspectives on each problem, thus completing them much quicker. Then I have extra time at the end of the test to check over my answers!
One of the interesting problems I faced over the span of last week was assignment 1's question 4. While most struggled with it, I felt quite confident in my answer. I will share my insights without giving away the answers in case someone wishes to try it again.
So we begin by setting the predicate we will be proving.
P(n): A binary string of length n that begins and ends with the same bit has even number of occurrences of substrings from {01, 10}.
Well, what is the shortest length of a binary string? 0? Well if it were 0, then the string has no bits so it cannot start and end with the same bit. This is thus vacuously true, but it does not help our later induction. What about 1? Well, the substrings we care about are of length 2, so it has no instances of either, yet still begins and ends with the same bit. Let's make this our basecase. 0 is even since it is divisible by 2 (0 = 2n where n = 0).
For our inductive step, we should notice that there are two possible cases for this string: either the string begins and ends with the same bit, or it does not.
So naturally we separate the two cases. For the case where they begin and end with the same bit, we notice that there are two possible subcases as well. Either we can append another bit identical to the starting bit/ending bit, let's call it j. Or we append j complement, the other bit (if j = 1, then jc = 0)
In both cases, we know that P(n-1) by complete induction since this was our first case.
In subcase 1, we can use complete induction by noticing that without the new appended digit, we have an even number of instances of {10,01}. Thus by adding the new digit, j, we have a substring formed by the last two digits equal to "jj". We then note that "jj" is not in the set {10,01}. Thus the addition digit did nothing to change the number of instances, thus the number of instances is still even by complete induction. So P(n).
In subcase 2, we append jc to the end of the string. Firstly we notice that the starting bit and ending bit are now not equivalent, thus we declare this subcase to be vacuously true.
The rest is quite simple; we have another case with 2 further subcases. Can you complete the rest of the proof? Remember that if it does not start and end with the same bit, you must take the largest substring that satisfies the predicate. Using the largest substring, you know that there is no more instances of j after the last digit in the largest substring. Thus from then onwards, the digits are all jc.
Surely you all knew this much when you handed in assignment 1 though.
Either way, I wish you all luck with the upcoming term test! Enjoy what's left of your thanksgiving.
-ラムダ
No comments:
Post a Comment