ผลต่างระหว่างรุ่นของ "01204211/activity8 polynomials and graph theory 1"
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
แถว 15: | แถว 15: | ||
− | '''A.1-2''' Let's experiment on erasure | + | '''A.1-2''' '''Erasure codes.''' Let's experiment on erasure codes using the degree 3 polynomial <math>f</math> from the last question. You should work with another student. |
''Encoding:'' Let's treat the first 4 digits of your ID <math>a_0,a_1,a_2,a_3</math> as a message. We will encode it into 6 pairs of numbers (modulo 11) like this: <math>(0,f(0))</math>, <math>(1,f(1))</math>, <math>(2,f(2))</math>, <math>(3,f(3))</math>, <math>(4,f(4))</math>, <math>(5,f(5))</math>. | ''Encoding:'' Let's treat the first 4 digits of your ID <math>a_0,a_1,a_2,a_3</math> as a message. We will encode it into 6 pairs of numbers (modulo 11) like this: <math>(0,f(0))</math>, <math>(1,f(1))</math>, <math>(2,f(2))</math>, <math>(3,f(3))</math>, <math>(4,f(4))</math>, <math>(5,f(5))</math>. | ||
แถว 24: | แถว 24: | ||
''Decoding:'' Now suppose that you have already got the encoded message (with 2 missing pairs) from your friend. How can you decode the message? Try to decode the message and check with your friend if you do that correctly. | ''Decoding:'' Now suppose that you have already got the encoded message (with 2 missing pairs) from your friend. How can you decode the message? Try to decode the message and check with your friend if you do that correctly. | ||
+ | |||
+ | |||
+ | '''A.1-3''' '''Secret sharing.''' | ||
=== Graph theory 1 === | === Graph theory 1 === | ||
== Homework == | == Homework == |
รุ่นแก้ไขเมื่อ 01:47, 26 พฤศจิกายน 2558
- This is part of 01204211-58.
In-class activities
Polynomials
- To work on these questions, you can refer to this lecture note from Berkeley.
For this set of activities, we shall work modulo 11.
We will use your student ID as a data. For , let denote the -th digit (counting from the lest, starting at 0) of your student ID. For example if your student ID is 5755543210, , , ,
A.1-1 We shall use your last 4 digits: . Find a polynomial of degree 3 such that for . You should start by writing down .
A.1-2 Erasure codes. Let's experiment on erasure codes using the degree 3 polynomial from the last question. You should work with another student.
Encoding: Let's treat the first 4 digits of your ID as a message. We will encode it into 6 pairs of numbers (modulo 11) like this: , , , , , .
Note that the first 4 pairs represent your message exactly. The last 2 pairs provide extra information.
Now discard 2 of the first 4 pairs, and give the rest (including the last 2 pairs) to your friend. (I.e., you should give your friend 4 pairs of integer modulo 11.) Notes: do not give out the polynomial.
Decoding: Now suppose that you have already got the encoded message (with 2 missing pairs) from your friend. How can you decode the message? Try to decode the message and check with your friend if you do that correctly.
A.1-3 Secret sharing.