CS297 Proposal

Algorithm to obtain a total order from partial orders for social networks

Chandrika Satyavolu (satyavolu.chandrika@gmail.com)

Advisor: Dr. Chris Pollett

Social Networking can be used to harness human intelligence to solve problems which might be hard to program a computer to do. An example of this is a recaptcha. Captcha is a method that ensures security and prevents spam. The user is asked to complete a simple test (e.g: read and enter the scanned and distorted text displayed) that determines if the user is human. Recaptcha is a similar technique that uses human intelligence to digitize books and enable search through scanned text. In this project, we are going to develop social algorithms for creating total orders based on humanly computed partial orders. Examples of where this might be useful include: (1) In Grading, to construct a total order from partial orders created by the students themselves or the assistants. (2) To rank movies, a total order can be developed from the partial rankings given by viewers. (3) In auction and shopping portals, when searching for an item, the results displayed would be a total order obtained from the partial orders that are humanly created using ratings given to the sellers. In this project we intend to create and test at least three such algorithms generating total orders from humanly generated partial orders. We also intend to look at the usability of different ways for people to select their partial order preferences. For example, to create partial orders for movies, one could ask the user to select movies in the same genre and rank them or provide them with a set of movies in the same genre (after a category search) and ask the user to rank them.

Schedule:

Deliverables:

The following will be done by the end of CS297:

1. Alter the sorting algorithms from the references to obtain the total order from the partial orders.

2. Code a prototype for partial order sorting system.

3. Randomize the algorithm by varying the partial order inputs and observe the variation in the total order output.

4. Analyze complexity of the algorithm.

5. Write up CS 297 Report.

References:

[1] Introduction to Algorithms. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Prentice-Hall, 2nd edition, 2002.
[2] Intelligent Planning - A Decomposition and Abstraction Based Approach. Qiang Yang, Springer-Verlag, 1997.
[3] Artifical Intelligence: A Modern Approach. S. Russell and P. Norvig, Prentice-Hall, 2nd edition, 2002.