Solve random algorithm problems

1. Random walk on complete graph Kn. Mr. A enjoys random walk on the complete graph Kn. Today he has started random walk from a randomly selected vertex of Kn and is going to walk until he visits k distinct vertices (including the vertex he has started from). Let Tk be the (random) number of steps of today’s walk (step = traversed edge). Tomorrow he will continue random walk untill he visits all the vertices. Let Rk be the (random) number of steps of tomorrow’s walk. Evaluate the expected values ETk and ERk. 2. Randomized 2-SAT algorithm. Statement of the problem. The randomized algorithm. Analysis of the number of steps via random walk (formulate and prove the upper bound on the expected number of steps of a related random walk; apply this upper bound to the randomized 2-SAT algorithm). MonteCarlo algorithm and the upper bound on the probability of its failure 3. Random Quick sort. Pivots are selected uniformly at random and independently of each other. The set to be sorted consists of n distinct numbers. Let us denote the oredered list of them by s1 < s2 < · · · < sn. What is the probability that the numbers si , sj and sr will (all) be compared pairwise? 4. Apply one iteration of the randomized min-cut algorithm to the graph Gi. What is the probability that the cut found is a minimal one? Explain your answer. Parameters are: I = 7, j = 9, k = 14, n =. 43, r = 11