 # 3 Problems with Approximation Algorithms and Expectation Analysis

## Question

Problem 1
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....
\$33.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

### Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.