Error Correction: Critical Thinking Questions
Each team will receive a deck of cards. For a regular card deck you can use face-up/face-down to represent 0/1. A satisfactory outcome for this activity is that the team can successfully demonstrate the trick to the class. That means, someone will lay out a 5x5 array of cards randomly. Then a member of the team will layout the 6th row and column and will successfully identify the flipped card when some from the class secretly flips a single card.
1.) In the video, are the 6th row and 6th column being laid out in a truly random way or is some kind of rule or algorithm being used? If so, what's the rule?
Yes, the algorithm is that each row and column has an even number of cards that are flipped and not flipped, not odd.
2.) HINT: Count the number of face cards in each row and column. What pattern or rule do you see if you do that?
The rule is that the number of face-up cards must be even, making the face down cards even as well.
3.) Practice: Everyone on the team should practice the "trick" using the widgets or the deck of cards.
n/a
4.) (Portfolio) What is the "trick"? Of course, it's not really a trick. It's an algorithm. So, describe an algorithm in pseudocode that solves the problem of identifying the flipped card.
If the number of flipped cards a row is even, nothing was flipped. If the number of flipped cards is odd, a card in that row or column was flipped. Check all rows/ columns until one has an even number of face-up cards.
5.) (Portfolio) The card "trick" shows that it is always possible to identify the card that was flipped as long as only one card was flipped. Would it be possible always to determine if an error occurred if two cards were flipped? Experiment with the cards or widgets to help answer this question.
Yes tis would be possible, but only if the two cards that were flipped were in different rows and columns. If you flipped two in the same column, the algorithm would stand because the flipped cards would still be an even number, but if they are in different rows/ columns, then the algorithm would still work because there would be an odd number of flipped cards in two rows/ columns.
6.) In this case, the 25 original cards (bits) are data and the 11 additional bits are for error detection, meaning that 25/36 = 69% of the bits are data and 31% are redundant bits used for error detection. Suppose the original array was 3x3. How many error detection bits would you need in that case and what percentage of the total bits would now be data bits?
If the original array was 3x3, you would need 7 error detection bits. 9 bits would be data bits, making up 57% of the total bits.