$($for Instructor$)$ "Recommender systems" have become popular in recent years as a way of

identifying items such as books $($or music, movies, restaurants, and so forth$)$ that an online user

might like based on that user's past choices and how those choices might align with other users.

So the question is$,$ how to determine the "similarity" between two sets of rankings. One way is

to have user X rank a set of n books from $1$ to n and then compare that ranking with the

ranking of User Y on the same set of books.

More specifically, let $a_1,a_2,$dots,$a_n$ be some arbitrary sequence of n distinct numbers. $($In our

example case, these numbers are labels for book titles; these would be in arbitrary order in

User Y$\text{'}$s ranking.$)$ Then figure out how to measure the difference between this sequence and

one that puts the same $n$ values in increasing order $($User $x^{\text{'}}s$ ranking$).$ In a given sequence, if

$a_i>a_{j}4,6,1,7,3(4,1),(4,3),(6,1),(6,3),(7,3)a_1,a_2,$dots,$a_{n}n(nlgn)i$ but $a_i>a_j,$ that $is$ called $an$ inversion. The number $of$ inversions $in$ the arbitrary sequence

$is0if$ that sequence happens $tobein$ increasing order and becomes larger $as$ that sequence $is$

more "scrambled." For example, the sequence $4,6,1,7,3$ has $5$ inversions:

$(4,1),(4,3),(6,1),(6,3),(7,3)$

$a.$ Describe the characteristics $of$ a sequence $a_1,a_2,$dots,$a_n$ that has the maximum number $of$

inversions; what $is$ the order $of$ magnitude $of$ that number?

$b.$ Describe a brute$-$force algorithm for counting the number $of$ inversions $inan$ arbitrary

sequence $of$ length $n$ and give its order $of$ magnitude.

$c.$ Describe $(explain$ the divide, conquer, and combine steps$)$ a divide and conquer

algorithm $to$ count the number $of$ inversions $inann-$element sequence and prove that $itis$

$(nlgn).(Hint$: think Mergesort$).$