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
Week 1-2:
Aug 23 - Sep 2 | Implement VoteSort algorithm to generate a total order. |
Week 3-4:
Sep 3 - Sep 16 | Further research on game theory, and analyze how it can be used in the system to assign reward values fairly. |
Week 5-6:
Sep 17 - Sep 30 | Implement variants of VoteSort with different professor weightings and reward values. |
Week 7:
Oct 1 - Oct 7 | Implement test cases to analyze how student grading behaviors
affect the outcomes. |
Week 8-9:
Oct 8 - Oct 21 | Design and implement a user-friendly interface to assign and
collect student papers and student and professor permutations. Integrate this interface
with VoteSort algorithm and Dr Pollett's online grading system. |
Week 10-11:
Oct 22 - Nov 4 | Write CS298 report. |
Week 12:
Nov 5 - Nov 11 | Test, debug, and prepare draft for committee. |
Week 13-14:
Nov 12 - Nov 25 | Finalize report. |
Week 15:
Nov 26 - Dec 2 | Prepare slides for oral presentation. |
Week 16:
Dec 3 - Dec 9 | Oral defense. |
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.
|