## Question

In a list of distinct numbers a1,…an , we say that the elements ai and aj are inverted if i<j but ai>aj. Suppose that all orderings of a1,…an are equally probable under some probability distribution (In other words we shuffled a set of numbers perfectly to obtain the order a1,…,an.) What is the expected number of inversions?

Problem 2

Consider the following greedy algorithm for finding a matching.

Initialize S to an empty set of edges

While there is an edge where both vertices are unmatched by S

Add the above edge to S

Return S

What is the running time of this algorithm?

Give an example of a graph where the algorithm does not find the maximum matching.

Show that the matching found by the algorithm always has at least half as many edges as a maximum matching.

(Bonus) Now consider a similar algorithm for finding a maximum weight matching in an edge-weighted graph: Greedily add the heaviest edge possible to the current matching; stop when no further edge can be added. Show that this algorithm finds a matching whose weight is at least half the optimum.

Problem 3

Consider the following factor 2 approximation algorithm for the minimum cardinality vertex cover problem. Find a depth first search tree in the given graph, G, and output the set, say S, of all the non-leaf vertices of this tree. Show that S is indeed a vertex cover for G and |S|≤2⋅OPT.

Hint: Use the tree to construct a matching that includes all the vertices in S.

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

For any pair (i,j) of two elements from the array a1,a2,….an are two possibilities: either i<j and ai<aj or i<j and ai>aj (hence inversion). So the probability for each pair to be an inversion is ½.But the number of pairs in the array is nC2= n(n-1)/2. So intuitively the total amount of expected inversions would be equal to ½* n(n-1)/2= n(n-1)/4.

However it is necessary to attempt giving a more rigorous proof based on the random probabilities of the inversions after shuffling the values.

We randomly take a pair (i,j) with i<j such that ai>aj (hence it is an inversion).

The indicator for the random variable of the event of being an inversion is ½ because there are only two equally-likely possibilities (as we proved above). So the expected value E[Indicator_i,j]=1/2.

The requested expected number of inversions from the entire array will be equal to the sum of all Indicator_i,j....