US5259766A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for interactive computer science testing, anaylsis and feedback
Assignee: Educational Testing Service
•
Filing: 1991-12-13
•
Granted: 1993-11-09
•
Expires: 2011-12-13
Abstract
Abstract Disclosed is a method and system for administering to a student a problem in computer science for testing, analysis and feedback. The student is provided with an item pool of predetermined test problems to be selected by the student. The student inputs a solution in response to the problem selected, and the solution program is converted, by lexing and parsing, into an abstract syntax tree representation. Predetermined knowledge base patterns are selected from a knowledge base and compared against portions of the abstract syntax tree. Messages and a score are provided to the student which indicate the correctness or incorrectness of the solution program, as determined by the knowledge base patterns which were matched against the portions of the abstract syntax tree. The present method and system is especially qualified to analyze free-response test items.
Inventors
- 👤 Warren Sack
- 👤 Randy E. Bennett
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 13:22
CPC Classifications
G; G09; G09B; G09B19/00; G09B19/0053; G09B7/00; G09B7/02; G09B7/04
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
152 words
A method of evaluating a solution program input to a computer in response to a computer science problem in which the solution program may contain a plurality of errors, said method comprising the steps of: a) converting the solution program in response t the computer science problem into an abstract syntax tree representation; b) comparing a first predetermined pattern against a first portion of the abstract syntax tree, said first portion representing certain nodes of the abstract syntax tree; c) repeating step (b) against a plurality of portions of the abstract syntax tree until the first predetermined pattern matches a portion of the abstract syntax tree; wherein the first predetermined pattern has been specified so as to match a range of abstract syntax tree portion; and d) providing information correlated to the first predetermined pattern so matched; wherein said information is a textual message indicative of the correctness of the solution program.
Claim 2
Independent Claim
152 words
A method of evaluating a solution program input to a computer in response to a computer science problem in which the solution program may contain a plurality of errors, said method comprising the steps of: a) converting the solution program in response t the computer science problem into an abstract syntax tree representation; b) comparing a first predetermined pattern against a first portion of the abstract syntax tree, said first portion representing certain nodes of the abstract syntax tree; c) repeating step (b) against a plurality of portions of the abstract syntax tree until the first predetermined pattern matches a portion of the abstract syntax tree; wherein the first predetermined pattern has been specified so as to match a range of abstract syntax tree portion; and d) providing information correlated to the first predetermined pattern so matched; wherein said information is a textual message indicative of the correctness of the solution program.
Claim 3
Dependent Claim
96 words
The method of claim 1 further comprising the steps of: e) comparing a subsequent predetermined pattern against the first pattern the first portion of the abstract syntax tree; f) repeating step (e) against a plurality of portions of the abstract syntax tree until the subsequent predetermined pattern matches a portion of the abstract syntax tree; g) providing information correlated to the subsequent predetermined pattern so matched; wherein said information is a textual message indicative of the correctness of the solution program; and h) repeating steps (e), (f) and (g) for a plurality of sequent predetermined patterns.
Claim 4
Dependent Claim
15 words
The method of claim 2 in which the information provided further comprises a weighted score.
Claim 5
Dependent Claim
55 words
The method of claim 3 in which the converting step comprises the steps of: (i) lexing the solution program into a list of tokens, each token being representative of a part of the solution program and its location within the solution program and (ii) parsing the list of tokens into an abstract syntax tree representation.
Claim 6
Dependent Claim
18 words
The method of claim 4 wherein the lexing step and the parsing step are implemented in Prolog programs.
Claim 7
Dependent Claim
22 words
The method of claim 5 wherein the Prolog programs that implement the lexing step and parsing step comprises LEXER.ARI and PARSER.ARI programs.
Claim 8
Dependent Claim
22 words
The method of claim 6 in which the Prolog program that implements steps (b) and (c) of the method comprises ENGINE.ARI program.
Claim 9
Dependent Claim
15 words
The method of claim 1 in which the computer science problem is an open-ended problem.
Claim 10
Dependent Claim
15 words
The method of claim 1 in which the computer science problem is a completion problem.
Claim 11
Dependent Claim
16 words
The method of claim 1 in which the computer science problem is a faulty solution problem.
Claim 12
Independent Claim
202 words
A method of administering to a student a problem in computer science for analysis and feedback comprising the steps of: a) providing an item pool to the student, said item pool comprising a plurality of predetermined test problems in computer science to be selected by the student; b) recording the student's solution program to a particular test problem selected; c) lexing the solution program into a list of tokens, each token being representative of a part of the solution program and its location within the solution program; d) parsing the list of tokens into an abstract syntax tree representation; e) comparing a predetermined pattern against a first portion of the abstract syntax tree; f) repeating the comparison step with a plurality of portions of the abstract syntax tree until the predetermined pattern matches a portion of the abstract syntax tree; g) repeating steps (e) and (f) for a plurality of predetermined patterns; h) providing to the student text messages correlated to the predetermined patterns so matched; whereby the student is automatically provided with information embodied in the text messages which is indicative of the correctness or incorrectness of the solution text entered by the student in response to the test problem selected.
Claim 13
Independent Claim
202 words
A method of administering to a student a problem in computer science for analysis and feedback comprising the steps of: a) providing an item pool to the student, said item pool comprising a plurality of predetermined test problems in computer science to be selected by the student; b) recording the student's solution program to a particular test problem selected; c) lexing the solution program into a list of tokens, each token being representative of a part of the solution program and its location within the solution program; d) parsing the list of tokens into an abstract syntax tree representation; e) comparing a predetermined pattern against a first portion of the abstract syntax tree; f) repeating the comparison step with a plurality of portions of the abstract syntax tree until the predetermined pattern matches a portion of the abstract syntax tree; g) repeating steps (e) and (f) for a plurality of predetermined patterns; h) providing to the student text messages correlated to the predetermined patterns so matched; whereby the student is automatically provided with information embodied in the text messages which is indicative of the correctness or incorrectness of the solution text entered by the student in response to the test problem selected.
Claim 14
Independent Claim
200 words
A method of administering an examination in computer science to a student comprising the steps of: a) providing to the student a predetermined test problem in computer science from an item pool comprising a plurality of different predetermined test problems; b) recording the student's solution program in computer science to the predetermined test problem so provided; c) lexing the solution program into a list of tokens, each token being representative of a part of the solution program and its location within the solution program; d) parsing the list of tokens into an abstract syntax tree representation; e) comparing a predetermined pattern against a first portion of the abstract syntax tree; f) repeating the comparison step with a plurality of portions of the abstract syntax tree until the predetermined pattern matches a portion of the abstract syntax tree; g) repeating steps (e) and (f) for a plurality of predetermined patterns; and h) storing a score correlated to the predetermined patterns so matched; whereby the student's solution program to the predetermined test problem is automatically evaluated and scored, the score being indicative of the correctness or incorrectness of the solution text entered by the student in response to the test problem provided.
Claim 15
Independent Claim
200 words
A method of administering an examination in computer science to a student comprising the steps of: a) providing to the student a predetermined test problem in computer science from an item pool comprising a plurality of different predetermined test problems; b) recording the student's solution program in computer science to the predetermined test problem so provided; c) lexing the solution program into a list of tokens, each token being representative of a part of the solution program and its location within the solution program; d) parsing the list of tokens into an abstract syntax tree representation; e) comparing a predetermined pattern against a first portion of the abstract syntax tree; f) repeating the comparison step with a plurality of portions of the abstract syntax tree until the predetermined pattern matches a portion of the abstract syntax tree; g) repeating steps (e) and (f) for a plurality of predetermined patterns; and h) storing a score correlated to the predetermined patterns so matched; whereby the student's solution program to the predetermined test problem is automatically evaluated and scored, the score being indicative of the correctness or incorrectness of the solution text entered by the student in response to the test problem provided.
Claim 16
Dependent Claim
63 words
The method of claim 12 further comprising the steps of: i) eliminating from the item pool the predetermined test problem already provided to the student; j) repeating steps (a) through (i) a predetermined number of times; k) storing a cumulative score indicative of all the scores stored in step (h); whereby the cumulative score is indicative of the student's ability in computer science.
Claim 17
Dependent Claim
201 words
A computer system for administering a problem for analysis and feedback in a computer science programming language to a student, said system comprising: a) a user interface comprising i) an item pool comprising a plurality of predetermined test problems in computer science to be selected by the student; ii) output means for providing to the student the particular test problem selected; and iii) input means for providing communications from the student to the system; iv) editor means for recording to student's solution program in computer science to the particular test problem selected; b) a knowledge base comprising a set of predetermined knowledge base patterns; c) an analytic component comprising i) means for converting the student's solution program into an abstract syntax tree; ii) means for comparing each of the predetermined knowledge base patterns against portions of the abstract syntax tree until matched successfully; and d) means for providing to the output means of the user interface a text message correlated to the knowledge base patterns so matched; whereby the student is automatically provided with information embodies in the text message which is indicative of the correctness of the solution text entered by the student in response to the test problem selected.
Claim 18
Dependent Claim
201 words
A computer system for administering a problem for analysis and feedback in a computer science programming language to a student, said system comprising: a) a user interface comprising i) an item pool comprising a plurality of predetermined test problems in computer science to be selected by the student; ii) output means for providing to the student the particular test problem selected; and iii) input means for providing communications from the student to the system; iv) editor means for recording to student's solution program in computer science to the particular test problem selected; b) a knowledge base comprising a set of predetermined knowledge base patterns; c) an analytic component comprising i) means for converting the student's solution program into an abstract syntax tree; ii) means for comparing each of the predetermined knowledge base patterns against portions of the abstract syntax tree until matched successfully; and d) means for providing to the output means of the user interface a text message correlated to the knowledge base patterns so matched; whereby the student is automatically provided with information embodies in the text message which is indicative of the correctness of the solution text entered by the student in response to the test problem selected.
Claim 19
Dependent Claim
70 words
The computer system of claim 14 in which the converting means comprises: A) means for system of claim 14 in which the converting means comprises: A) means for lexing the student's solution program into a list of tokens, each token being representative of a part of the solution program and its location within the solution program; and B) means for parsing the list of tokens into an abstract syntax tree.
Claim 20
Dependent Claim
22 words
The computer system of claim 15 including means for implementing Prolog programs; wherein the Prolog programs comprises LEXER.ARI, PARSER.ARI and ENGINE.ARI programs.
Claim 21
Dependent Claim
39 words
The computer system of claim 16 in which the means for lexing is implemented by the LEXER.ARI program, the means for parsing is implemented by the PARSER.ARI program, and the means for comparing is implemented by the ENGINE.ARI program.
Claim 22
Dependent Claim
158 words
An expert system for evaluating a solution program into to a computer in response to a computer science problem comprising: a) interface means for providing communication to and from a user; b) lexing means for converting said solution program into a list of tokens, each of said tokens being representative of a part of the solution program and its location within the solution program; c) parsing means for converting the list of tokens produced by the lexing means into an abstract syntax tree representation of the solution program; d) a knowledge base comprising a plurality of predetermined knowledge base patterns wherein each of said knowledge base patterns represent a certain part of a model solution program; e) an inference engine comprising means for comparing each of said knowledge base patterns against portions of the abstract syntax tree until successfully matched; and f) means for providing to the interface output messages correlated to the knowledge base patterns successfully matched.
Claim 23
Dependent Claim
158 words
An expert system for evaluating a solution program into to a computer in response to a computer science problem comprising: a) interface means for providing communication to and from a user; b) lexing means for converting said solution program into a list of tokens, each of said tokens being representative of a part of the solution program and its location within the solution program; c) parsing means for converting the list of tokens produced by the lexing means into an abstract syntax tree representation of the solution program; d) a knowledge base comprising a plurality of predetermined knowledge base patterns wherein each of said knowledge base patterns represent a certain part of a model solution program; e) an inference engine comprising means for comparing each of said knowledge base patterns against portions of the abstract syntax tree until successfully matched; and f) means for providing to the interface output messages correlated to the knowledge base patterns successfully matched.
Claim 24
Dependent Claim
50 words
The expert system of claim 18 including means for implementing Prolog programs; wherein the Prolog programs comprise LEXER.ARI, PARSER.ARI and ENGINE.ARI programs; and wherein the lexing means is implemented by the LEXER.ARI, the parsing means is implemented by the PARSER.ARI, and the inference engine is implemented by the ENGINE.ARI program.
Claim 25
Independent Claim
148 words
A method for interactively compiling knowledge base patterns of computer science programs for matching against portions of abstract syntax tree representations of model solution programs in response to the computer science problems, said method comprising the steps of: a) lexing a model program into a list of tokens, each of said tokens being representative of a part of the model program and its location within the model program; b) parsing the list of tokens into an abstract syntax tree representation of the model program; c) querying a user to select the part of the model program against which the knowledge base pattern will be used to compare; and d) generating a knowledge base pattern in accordance with the user's selection such that said knowledge base pattern will match against a portion of the abstract syntax tree correlated to the part of the model program selected by the user.
Claim 26
Independent Claim
148 words
A method for interactively compiling knowledge base patterns of computer science programs for matching against portions of abstract syntax tree representations of model solution programs in response to the computer science problems, said method comprising the steps of: a) lexing a model program into a list of tokens, each of said tokens being representative of a part of the model program and its location within the model program; b) parsing the list of tokens into an abstract syntax tree representation of the model program; c) querying a user to select the part of the model program against which the knowledge base pattern will be used to compare; and d) generating a knowledge base pattern in accordance with the user's selection such that said knowledge base pattern will match against a portion of the abstract syntax tree correlated to the part of the model program selected by the user.
Claim 27
Dependent Claim
28 words
The method of claim 20 further comprising the steps of allowing the user to specify node relations of the knowledge base pattern in accordance with desired match criteria.
Claim 28
Independent Claim
216 words
A method of administering to a student problems in computer science for analysis and feedback comprising the steps of: a) providing an item pool to the student, said item pool comprising a plurality of predetermined test problems in computer science to be selected by the student; b) recording the student's solution program to a particular test problem selected; c) lexing the solution program into a list of tokens, each token being representative of a part of the solution program and its location within the solution program; d) parsing the list of tokens into an abstract syntax tree representation; e) comparing a predetermined pattern against a first portion of the abstract syntax tree; f) repeating the comparison step with a plurality of portions of the abstract syntax tree until the predetermined pattern matches a portion of the abstract syntax tree; g) repeating steps (e) and (f) for a plurality of predetermined patterns; h) providing to the student text messages correlated to the predetermined patterns so matched; and i) storing a score correlated to the predetermined patterns so matched; whereby the student is automatically provided with a score and information embodied in the text messages which is indicative of the correctness or incorrectness of the solution text entered by the student in response to the test problem selected.
Claim 29
Independent Claim
216 words
A method of administering to a student problems in computer science for analysis and feedback comprising the steps of: a) providing an item pool to the student, said item pool comprising a plurality of predetermined test problems in computer science to be selected by the student; b) recording the student's solution program to a particular test problem selected; c) lexing the solution program into a list of tokens, each token being representative of a part of the solution program and its location within the solution program; d) parsing the list of tokens into an abstract syntax tree representation; e) comparing a predetermined pattern against a first portion of the abstract syntax tree; f) repeating the comparison step with a plurality of portions of the abstract syntax tree until the predetermined pattern matches a portion of the abstract syntax tree; g) repeating steps (e) and (f) for a plurality of predetermined patterns; h) providing to the student text messages correlated to the predetermined patterns so matched; and i) storing a score correlated to the predetermined patterns so matched; whereby the student is automatically provided with a score and information embodied in the text messages which is indicative of the correctness or incorrectness of the solution text entered by the student in response to the test problem selected.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-11-08 | 1997-05-10 | 1997-11-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-11-08 | 2001-05-10 | 2001-11-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-11-08 | 2005-05-10 | 2005-11-09 | $7700.00 | Window Closed / Lapsed |