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 PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use 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....

By purchasing this solution you'll be able to access the following files:

50% discount

$29.25 $14.63
for this solution

or FREE if you
register a new account!

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.

Upload a file
Continue without uploading

We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats