assignment
代写Algorithm | app | Python | assignment – 该题目是一个常规的app的练习题目代写, 涵盖了web/Algorithm/app/Python等程序代做方面, 这个项目是assignment代写的代写题目
Total points: 80 (+0 bonus)
assignment 3
Written assignment
- [17 points] Visitmetrics.torproject.orgto answer the following questions about Tor: (a) [4 points] Give the total amount of advertised bandwidth of relays with the Guard flag (but not the Exit flag) and relays with the Exit flag (but not the Guard flag) on 2020-02-01. Which is more? Give one reason to explain this phenomenon. (b) [4 points] Give the median download rate of a file (in bytes per second) for a 50 KiB file and a 5 MiB file to theop-hkonionserver on 2020-02-01. Can you explain the difference? (c) [5 points] The download times measured in the above were done on circuits with three nodes, randomly chosen across the globe. Based on these figures, estimate the median download rate for a 50 KiB file if Tor used only one node. You may need to make certain assumptions; write them down. (d) [4 points] Determine the growth (as a ratio) in the bandwidth spent on answering directory requests between 2017-01-01 to 2018-01-01. A directory request is a list of all Tor nodes sent by directories when a user connects to Tor. What is the main cause of this growth? Use figures to support your conclusion.
- We have four data privacy techniques:
- k-anonymity
- Differential privacy
- Secure multiparty computation (SMPC)
- Private information retrieval (PIR)
For each scenario below, two of the four data privacy techniques will be proposed to
resolve the challenge. Choose the correct one, explain why it is suitable, and why the
other choice is not suitable.
(a) [4 points] A failing streaming entertainment company wants to revitalize its busi-
ness by improving its recommendation algorithm. The recommendation algorithm
takes in private data such as user location, viewing hours, and demographic infor-
mation, and outputs recommendations of what shows to watch. The company will
run a public contest and select the best algorithm. To run the contest, they need
to give contestants access to millions of entires of private data, which is a violation
of privacy if not done with a privacy-preserving method. Proposals:k-anonymity,
SMPC.
(b) [4 points] You want to buy a new smart device that encourages a healthy lifestyle
by monitoring your daily exercise. The device needs to track your movement on
a map to know how much calories you are actually expending (e.g. hiking and
swimming is different from walking). However, you consider this to be a privacy
risk: you do not want the app to know where you are at all times. A new company
making these smart devices is willing to use a data privacy technique to protect
your privacy. Proposals: differential privacy, PIR.
(c) [4 points] You would like to purchase a new web domain. However, you are aware
of the practice of cybersquatting; people may purchase the domain first if they know
it is in demand, and sell it to you at an elevated price. You want to know if the
domain is still available, but you are worried that attempting a DNS query for the
domain will lead to some DNS servers purchasing it immediately for cybersquatting.
To assure potential customers that it is not malicious, a DNS server is willing to
cooperate with you and implement a privacy-preserving algorithm. Proposals: k-
anonymity, PIR.
(d) [4 points] People are anxious to know if they are living in the same apartment as
someone infected with the infectious CROW disease. The hospital that holds all this
information is willing to run a privacy-preserving Algorithm with worried potential
infectees to check if someone living in their apartment has been infected. Proposals:
differential privacy, SMPC.
Programming assignment
Error Correcting Codes[47 points]
Error Correcting Codes (ECCs) can be used in unsafe transmission or storage devices
to improve reliability by providing redundancy. Unlike checksums, ECCs can automat-
ically correct errors up to a certain number of bits. In this question, you will be asked
to implement the general Hamming code, which can correct any 1-bit error in a general
string. (Do not use a Hamming code library it should be your own code.) The speci-
fications of the Hamming code are as follows; it has been slightly modified to discourage
code sharing from other Hamming code implementations.
- Write the input data string as a bitstring according to ASCII.
- Choose enough parity bits and intersperse the data bits with parity bits, so that thei-th parity bitpiis followed by exactly 2i^1 1 data bits. Denote thei-th bit ofHasHi; the first bit isH 1. Denote the length ofHas|H|.
- LetB(x) be the bitstring representation of the integerx, for example,B(5) = 00101.
- Define eachMito be a set of specific bit positions inH, such thatMiis the set of integers 1x|H|where thei-th least significant bit ofB(x) is 1.
- Set the parity bitpito be the XOR of all the bits ofHin the positions indicated byMi, exceptpiitself, which is always located atH 2 i 1 :
pi=
xMi\{ 2 i^1 }
Hx
Here is a more detailed explanation ofMi. Consider the integerx= 10, soB(10) is
- Then the 1st least significant bit is 0, the 2nd is 1, the 3rd is 0, and the 4th is 1 (reverse the bitstring). Soxbelongs toM 2 andM 4 , not toM 1 andM 3. To work out an example:
- The input data string is ab, which becomes 0110000101100010 (16 data bits).
- We need five parity bits,p 1 , p 2 , p 3 , p 4 , p 5 , as follows:
H=p 1 p 20 p 3110 p 40001011 p 500010
p 5 can be followed by up to 15 data bits, but we ran out of data bits, so we stopped
there.H 3 = 0 andH 8 =p 4 .|H|= 21.
- For example,B(20) = 10100.
- M 1 ={ 1 , 3 , 5 , 7 , 9 , 11 , 13 , 15 , 17 , 19 , 21 } M 2 ={ 2 , 3 , 6 , 7 , 10 , 11 , 14 , 15 , 18 , 19 } M 3 ={ 4 , 5 , 6 , 7 , 12 , 13 , 14 , 15 , 20 , 21 } M 4 ={ 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 } M 5 ={ 16 , 17 , 18 , 19 , 20 , 21 }
5.
p 1 =H 3 H 5 H 7 H 9 H 11 H 13 H 15 H 17 H 19 H 21 = 0
p 2 =H 3 H 6 H 7 ... = 1
p 3 =H 5 H 6 H 7 ... = 0
p 4 =... = 1
p 5 =... = 1
(a) [20 points] Write a program that will automatically generate the correct parity bits
for any input string. The input string will be the first argument of the program.
Your program, calleda3a, should write the parity bits in the correct order tostdout
(e.g. cout or print) ascharacters, 0 or 1. Continuing the above example, if
the program is called with:
./a3a ab
The program should display:
01011
(b) [20 points] Write a program that will automatically correct any one-bit error in either the parity or the data string. The parity will be the first argument of the program, and the data string will be the second argument of the program. Your program, calleda3b, should output thecorrectedparity bits to the first line of stdout, and thecorrecteddata string to the second line ofstdout. If there is no correction to be made, you should still output the original parity bits and the data string. For example, if I run your program with:
./a3b 01011 ac
Your output should be:
01011
ab
The program will always be tested with the correct number of parity bits, and there
will either be a one-bit error in the parity or the data string, or no error. Either
type of error should be fixed. Also, note the meaning of an ASCII one-bit error:
a (01100001) can become i (01101001), but a cannot become b (01100010)
because that would be two bit flips.
(c) [7 points] Submit two sentences in filessentence1andsentence2, such that they
have the same Hamming code (as output by part a). They should all be logical
and grammatically correct sentences with no typos, and they should all include
your @sfu.ca SID. Any ASCII characters that are not letters, numbers, or basic
punctuation will be removed.
Hint: It may be easier to construct these sentences if you use numbers somewhere
in your sentence.
Submission instructions
All submissions should be done through CourSys. Submit the following programs:
a3.pdf, containing all your written answers.
Files for the programming assignment:sentence1,sentence2.
Code for the programming assignment, detailed below:
For the programming assignment, submit your code; do not submit any compiled files.
C++: Submit a3a.cpp, a3b.cpp. I will compile them and call./a3a <message>.
Python: Submit a3a.py, a3b.py. I will call Python a3a.py
Java: Submit a3a.java, a3b.java. I will compile withjavac a3a.javaand then calljava
a3a <message>.
If there is a Makefile in your folder, the Makefile will override all of the above. This
implies if you are not writing in C++, Python, or Java, you must include a Makefile.
Keep in mind that plagiarism is a serious academic offense; you may discuss the assign-
ment, but write your assignment alone and do not show or send anyone your answers and
code.
The submission system will be closed exactly 48 hours after the due date of the assign-
ment. Submissions after then will not be accepted unless you have requested an extension
before the due date of the assignment. You will receive no marks if there is no submission
within 48 hours after the due date.