CS365 Homework 1 Solution

• There are 3 paper-pencil-like problems and 1 coding problem.
• LaTeX is recommended but hand-written solutions will be accepted as long as they are legible. The coding part and the associated text should be coded in the Jupyter notebook provided to you on the class Git repo.
• No extension will be provided, unless for serious documented reasons.
• Start early!
• Study the material taught in class, and feel free to do so in small groups, but the solutions should be a product of your own work.
• This is not a multiple choice homework; reasoning, and mathematical proofs are required before giving your final answer.
1 Is there a path from s to t? [15 points]

Figure 1: How likely is water to reach t from s?
Consider the network shown in Figure 1. Recall that pi is the probability pipe i breaks down, and that pipes break down independently.
1. What is the probability water can go from the water source s to the destination village t? Explain your answer. You do not need to simplify it algebraically.
2 PIN Cracker [30 Points]
John has a cell phone with a PIN that consists of 4 digits (0-9). Unfortunately John totally forgot his PIN, but at least he can try PIN numbers as many times as he wants to without blocking the device. He applies the following two strategies1:
(s1) He tries a valid PIN uniformly at random each hour, till he enters the right one.
(s2) He keeps track of the unsuccessful attempts, and chooses a PIN uniformly at random from the PIN numbers he has not tried yet.
2. Let X1,X2 be the number of trials under strategies s1 and s2 respectively. Compute their expectations analytically:
i) [5 points] E[X1].
ii) [5 points] E[X2].
3. [10 points] Apply Markov’s inequality to upper bound the probability P(Xi ≥ 7000) for i = 1,2. Does Markov’s inequality always provide meaningful bounds?

1In reality, there exist better strategies to break a PIN https://www.popsci.com/technology/article/
2012-09/infographic-day-fastest-way-crack-4-digit-pin-number/, but let’s assume we employ only naive strategies here.
3 [25 points]
Provide clean proofs and calculations for the following problems.

4 Coding [30 points]
The coding part of the homework is available on Git here . Follow the instructions in the Jupyter notebook. After finishing it, download the notebook in PDF format, which should include all the code and figures. If you have trouble converting it to PDF, you can download it as HTML, and then save it as PDF. Submit the math problems and coding problems separately in two files through Gradescope.