Advanced Algorithms COMP4121 2020 Solutions to Practice Problems
Here are a few problems of the kind you will be asked to solve on the final exam.
1. You are watching traffic on a busy road and you notice that on average three out of every four trucks on the road are followed by a car, while only one out of every five cars is followed by a truck. What fraction of vehicles on the road are trucks?
Solution: Let the fraction of cars be x and fraction of trucks y; then the probability to see a car is x and the probability to see a truck is y. These probabilities must satisfy
(x, y) 3/4 1/4 = (x, y)
One of the two homogeneous equations is redundant, so we get a solution by
4/5x + 3/4y = x x+y=1
Solution: x = 15/19 and y = 4/19.
2. How many balls in R1000 of radius 1/2 does it take so that these balls together
have the same volume as a unit ball in this space?
Answer: 107150860718626732094842504906 0001810561404811705533607443750388370351 0511249361224931983788156958581275946729 1755314682518714528569231404359845775746 9857480393456777482423098542107460506237 1141877954182153046474983581941267398767 5591655439460770629145711964776865421676 60429831652624386837205668069376
We use the fact that V1/2(1000) = (1/2)1000V (1000); Thus, V (1000) = 21000V1/2(1000).
3. (A tiny bit harder) Let G be a strongly connected directed graph, i.e., a graph such that for any two vertices u,v there exists a path from u to v. A vertex w in G is periodic if there exists an integer k such that every loop containing w has length divisible by k. Show that if one vertex of a strongly connected graph is periodic, then all vertices must also be periodic.
Solution: Assume v is periodic and let w be an arbitrary vertex in G. Then there is a path from v to w and a path from w to v. These two paths together form a loop containing v. Thus, the length of this loop must be divisible by k. Consider now an arbitrary loop l containing w. Then the path consisting of the path from v to w, concatenated with the loop l, concatenated with the path from w to v also forms a loop containing v and its length is thus divisible by k. However, since the sum of the lengths of the paths from v to w and from w to v is divisible by k also the length of the loop l must itself be divisible by k.
4. (Basic probability and the Markov inequality) You are presented with n fair coins, n ≥ 1; you flip each and if it comes tail you get the coin, if it comes head you do not get it.
(a) Use the Markov inequality to show that the probability to win at least 3/4 of all coins is not more than 2/3.
(b) Show that the probability to win at most 1/4 of all coins is also not more than 2/3.
(c) Find a formula for finding the exact probability to win at least k, (0 ≤ k ≤ n) out of n available coins and plot its values for all 0 ≤ k ≤ n and n = 100. (Your formula can contain summations without a closed form; you can use any software you like for computing and plotting.)
(d) Was Markov inequality useful in this problem?
1.0 0.8 0.6 0.4 0.2
20 40 60 80 100
(a) Since the coins are fair, the probability to get a tail at each toss is p = 1/2. Thus, the expected number of coins to be won is E = ni=1(1·p+0·(1− p)) = n/2. Thus, if we denote the random variable “number of tails won” by X. the Markov inequality for the non-negative random variable X implies
P(X≥3/4·n)≤ E = n/2 =2 3/4·n 3/4·n 3
(b) Since the coin is fair, the probability to win 3/4 of all coins is equal the probability to loose 3/4 of all coins which happens just in case you win at most 1/4 of all coins.
(c) The probability to win exactly k coins is npk(1 − p)n−k = 1 n if p = k 2nk
1/2. Thus, the probability P(k) to win at least k coins is P ( k ) = 1 n n
(d) Clearly, the plot of P(k) shows that the probability to win at least 3/4 of all coins, i.e., 75 coins is negligible, but the Markov inequality here only
shows that such probability is smaller than 2/3, which is not a very useful estimate.
5. Consider the deterministic Linear Time Algorithm for Order Statistic.
(a) Assume we split the numbers in groups of seven elements. Derive the asymptotic run time of the algorithm, following closely what we did in the case when we split the input numbers into groups of five.
Hint: You have to figure out what the recursion should look like and for what K you can derive T (n) < K · C · n. In case of splitting into groups of five K = 11 worked. If you split into groups of seven you will need a different K. Try setting K a variable and see what you get if you substitute this into the right side of the recurrence; it should be easy to figure out what K works.
(b) Assume we split the numbers in groups of three elements. Explain why the proof breaks down.
Hint: Show that no K works.
(a) If we split the numbers into groups of 7, then the middle row has n/7 numbers and one half of this row has n/14 numbers. Thus, now 4n/14 many numbers are guaranteed to be smaller or equal to the pivot and as many are larger or equal to the pivot. So after partitioning around the pivot each of the two groups will have at most 10n/14 many elements. So we are making now one call of the recursive procedure for n/7 many elements in the middle row to find a good pivot and another call for at most 10n/14 many elements, i.e., the recurrence now looks as follows
T(n) ≤ T(n/7) + T(10n/14) + Cn
We will now find a number K such that T(n) ≤ KCn. Assuming T(n/7) ≤
KCn/7 and T(10n/14) ≤ KC10n/14 we now have
T (n) ≤ T (n/7)+T (10n/14)+Cn ≤ KCn/7+KC10n/14+Cn = 6KCn/7+Cn
To finish the argument we now need to have 6KCn/7 + Cn ≤ KCn and for this it is enough to take K = 7 because in this case we have
T(n) ≤ 7Cn/7 + 7C10n/14 + Cn = Cn + 5Cn + Cn = 7Cn 4
(b) Assume now that we group numbers into groups of 3; then the middle row would have n/3 many elements and its half n/6 many elements; thus we would have at least 2n/6 elements smaller than the pivot and 2n/6 many elements larger than the pivot. So to find the pivot we would call the algorithm on n/3 many elements and then we would call it on the partition of size at most 2n/3. Assuming that T(n/3) ≤ KCn/3 and T(2n/3) ≤ 2KCn/3 we would now have
T(n) ≤ KCn/3 + 2KCn/3 + Cn = KCn + Cn
To finish the argument we would need that KCn + Cn ≤ KCn which is clearly not true for any K. So we do need to split the numbers in groups of at least 5 (we need an odd number to have a middle row to have simpler counting.)
6. Modify the SkipList data structure so that finding the kth smallest element can also be done in expected time O(log n).
Solution: Assume an element a has pointers on all levels i such that 0 ≤ i ≤ k; for a forward pointer on level i keep a counter containing the total number of elements between a and the next element with a pointer on level i. Such a pointer is updated whenever an element is added or deleted.
7. Consider Karger’s MinCut algorithm. How many repetitions of the 4-Contract(G) would you need to make to guarantee that MinCut is found with a probability
of 1 − 1 where n is the number of vertices of G. How does the asymptotic n2
run time of the whole algorithm change?
Solution: We have shown that the probability of a success of 4-Contract(G) is at least 1/ log n; if we repeat it K(log n)2 times the probability P of a success is at least
1 K(logn)2 1 lognKlogn P=1− 1−logn =1− 1−logn (1)
≈1−e−Klogn =1−(elogn)−K =1−n−K =1− 1 (2) nK
Thus, to have Karger’s algorithm succeed with a probability of at least 1−1/n2 we have to run it only 2(log n)2 many times, so asymptotically the algorithm remains an O(n2(logn)3) algorithm, just the appropriate constant multiplier has doubled in size.
8. The present day “publish or perish” madness in academia involves counting number of papers researchers have published, as well as the number of citations their papers got.
(a) One might argue that not all citations are equally valuable: a citation in a paper that is itself often cited is more valuable than a citation in a paper that no one cites. Design a PageRank style algorithm which would rank papers according to their “importance”, and then use such an algorithm to rank researchers by their “importance”.
(b) Assume now that you do not have information on the citations in each published paper, but instead you have for every researcher a list of other researchers who have cited him and how many times they cited him. De- sign again a PageRank style algorithm which would rank researchers by their importance.
(a) Construct a directed graph with vertices corresponding to individual pa- pers and with edges from p1 to p2 just in case p1 has a citation of p2. Now apply the PageRank algorithm (which involves handling dangling vertices and adding weak edges between every two papers etc. ). After finding the PageRank of each paper to rank researchers simply add the PageRanks of all of their papers.
(b) Now the vertices of the graph will be the researchers with an edge from R1 to R2 just in case researcher R1 has cited researcher R2. This time the edges have weights proportional to the total number of citations of R2 by R1 (normalised by dividing such a number by the total number of citations R1 has made up to this moment.) Apply again the complete PageRank matrix construction and algorithm.
9. You are watching traffic on a busy road and you notice that on average three out of every four trucks on the road are followed by a car, while only one out of every five cars is followed by a truck. What fraction of vehicles on the road are trucks
Solution: We can assume that the traffic is already(approximately) in a steady state given by the stationary distribution of the corresponding Markov
Process. The states (here they are observations) are “truck” and ”car”; if the previous state was a truck the probability that the next state will be a car is 3/4; thus, the probability that the next state will also be a truck is 1/4. Similarly, if the present state is a car, then the probability that the next state will be a truck is 1/5 and consequently it will be another car with a probability of 4/5. So we are looking for c (the probability that the current observation is a car) and t (the probability that the current state is a truck) which satisfy:
4/5 1/5
ct=ct 3/41/4; c+t=1
The solutions of these three linear equations (one of the first two is redundant) are c = 15/19 and t = 4/19.
10. You are monitoring Sydney summer weather and you noticed that on average seven out of every 10 pleasant weather days are followed by another pleasant wether day and only one out of every 10 pleasant weather days is followed by a day with a summer shower. You also noticed that on average 2 out of every 15 days with a summer shower are followed by another day with a summer shower and that 4 out of every 9 very hot days are followed by a day with a pleasant wether. You also know that on average out of 90 summer days 50 have pleasant wether, 10 have summer showers and 30 are very hot. Set up the equations which can be used to determine what fraction of days with a shower are followed by a very hot day. Note that you are not asked to solve such a system of equations, just to set up all the equations needed to solve the problem.
Solution: This is similar to the car/truck problem. Let x be the fraction of days with a shower followed by a pleasant day and let y be the fraction of very hot days followed by a day with a shower. Then we have to have the following equations satisfied:
7/10 1/10 1 − 7/10 − 1/10 50/90 10/90 30/90 = 50/90 10/90 30/90 x 2/15 1 − x − 2/15
4/9 y 1−4/9−y
which is equivalent to
5/9 1/9 3/9=5/9 1/9 3/9 x 2/15 13/15−x
The solutions to above system are x = 1/6 and y = 11/90. 7
7/10 1/10 2/10 4/9 y 5/9−y
Recall that a matrix consisting of non-negative reals is row-stochastic if in each row all the entries in that row sum up to 1; thus if
s11 s12 s13 ... s1n s21 s22 s23 ... s2n
M=s31 s32 s33 ... s3n
. . . . . . . . . sn1 sn2 sn3 ... snn
thenforall1≤i≤nwehavenj=1sij =1. Assumethatx⊤ = (x1,x2,...,xn) is a vector such that xi ≥ 0 and ni=1 xi = 1. Show that then vector y = x⊤M also has the property that yi ≥ 0 and that ni=1 yi = 1. Thus, if x is a vector of probabilities of states of a Markov chain, then so is vector y.
(b) In computing the Google PageRank iteratively we start with vector (1/N,1/N,...,1/N)⊤ giving each page the same initial rank of 1/N. Prove that after the iteration has stopped, the sum of the PageRanks of all web pages will be equal to 1.
(a) Let y⊤ = x⊤M with ni=1 xi = 1. Note that
yj = xiMi,j = xiMi,j
j=1 j=1 i=1 i=1 j=1 nnn
=xM =x=1. i i,j i
i=1 j=1 i=1
(b) Apply the previous fact to every step of iteration.
12. Below is given the graph of the Internet one millisecond after the Big Bang.
(a) Construct the corresponding Google matrix with α = 7/8.
(b) Explain what property the PageRank satisfies (i.e., how it is related to the corresponding Google matrix).
(c) Find the PageRank of all nodes (you do not need an iterative algorithm to find the PageRank for such a small matrix; you can solve the corre- sponding system of linear equations directly, keeping in mind that the
Figure 1: The Internet 1ms after the Big Bang
PageRanks of all pages can be interpreted as probabilities and thus must sum up to 1)
Step one - Matrix G0:
0 1/4 1/4 1/4 0 0 0
1/4 0 1/4 0 1/4 0 1/4
0 1/3 0 1/3 0 0 1/3
0 0 0 1/2 1/2 0
1/4 0 0 0 0 0 0
0 1/3 0 1/3 0 0
Step two - fixing the dangling node. There are 8 websites so N = 8 and we get
0 0 0 1/3 0 0
1/64 7/32 + 1/64
1/8 7/24 + 1/64 1/8
7/24 + 1/64
7/32 + 1/64 1/64 7/24 + 1/64 1/64 1/8 1/64 1/8 1/64
7/32 + 1/64 7/32 + 1/64 1/64 1/64 1/8 7/24 + 1/64 1/8 7/24 + 1/64
7/32 + 1/64 1/64 7/24 + 1/64 1/64 1/8 1/64 1/8 1/64
1/64 7/32 + 1/64 1/64 7/16 + 1/64 1/8 1/64 1/8 7/24 + 1/64
1/64 1/64 1/64 7/16 + 1/64 1/8
1/64 1/8 1/64
7/32 + 1/64
1/64 1/8
1/64 1/8
0 G1 = 1/8
1/3 1/8 1/3
1/4 1/4 1/4 0 0 0 1/4 0 1/4 0 1/3 0 1/3 0 0
0 0 0 1/8 1/8 1/8 0 1/3 0 1/8 1/8 1/8 0 1/3 0
1/3 1/2 1/2 0
Step 3 - adding the teleportation. Every entry eij in a row i that was not corresponding to a dangling node is replaced by 7/8eij + (1 − 7/8) × 1/8 = 7/8eij + 1/64, so matrix G is
which means that
1/64 15/64 15/64 15/64 1/64 1/64 1/64 15/64
1/64 1/64 1/64 1/8 1/64 1/8
59/192 1/64 59/192 1/64 59/192 1/64 1/64 1/64 Finally, use your favourite linear equations solver to solve
15/64 1/64 15/64 1/64 15/64 1/64 15/64 1/64 59/192 1/64 59/192 1/64 1/64 59/192 1/64 1/64 1/64 1/64 29/64 29/64 1/64
G= 1/8 1/8 1/8 1/8 1/8 1/8 1/8 59/192 1/64 59/192 1/64 1/64 1/64 59/192 1 / 8 1 / 8 1 / 8 1 / 8 1 / 8 1 / 8 1 / 8
1/8 1/8 00 1/8 1/8
1/8 1/8 1/3 0 1/8 1/8
(r(1), r(2), r(3), r(4), r(5), r(6), r(7), r(8)) = (r(1), r(2), r(3), r(4), r(5), r(6), r(7), r(8))G r(1) + r(2) + r(3) + r(4) + r(5) + r(6) + r(7) + r(8) = 1
0 0 0
1/64 7/32 + 1/64 7/24 + 1/64 1/64 1/8 7/24 + 1/64 1/8 1/64
for r(1),...,r(8).
You should get something like this:
r(1) = 0.126617, r(2) = 0.121085, r(3) = 0.154315, r(4) = 0.121085, r(5) = 0.15003, r(6) = 0.101354, r(7) = 0.149437, r(8) = 0.0760767
Thus, the ordering of webpages according the PageRank is: r(3), r(5), r(7), r(1), r(2), r(4), r(6), r(8).
13. Prove that if in an irreducible Markov Chain one state is aperiodic, then all states must be aperiodic. Thus, equivalently, assume you have a directed strongly connected graph G which has one vertex v which satisfies that there is NO number K such that the length of every loop containing v is divisible by K. Show that in this case all vertices have the same property.
Hint: Let u be an aperiodic vertex and v an arbitrary vertex. Since the graph is strongly connected, there is a path p1 from v to u and a path p2 from u back to v. Show that for every integer K you can find a path containing v whose length is not divisible by K. You might want to make several trips starting at v, traversing only p1 and then p2 back to v and just one trip traversing p1 then going through the loop containing u whose length is not divisible by K and then traversing path p2 back to v.
Solution: Let u be an aperiodic vertex and v an arbitrary vertex. Since the graph is strongly connected, there is a path p1 from v to u and a path p2 from u back to v. Assume that v is periodic and so for some integer K every loop containing v has a length divisible by K. Consider now a path starting at v that traverses K − 1 times the loop consisting of p1 and p2, then traverses again p1 then goes around a loop containing u whose length l is not divisible by K and which exists due to aperiodicity of u and finally traverses p2 back to v. The total length of such a lop is
(K − 1) × (length(p1) + length(p2)) + length(p1) + l + length(p2) = K × (length(p1) + length(p2)) + l
which is clearly a number not divisible by K because l is not divisible by K. 11
Alternatively, it is also enough to prove that if a Markov chain has one periodic state then all states must be periodic. Assume that v is periodic with period K and let w be any other state (represented as vertices of the associated graph). Consider an arbitrary loop l containing w. There must also be a path p1 from w to v and a path p2 back from v to w. p1 joined with p2 forms a loop containing v thus length(p1) + length(p2) must be divisible by K. Consider also the loop containing v consisting of the path from v to w, then loop l and finally the path from w to v. its total length must also be divisible by K. By subtracting we get that the length of l must also be divisible by K proving v is also periodic.
14. One of the most common hash functions used is defined as h(x) = x mod p where p is a prime. This function has a drawback that it is not local, in the sense that two numbers can be close to each other but their hash values can befaraway,forexampleifp=31andx1 =30andx2 =31thenh(x1)=30 mod 31 = 30 but h(31) = 31 mod 31 = 0. Can you slightly alter this hash function so that numbers which are close to each other have hash values that are also close to each other?
Solution: Let p be a prime; let h(n) = n mod 2p; then we let
h(n) h(n)=
2p − 1 − h(n)
if h(n)