This is the grading rubric for problem-set hand-ins for CS 252. Please also see the Homework Guidelines and Feedback Key for additional information regarding the evaluation of problem sets.

This rubric is focused mostly on algorithm-design problems. For such problems, the required components of a solution (referred to below as the “components”) are:

• A statement of the algorithm
• A claim of correctness and a proof of this claim
• A claim of running time and a proof of this claim

Rather than asking for an algorithm, some questions may instead ask for a counterexample or proof of a given statement, or may be multi-part; in these cases the required components should be clear from context.

## Calculation of Total Score

Each problem is scored on a 23-point qualitative scale. The number of points for each rating is indicated in parentheses in the table below. The total score is computed as the sum of the Correctness, Style, Clarity, Precision, and Conciseness scores (with a maximum sum of 23 points), multiplied by the Completeness score (which is a fraction out of 23), and rounded up. Remember that the total score, as a percentage, does not map directly onto a letter grade; these are qualitative scores.

Each question receives only one score per category; this means that multi-part questions are evaluated as a whole. In multi-part questions, the scores will be roughly the average of the scores that the individual parts would receive: that is, great work in some parts can offset so-so work in another.

The grading follows a principle of avoiding “double jeopardy”; that is, errors count against the rating only for one category, unless they're egregious. (For example, style issues may affect clarity, but unless something is seriously going wrong, this will be noted only in the rating for either style or clarity.) When an error affects multiple categories, it factors into the rating only for the category that it affects most severely. In particular, if a section is incomplete, this affects only the Completeness rating, and does not affect the rating for the other criteria at all.

## Rubric

Criterion Great Good So-So Poor
Completeness All components are present and complete. (23/23) All components are present, but some are somewhat incomplete. (21/23) One or more components are missing, or all components are severely incomplete. (16/23) No genuine attempt at a complete solution. (8/23)
Correctness All components are completely correct. (9) At least one component contains a minor error. (7) At least one component contains a major error. (4) Multiple major errors, or an entirely incorrect response. (0)
Style A professional, polished tone and format are maintained throughout the solution. (3) Minor issues of tone, voice, spelling, punctuation, or formatting. (2) Major tone or presentation issues. (1) Exceedingly terse, sloppy, or otherwise unpolished writing. (0)
Clarity All components are clear, organized, and easy to follow. (4) Occasional or minor issues of clarity, causing confusion that can be overcome by careful reading and charitable interpretation by the reader. (3) Truly confusing writing that can only be interpreted with significant effort. (1) Exceedingly confusing writing. (0)
Precision No meaningful ambiguity. (4) Occasional or minor issues of precision, causing meaningful ambiguity that can be overcome by charitable interpretation by the reader. (3) Major precision errors that cause meaningful ambiguity in the interpretation of the solution, which can only be resolved with difficulty (if at all). (1) Severely underspecified instructions, definitions, claims, or arguments. (0)
Conciseness Direct and to the point, without sacrificing appropriate clarity or precision. (3) Occasional extraneous writing. (2) Very long-winded, redundant, or extraneous writing. (1) Exceedingly longer writing than is necessary for the clear, precise expression of the ideas in the solution. (0)

## Notes on Great Writeups

A little further elaboration on the characteristics of “great” writeups:

Completeness Sometimes the running time is relatively obvious, and in this case a thorough proof of running time is not necessary. A couple typos are acceptable, as is the occasional non-distracting lighter-toned aside. In a clear write-up, each component of the solution is organized and easy to follow. The different components are easily distinguished, and the purpose of each bit of writing is apparent. Variables in clear pseudocode are easy to understand, because of preceding explanatory prose, comments, and/or self-explanatory variable names. A precise write-up leaves no meaningful ambiguity in the interpretation of the algorithm or the arguments about its properties. Note, however, that the audience for each solution is not a robot, but instead a well-informed, but skeptical, human reader. Many forms of presentation that would be “ambiguous” or “underspecified” if we were writing code to be run by a computer are nevertheless acceptable in these solutions. So long as the solution is comprehensible and specific enough that the reader could easily write a correct implementation of the instructions, or could easily flesh out the pedantic details of the argument, it is just fine.

## Descriptions of Errors

Criterion Minor Major
Correctness Incorrect values for constants; minor unconsidered edge cases; minor gaps in logic. False-positive or false-negative outputs; large portions of the input space that are not handled correctly by the algorithm; running time that does not meet the requirements of the problem statement; major gaps in logic.
Style Provisional or passive voicing; smarmy or pompous voicing; occasional distracting lapses in professionalism. Consistent errors of capitalization or punctuation; consistently un-professional tone; major errors in formatting.
Clarity Disorganized or hard-to-follow arguments or explanations; confusing variable names or pseudocode style; obscure or needlessly complicated pseudocode structure. Severe instances of issues described to the left, causing confusion that can only be overcome with significant effort on the part of the reader.
Precision

In algorithm statements, meaningful lack of specificity regarding: order of operations, definitions of variables or terms, data-structure implementation or initialization, implementation of non-trivial steps described in prose, minor off-by-one errors, non-catastrophic out-of-bounds errors, and similar logic issues. Also: the use of programming constructs that are language-specific, or pseudocode that otherwise leans too heavily on high-level convenience functions built into some languages.

In arguments: imprecise definitions or claims.

In running times: missing terms that ought to be included, or inclusion of dominated terms that ought to be left out.

Severe instances of issues described to the left, causing unresolvable ambiguity.

Use of an abstract data type without specifying the implementation, when multiple reasonable implementations exist whose performance characteristics differ.

Conciseness Prose that describes the design process for the solution rather than the idea of the solution itself; prose that is redundant with existing pseudocode and that does not serve clarity; prose that could be replaced with significantly more concise pseudocode; pseudocode that could be replaced with shorter prose without sacrificing clarity or precision; the repeated use of words where mathematical notation would serve just as well; or pedantic inclusion of unnecessary details in description or argument. Severe instances of issues mentioned to the left, resulting in a write-up that is much longer than necessary.