1. Recursion: Define a Recursive Integer List (RIL) to be a list of a finite number of objects, where each object is either an integer or is an RIL. For example, L = (3, 2, [4, 3], [[3,9), (), 8], 7] is an RIL. Give the pheudo code for a recurive algorithm RILSum that given a RIL L, returns the sum of all the integers appearing in it. For example, RILSum(L) = 3+2+4+3+3+9+8+7. No explanation or running time needed. 2. 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 them 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 co denote the bit on the zeroth box and 21 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 xo. Otherwise, he says to flip 31 Decode: Pre-Condition: Let x'o and x' denote bits on the boxes after the bit specified by the en- coder(2) has been flipped. 1 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(n) and encoder(n2), giving them respectively ni and n2 boxes, where n = ni X n2. Decoder (n) will do the same. One of your test questions is to determine for which factorization n=n xn2 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 n 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 l's is odd.) The following is an example. 011101 10100 0 01010 0 n=20, n1 = 4 and n2 = 5. 11001 01001 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(n), 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(ni) and decoder(n2). 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(ni) 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 = nu 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 your 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 n2? 3. Oh dear. I was trying to understand the base cases of the above algorithm and I came up with a much easier algorithm. Instead of laying out the n boxes into a ni X n2 rectangle, spread it into a log n dimensional hypercube. Don't worry about this. Just name each of the n boxes with a unique 2 log n bit binary vector. For example, if n = 16, then the first box will be named (0,0,0,0) and the last the last box will be named (1,1,1,1). We will add these vectors by taking the parity in each of the dimensions/columns, i.e. bit-wise xor. For example, (1,0,1,0) + (1,1,0,0) = (0,1,1,0). One funny thing is that if you add one of these vectors to itself, you get the zero vector, namely (1,0,1,0) + (1,0,1,0) = (0,0,0,0). This helps to show that X + Y = X - Y and X + Y + Y = X. (a) Now each box has a vector name, a bit label given by the warden (one of which is flipped by encoder(n)), and maybe contains the key. Both encoder(n) and decoder(n) will add up the vectors of the boxes that have label 1. Let E and D denote these sums. Let F denote the vector name of the box whose bit encoder(n) flips. Give an equation giving D as a function of E and F. (b) Let K denote the vector name of the box containing the key. Give a simple equation with which decoder(n) will determine K from D. (c) Given this, give an equation with which encoder (n) will determine F from E and K. (d) Characterize the values of n for which your algorithm works and for which it does not. Explain why. 3 1. Recursion: Define a Recursive Integer List (RIL) to be a list of a finite number of objects, where each object is either an integer or is an RIL. For example, L = (3, 2, [4, 3], [[3,9), (), 8], 7] is an RIL. Give the pheudo code for a recurive algorithm RILSum that given a RIL L, returns the sum of all the integers appearing in it. For example, RILSum(L) = 3+2+4+3+3+9+8+7. No explanation or running time needed. 2. 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 them 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 co denote the bit on the zeroth box and 21 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 xo. Otherwise, he says to flip 31 Decode: Pre-Condition: Let x'o and x' denote bits on the boxes after the bit specified by the en- coder(2) has been flipped. 1 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(n) and encoder(n2), giving them respectively ni and n2 boxes, where n = ni X n2. Decoder (n) will do the same. One of your test questions is to determine for which factorization n=n xn2 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 n 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 l's is odd.) The following is an example. 011101 10100 0 01010 0 n=20, n1 = 4 and n2 = 5. 11001 01001 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(n), 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(ni) and decoder(n2). 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(ni) 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 = nu 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 your 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 n2? 3. Oh dear. I was trying to understand the base cases of the above algorithm and I came up with a much easier algorithm. Instead of laying out the n boxes into a ni X n2 rectangle, spread it into a log n dimensional hypercube. Don't worry about this. Just name each of the n boxes with a unique 2 log n bit binary vector. For example, if n = 16, then the first box will be named (0,0,0,0) and the last the last box will be named (1,1,1,1). We will add these vectors by taking the parity in each of the dimensions/columns, i.e. bit-wise xor. For example, (1,0,1,0) + (1,1,0,0) = (0,1,1,0). One funny thing is that if you add one of these vectors to itself, you get the zero vector, namely (1,0,1,0) + (1,0,1,0) = (0,0,0,0). This helps to show that X + Y = X - Y and X + Y + Y = X. (a) Now each box has a vector name, a bit label given by the warden (one of which is flipped by encoder(n)), and maybe contains the key. Both encoder(n) and decoder(n) will add up the vectors of the boxes that have label 1. Let E and D denote these sums. Let F denote the vector name of the box whose bit encoder(n) flips. Give an equation giving D as a function of E and F. (b) Let K denote the vector name of the box containing the key. Give a simple equation with which decoder(n) will determine K from D. (c) Given this, give an equation with which encoder (n) will determine F from E and K. (d) Characterize the values of n for which your algorithm works and for which it does not. Explain why. 3