The following parts (a) and (b) are independent, but both refer to inversion in
ID: 3564841 • Letter: T
Question
The following parts (a) and (b) are independent, but both refer to inversion in a sequence. Suppose we exchange elements a[i] and a[j] (j>i) which were originally out of order. For example if a= [2,8,3,7,1,5,6] and if we exchange second (i=2) and sixth (j=6) elements, we have [2,5,3,7,1,8,6] and now 5 and 8 are ordered and therefore the array has fewer inversions, i.e. several inversions are removed. In terms of i and j, what is the maximum number of inversions that can be removed if we exchange elements a[i] and a[j]? This problem arises in ranking which has many applications especially, in a web technique called collaborative filtering. Here they try to match your preference (for books, movies, restaurants) with those of other people on the internet. A main problem in collaborative ranking is comparing two rankings. You rank a list of n movies, say if n =4 you rank them as {1,2,3,4} and another person ranks them for example as {a1,a2,a3,a4}={3,1,4,2}, that is the movie you ranked 1, the other person ranked 4, and so on. A natural way to quantify similarity between two rankings is to count the number of inversions in the second sequence. Given a list {a1, a2,..., an}, propose an algorithm in pseudo-code to count the number of inversions with 0(n Ig n) complexity.Explanation / Answer
Inversion Count for an array indicates
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.