This is an old revision of the document!

We have spent some time discussing approaches to solving a number of common recurrences. We shall illustrate the application of divide-and-conquer to problems form a number of different domains. The Problem. We will consider a problem that arises in the analysis of rankings such as couple of websites use a technique known as collaborative filtering, in which they try to match preferences of books, movies, e.t.c with others on the internet. A website can recommend stuff by finding people with similar tastes as you. A problem that websites face is one of comparing two rankings. What is a good way to measure, numerically, how similar two people's rankings are? A natural method would be to label the movies from 1 to n according to your ranking, then order these labels according to the stranger's ranking, and see how many pairs are out of order.