Description

Sundry
Before you start writing your final homework submission, state briefly how you worked on it. Who else did you work with? List names and email addresses. (In case of homework party, you can just describe the group.)
1 Exam Policy and Practice
Please read the all the documents (Policy, Key Changes, and Reminders) of the Exam Policy carefully before proceeding. This question is designed to familiarize you with some of the things you will have to do during the exam.
(a) After reading through the Exam Policy carefully, please answer the following questions.
(i) Given you experience no disruptions during the exam, how many total minutes do you have for scanning and submission?
(ii) Are you required to record locally during the exam? How much space should you have available on your computer for a local recording?
(iii) How should you contact the course staff for an emergency situation during the exam?
(b) Please configure your Zoom link.
(i) You should use the same Zoom link to join the meeting for the midterm as the Zoom link that you send to us. This can easily be done by submitting your Personal Meeting Room link and setting your Personal Meeting ID as your default on all devices you will be using for the final.
(ii) Ensure anyone can join your Zoom link and that there is no waiting room for your Zoom meeting.
(iii) Please the following Google Form with your Zoom link that you plan to use.
(c) You will now conduct a Zoom recording. Please read all instructions beforehand. You will use this recording to submit the mock midterm on gradescope, and should use the remaining time of the recording to work through a practice exam or other study material to simulate the actual circumstances of the final exam. It is advised to complete the LaTex Rehearsal beforehand, to familiarize yourself with typing LaTex answers.
(i) Start the Zoom call for the link you provided above. Turn on your microphone and recording device (webcam, phone camera). Turn off your speaker. Share your entire desktop (not just a particular window).
(iii) Hold your CalID next to your face and record yourself saying your name into the webcam. Both your face and your entire CalID should be visible in the video. We should be able to read your name and SID. This step should take at least 3 seconds. See figure ??. If you do not have a CalID for some reason, please hold up some document which has an image of you and proves your identity, such as a driver’s license.

Figure 1: ID card demonstration. Do not actually black out your SID and name.
(iv) Position your recording device in such a way that we can see your workspace and your hands as best as possible. We suggest using your phone to record your hands, but if you are not, then it should be visible in the recording, face down. See figure ??.

Figure 2: Demonstration of taking your exam. Your setup should look like this while you are taking the exam. The video must be on with your hands visible, alongside your exam pdf or gradescope.
(v) Your microphone should be on at all times. We should be able to see the time on your desktop at all times.
(vi) Record for two hours.
(vii) There are two mock midterm assignments on gradescope. You will see similar assignments on the day of the actual midterm. The one with (Short Answer) will be similar to Vitamins, where you will enter your answers in the gradescope assignment. The other (Written), will be full solution questions, and you will need to scan in your answers.
(viii) Complete and submit to the two mock midterm assignments. This includes both the short answers online, as well as scanning and submitting the written portion of the assignment.
(ix) For the remaining time, you should work through a practice final exam or other study material for the course. The more realistic it is to actually taking a final, the better practice it will be for you on the final.
Link for policy: https://docs.google.com/document/d/1-r3KrjQ46lX-OOiwx6lsoqAeSW0bDdM2oIw0xlKhLi0/edit?usp=sharing
Form to submit Zoom link: https://forms.gle/2HDJtQijTzQdutgX8
Form to submit 2 hour video link: https://forms.gle/XTJLhhbhqBNnKkxN9
2 Message is too noisy
In this problem, we are going to discuss the decoding procedure even when the codeword is corrupted more than they could be. For all parts, work in mod 17.
(a) Encode the message (0,1,4) into a polynomial, where P(0) = 0,P(1) = 1,P(2) = 4, what is P?
(b) Suppose you send the message (P(0),P(1),P(2),P(3),P(4)) to the receiver and last packet is corrupted to 0. Run the decoding process and calulate the Q,E as defined in the lecture. You should also confirm that Q(x)/E(x) = P(x).
(c) After corrupting the 4-th packet to 6 and 5-th packet to 8, decode again, by computing Q,E,Q(x)/E(x), and outputting the first 3 packets. Explain why the decoded message is not the original message, but rather (1,1,4).
(d) Define the Hamming distance between two messages to be the number of packets that differ. For example, the distance between (0,1,2,3,4) and (0,1,1,4,4) is 2 since they differ at the third and forth position.
Let RS[5,3] be all Reed-Solomon codewords with codeword length 5, message length 3. Show that the Hamming distance between any two codewords in RS[5,3] is at least 3. Also show that the codeword (1,1,3,7,13) (which the decoder finds) has the smallest Hamming distance from the non-codeword (1,1,4,7,13) compared to all other codeword in RS[5,3].
(e) We generalize RS[m,n] to be all Reed-Solomon codewords with length m, message length n. (Note: min Hamming distance between any pair of valid codewords is m−n+1). LetC0 be the corrupted codeword, msg = Decode(C0), E = Encode(msg). Hamming(x,y) is the hamming distance between x and y. Show
Hamming (Hamming
Hint: if there are too many corruptions, clearly it will decode to a wrong message.
3 Linearity
Prove that Reed Solomon codes are linear; that is, the element-wise sum of two Reed Solomon codewords is also a Reed Solomon codeword. To do this, use the coefficient encoding rather than interpolation encoding: If you have a message of length n and you want to send m packets, create a degree n−1 polynomial p(x) where your message (c0,c1,…,cn−1) are the coefficients of p(x), and the codeword is the evaluation of p(x) at {0,1,…,m−1}. (Assume we are working on GF(p) for large enough p.)
4 Multiplicative
Recall RS[m,n] to be all Reed-Solomon codewords with length m, message length n. Given two codewords a,b ∈ RS[m,n]. Let c = a ∗ b be the element-wise product of a and b. Show that c ∈ RS[m,2n−1]. (Assume we are working over GF(p), where p is large enough)
5 Maze
(a) Given a 4×4 grid, how many different paths from (0,0) to (4,4) satisfy the following condition:
• You can only go from (x,y) to either (x+1,y) or (x,y+1)
(b) Given a 4×4 grid, how many different paths from (0,0) to (4,4) satisfy the following condition:
• You can only go from (x,y) to either (x+1,y) or (x,y+1)
• You cannot go to points (x,y) where y > x, in other word, you cannot cross line y = x
(c) How many sequences of 4 pairs of parentheses are mismatched? An example of a matched sequence of paretheses is ()()()(), while a mismatched sequence is )))(((.
6 Good Game
Player will send ’GG’ (Good Game) to the winner after each defeat in a 1v1 competitive game. Maru is a skilled Terran player in the Game. And he is 27 pts behind Player Sierral. Suppose Sierral has finished all of his games and Maru has 10 games to go. If Maru wins the i-th game, he will get i pts.
(a) What’s the maximum number of GGs that Maru can send and have a higher points than Sierral?
(b) How many different ways that Maru can defeat Sierral (earns more than 27 pts)?
7 Counting Functions
(a) Compute g(n), the number of ways to divide {1,2,3,…,n} into 2 non-empty groups.
(b) Compute f(n), the number of ways to divide {1,2,3,…,n} into 3 non-empty groups. (Hint: our calculation involves a recursive formula, and included g)