Recursive Find the Key: My dear friend Chester told me this problem. I still have not looked at the solution from the video, but I found a sweet recursive solution. Then I found an even easier solution. I would love to share these with you. Prison Game: The game has three players: The "encoding" prisoner and the "decoding" prisoner are friends. Together they want to find the key to freedom. The prison warden wants to prevent thern from escaping. But the warden does like to play games with his victims. He hides the key into one of n boxes. The encoder knows its location and must communicate this to the decoder. But how they are able to communicate is very limited. The warden labels each box with a bit which he tells the encoder. The encoder communicates to the decoder by flipping the bit on one of the boxes. The decoder learns only the labelings with the one bit flipped. He does not learn, for example, which bit was flipped. From this alone, the decoder must then be able to determine which of the n boxes contains the key. Your job is two write two recursive programs: Encoder and Decoder. Encoder(n): Pre-Condition: The encoder, who we will refer to as encoder(n), learns the following: . The number of boxes n. The index i of the box containing the key. The vector of n bits labeling the boxes as provided by the warden. Post-Condition: Encoder(n) returns: . The index i' of the box whose bits will be flipped. Decoder(n): Pre-Condition: The decoder, who we will refer to as decoder(n), learns the following: The same vector of n bits given to encoder(n) except with the bit specified by encoder(n) flipped. Post-Condition: Decoder(n) returns: The location i of the key, as told to encoder(n). n = 2: With one box, you know where the key is, so let's consider when you have two. Encode: Pre-Condition: Let zo denote the bit on the zeroth box and 31 on the first. Let i e{0,1} indicate whether the key is in box 0 or in box 1. Post-Condition: If x1 = i, then the encoder (2) says to flip bit 20. Otherwise, he says to flip 1 Decode: Pre-Condition: Let zo and x denote bits on the boxes after the bit specified by the en- coder(2) has been flipped. Post-Condition: One of your test questions is to specify the actions of decoder(2) and to argue that this n = 2 algorithm works. Hints: You know you are to use recursion. Given that the input consists of some n boxes, the obvious thing is to give the first half of these boxes to your first recursive friend and the second half to your second. This, however, does not work. Instead, encoder(n) will name his recursive friends encoder (ni) and encoder(n2), giving them respectively ny and ng boxes, where n = ni x 12. Decoder(n) will do the same. One of your test questions is to determine for which factorization n = nu X n2 your program with n boxes works, assuming of course that these recursive friends solve their problem correctly. The encoder(n) and decoder(n) will each take his n bit vector and arrange the bits into a matrix with ny rows and n2 columns. Then each will determine the parity of each row and of each column. The parity is 1 if the number of 1's is odd.) The following is an example. 01110 101000 01010 on=20. n1 = 4 and n2 = 5. 11001 01001 1 1 The following are your questions: Hint: You might want to reread my recursive steps. (a) Finish the n = 2 case and prove that it works. (b) Explain what encoder(n) does with the help of encoder(ni), and encoder(n2). Hint: If you panic, you will find this hard. If you simply guess, I am quite sure you will figure out the inputs and outputs to these three programs. (c) Explain what decoder(n) does with the help of decoder(n), and decoder(n2). Hint: Same as last hint. (d) In order to prove that the decoder(n) algorithm works, you need to prove that if the instance it is given meets its precondition, then so does the subinstance it gives to each of its recursive friends, decoder(n 1) and decoder(ne). More specifically, suppose that as required, decoder(n) is given the same vector of n bits that were given to encoder(n) except with the bit specified by encoder(n) flipped. Prove that as required, decoder(n) is given the same vector of n bits that were given to encoder(n 1) except with the bit specified by encoder(nu) flipped. (e) Assuming that the recursive friends with ni and n2 boxes respectively correctly solved their problem, argue why encoder(n) and decoder(n) together correctly locate the key. Is this true for every factorization n=ni X n2? Hint: My solutions has 5 quite straight forward sentences. Hint: I did not use the word "prove" in order to avoid mass panic. Hint: A least once a class. I spouted off the steps needed to prove that our recursive program works. It is not hard. Hint: You might want to reread my recursive steps. (f) Characterize the values of n for which your algorithm works and for which it does not. For example, does the algorithm as I described it work for n = 3? Explain why. (g) What is the running time for this algorithm? Does this time depend on the choice of the factor- ization n = ni x ny? Recursive Find the Key: My dear friend Chester told me this problem. I still have not looked at the solution from the video, but I found a sweet recursive solution. Then I found an even easier solution. I would love to share these with you. Prison Game: The game has three players: The "encoding" prisoner and the "decoding" prisoner are friends. Together they want to find the key to freedom. The prison warden wants to prevent thern from escaping. But the warden does like to play games with his victims. He hides the key into one of n boxes. The encoder knows its location and must communicate this to the decoder. But how they are able to communicate is very limited. The warden labels each box with a bit which he tells the encoder. The encoder communicates to the decoder by flipping the bit on one of the boxes. The decoder learns only the labelings with the one bit flipped. He does not learn, for example, which bit was flipped. From this alone, the decoder must then be able to determine which of the n boxes contains the key. Your job is two write two recursive programs: Encoder and Decoder. Encoder(n): Pre-Condition: The encoder, who we will refer to as encoder(n), learns the following: . The number of boxes n. The index i of the box containing the key. The vector of n bits labeling the boxes as provided by the warden. Post-Condition: Encoder(n) returns: . The index i' of the box whose bits will be flipped. Decoder(n): Pre-Condition: The decoder, who we will refer to as decoder(n), learns the following: The same vector of n bits given to encoder(n) except with the bit specified by encoder(n) flipped. Post-Condition: Decoder(n) returns: The location i of the key, as told to encoder(n). n = 2: With one box, you know where the key is, so let's consider when you have two. Encode: Pre-Condition: Let zo denote the bit on the zeroth box and 31 on the first. Let i e{0,1} indicate whether the key is in box 0 or in box 1. Post-Condition: If x1 = i, then the encoder (2) says to flip bit 20. Otherwise, he says to flip 1 Decode: Pre-Condition: Let zo and x denote bits on the boxes after the bit specified by the en- coder(2) has been flipped. Post-Condition: One of your test questions is to specify the actions of decoder(2) and to argue that this n = 2 algorithm works. Hints: You know you are to use recursion. Given that the input consists of some n boxes, the obvious thing is to give the first half of these boxes to your first recursive friend and the second half to your second. This, however, does not work. Instead, encoder(n) will name his recursive friends encoder (ni) and encoder(n2), giving them respectively ny and ng boxes, where n = ni x 12. Decoder(n) will do the same. One of your test questions is to determine for which factorization n = nu X n2 your program with n boxes works, assuming of course that these recursive friends solve their problem correctly. The encoder(n) and decoder(n) will each take his n bit vector and arrange the bits into a matrix with ny rows and n2 columns. Then each will determine the parity of each row and of each column. The parity is 1 if the number of 1's is odd.) The following is an example. 01110 101000 01010 on=20. n1 = 4 and n2 = 5. 11001 01001 1 1 The following are your questions: Hint: You might want to reread my recursive steps. (a) Finish the n = 2 case and prove that it works. (b) Explain what encoder(n) does with the help of encoder(ni), and encoder(n2). Hint: If you panic, you will find this hard. If you simply guess, I am quite sure you will figure out the inputs and outputs to these three programs. (c) Explain what decoder(n) does with the help of decoder(n), and decoder(n2). Hint: Same as last hint. (d) In order to prove that the decoder(n) algorithm works, you need to prove that if the instance it is given meets its precondition, then so does the subinstance it gives to each of its recursive friends, decoder(n 1) and decoder(ne). More specifically, suppose that as required, decoder(n) is given the same vector of n bits that were given to encoder(n) except with the bit specified by encoder(n) flipped. Prove that as required, decoder(n) is given the same vector of n bits that were given to encoder(n 1) except with the bit specified by encoder(nu) flipped. (e) Assuming that the recursive friends with ni and n2 boxes respectively correctly solved their problem, argue why encoder(n) and decoder(n) together correctly locate the key. Is this true for every factorization n=ni X n2? Hint: My solutions has 5 quite straight forward sentences. Hint: I did not use the word "prove" in order to avoid mass panic. Hint: A least once a class. I spouted off the steps needed to prove that our recursive program works. It is not hard. Hint: You might want to reread my recursive steps. (f) Characterize the values of n for which your algorithm works and for which it does not. For example, does the algorithm as I described it work for n = 3? Explain why. (g) What is the running time for this algorithm? Does this time depend on the choice of the factor- ization n = ni x ny