算法代写 | EECS 376: Foundations of Computer Science Fall 2020 Homework 10

这个作业是完成概率相关的算法分析
EECS 376: Foundations of Computer Science
Fall 2020 Homework 10

Problems marked with E are graded on effort, which means that they are graded subjectively on
the perceived effort you put into them, rather than on correctness. For bonus questions, we will
not provide any insight during office hours or Piazza, and we do not guarantee anything about the
difficulty of these questions. We strongly encourage you to typeset your solutions in LATEX.
If you collaborated with someone, you must state their names. You must write your own solution
and may not look at any other student’s write-up.
0. If applicable, state the name(s) and uniqname(s) of your collaborator(s).
1. One way to estimate √
3 is by randomly throwing darts (represented as red points) uniformly
into a 1 × 1 square, similar to how we estimated π in class:
In the above diagram, the gray shaded region is an equilateral triangle.
For any given dart thrown at point (x, y), we can determine if the following are true:
• 3x
2 > y2
• 3(1 − x)
2 > y2
A geometric analysis reveals that a dart thrown at (x, y) lies in the shaded triangle precisely
when both of these inequalities are true.
Let p be the probability that a randomly thrown dart lies in the shaded region. In other
words, p is the area of the triangle divided by the area of the square. By throwing many
darts, we can estimate this p and use it to approximate √
3.
(a) What is the theoretical value of p? You will need to use this for part (c).
(b) Suppose we run t trials of the above process and arrive at an estimate of τ for √
3. Using
Chernoff bounds, give an upper bound for the number of trials
√
n necessary to estimate
3 using this method such that
i. |τ −
√
3| < 0.1 = 10−1 with probability 99%.
ii. |τ −
√
3| < 0.01 = 10−2 with probability 99%.
iii. |τ −
√
3| < 0.001 = 10−3 with probability 99%. E (c) On Canvas, we have provided a C++ program called findSqrtThree.cpp that calculates the value of √ 3 using a random number generator. If you encounter problems running on your computer, please compile and run it on CAEN (we tested that the program should terminate in a reasonable amount of time on CAEN). 2. You are trying to connect a network of server clusters and decide to take a randomized approach for connecting one cluster to another. To represent this network, we denote by Gn,p a random, undirected graph on n vertices constructed as follows: for each distinct set of two vertices u, v ∈ V , include the edge (u, v) in Gn,p with probability p. (a) What is the expected number of edges in Gn,p? In other words, what is the expected number of inter-cluster connections in the network? (b) Given v ∈ Gn,p, what is the expected value of deg(v)? In other words, what is the expected number of other clusters that an arbitrary cluster is connected with? (c) Assume n > 1. Let D be a blackbox that picks a random vertex (server cluster) v ∈
Gn,p and returns deg(v). Describe an algorithm that, using D as the only way to get
information about edges in G, produces output whose expected value is p. In other words,
solely by looking at the completed network, the algorithm estimates the probability that
originally was used to randomly connect server clusters to each other.
(d) Let p
0 be the estimate for p returned by your algorithm in part (c). Use Chernoff bounds
to give an upper bound on the probability that p
0 ≥ 3p. Your answer should depend on
p and n.
3. A hash function maps data objects to the indices of an array where they are stored; we would
like the function to distribute the objects roughly evenly among the indices. Suppose we need
to hash a large number n of objects to k indices. Consider an “ideal” function f that maps
each object to a uniformly random and independent index in {1, 2, . . . , k}.
(a) Let Xi be a random variable for the number of objects that f hashes to index i. Find,
with proof, a closed-form expression for Ex[Xi
].
(b) Find, with proof, an upper bound on the probability that f maps at least 2 · Ex[Xi
]
different objects to index i:
i. Using Markov’s inequality
ii. Using Chernoff bounds
iii. Under what condition on n and k does each method yield a tighter bound?
(c) Assuming that n, k are such that the Chernoff bound is the tighter of the two bounds
above, give an upper bound on the probability that f hashes at least 2 · Ex[Xi
] objects
to index i for some index i.
E (d) Consider the probability that some index i has more than 2 · Ex[Xi
] objects hashing to
it. Assuming that k 
√
n, describe how this probability behaves as n grows.