CS298 Proposal

A Student Self-Grading System

Chao Liang (csc57chao@yahoo.com)

Advisor: Dr. Chris Pollett

Committee Members: Dr. David Taylor (taylor@cs.sjsu.edu) and Dr. Mark Stamp (stamp@cs.sjsu.edu).

Abstract:

The main purpose of this project is to develop a grading system for homeworks in which both the students and professor share in the grading process. The hope though is to reduce the total number of homeworks the professor needs to grade in order to accurately assign grades to all of the students. To this end in CS297 an algorithm based on Quicksort, which we call VoteSort, was developed. The idea is that each student as well as the professor is given k randomly chosen homeworks from a total pool of n homeworks to rank from worst to best. These partial orders are then combined into a total order by using the VoteSort algorithm. This algorithm operates like Quicksort, but when a comparison of a homework j with the pivot i is needed, the number of times i appeared in one of the partial orders as better than j is used to decide which is bigger. Providing everyone grades accurately, a hand-wavy mathematical analysis suggests that with k around sqrt (n) (so everyone grading 5 homeworks for a class of 25 students), one can accurately determine a total order. Even if this is not the case it should be possible through simulation to determine a grade-spread which is accurate. To make the grades somewhat correspond to what the "correct grade" should have been for the homework two methods will be considered: (1) weighting the professor's permutation of k homeworks more highly in any vote tally, (2) rewarding students for getting comparisons in alignment with majority decisions, especially when those decisions involved many votes and the spread was large. We will try to analyze the weighting of rewards in terms of game theory. The whole system will also be constructed so as to be an easy add-on for Dr. Pollett PHP based grading program.

CS297 Results

• Three scripts were implemented to become more familiar with the web technologies needed for the online grading program as well as voting algorithms. One was to get search results from a database, using PHP. One was to use Ajax to implement a progress meter. The last one was to implement the Byzantine agreement algorithm using web browsers as the voters.
• Concepts, scenarios, and applications of game theory were studied [Myerson91]. These ideas will be used in the grading system to ensure students try to grade as accurately as possible.
• Developed an algorithm VoteSort to generate a total order from partial orders.

Proposed Schedule

Key Deliverables:

• Software
  • Complete implementation of VoteSort algorithm to generate a total order from all the student partial orders.
  • Variants of VoteSort with different professor weightings and reward values for students will be subclassed.
  • Test cases. These include cases to test: (a) When the students are assumed to grade perfectly how well the partial order can be recovered. (b) If the students vote randomly or dishonestly under different settings of the VoteSort algorithm how is the ultimate grade affected.
  • A user-friendly way to assign and collect the student homework grading permutations and to integrate this with the core components of the VoteSort algorithm and with Dr. Pollett's online grading system.
• Report
  • CS298 report which will include our experimental results as well as an attempt to mathematically analyze VoteSort and it variants.
  • Documentation on how to use the VoteSort algorithm within the context of Dr. Pollett's grading program.

Innovations and Challenges

• The VoteSort algorithm that generates a total order from partial orders, is innovative and new. Further, it solves a problem that is similar to -- but not the same as -- the timestamp ordering problem in concurrency control as well as to problems in bioinformatics of constructing a total DNA sequence from a collection of subsequences, so it might have other applications.
• Analyzing a randomized algorithm such as VoteSort is nontrivial. Further some of the test cases needed to study the problem require considerable programming.
• Integrating the Vote gathering process and VoteSort into Dr. Pollett's grading system in a way which is reasonably user friendly to students is challenging.

References:

[Blythe92] An Analysis of Search Techniques for a Totally-ordered Nonlinear planner. Jim Blythe and Manuela Veloso. Carnegie Mellon University. 1992.

[Jonsson99] Towards Efficient Universal Planning - A Randomized Approach. Peter Jonsson, Patrik Haslum and Christer Backstrom.Department of Computer and Information Science. Linkoping University of Sweden. 1999.

[Kambhampati96] Unifying Classical Planning Approaches. Subbarao Kambhampati and Biplav Srivastava. Department of Computer Science and Engineering of Arizona State University. 1996.

[Kearns02] A Tutorial on Computational Game Theory. Michael Kearns Computer and Information Science of University of Pennsylvania. 2002.

[Mahajan04] Experiences Applying Game Theory to System Design. Ratul Mahajan, Maya Rodrig, David Wetherall, and John Zahorjan. University of Washington. 2004.

[Minton94] Total-Order and Partial-Order Planning:A Comparative Analysis. Steven Minton, John Bresina, and Mark Drummond. Recom Technologies. 1994.

[Myerson91] Game Theory: Analysis of Conflict. Roger B. Myerson. Harvard University Press. 1991.

[Nielsen00] Designing Web Usability. Jakob Nielsen. New Riders Publishing. 2000.