COMP280: Homework Page

Spring 2005

• Mastery of the material is only part of the grading criteria; conveying your solutions clearly and succinctly are also part of what this class is teaching.
• Homework not retrieved in class will be placed in Duncan 3142.
• You can check your grades on-line at webct.owlnet.rice.edu. Please inform us promptly of any discrepancy.
• See further guidelines below, on writing up good homeworks.

• hw01, propositions, truth-tables, and boolean algebra.
  Due 2005.Jan.25 (Tue) in class.
  (Note that there are two minor exercises on the opening page, and a link from there to the remaining problems.)
  hw01 soln [pdf].

• hw02 Reasoning with inference rules; a few interpretations.
  Due 2005.Feb.01 (Tue) in class.
  hw02 soln [pdf].

• The first eight problems only, from
  hw03 First-order formulas and interpretations.
  Due 2005.Feb.08 (Tue) in class.
  hw03 soln [pdf].

• hw04: The remaining problems [9-15], from the handout labeled "hwC" (perhaps misleadingly). First-order algebra and inference rules.
  Due 2005.Feb.15 (Tue) in class.
  hw04 soln [pdf].

• hw05, Sets.
  Due 2004.Feb.22 (Tue).
  hw05 solution (ps, pdf)

• hw06, Functions, Summations, Cardinality.
  Due 2005.Mar.01 (Tue).
  hw06 solution (ps, pdf)

• hw07, Inductions (mathematical, strong, and structural)
  Due 2005.Mar.22.
  hw07 solution (ps, pdf)

• hw08, Program Correctness
  Due 2005.Mar.29 (Tue).
  hw08 solution

• hw09, big-Oh, Recurrence Relations
  Due 2005.Apr.05 (Tue).
  hw09 solution

• hw10, Modular Arithmetic
  Due 2005.Apr.19 (Tue).
  hw10 solution

• hw11, counting, FSM.
  Due 2005.Apr.26 (Tue)
  hw11 solution

• extra-credit homework.
  Due 2005.May.11 (Wed) 17:00.

Homework Guidelines

Your Responsibilities

• Write your name and owlnet userid (e.g. "ian@") and class/assignment-number on the first page of each assignment.
• Staple all your pages together. (-10% otherwise) There is no stapler in the classroom.
• Make sure your solutions are readable. Clearly mark which question each solution corresponds to, and don't turn in scratch work. The graders will not grade illegible or poorly labeled work, and you will get a zero.
• Homeworks is to be turned in in-class on the due-date.
  Late policy & turn-in as per class-info sheet.
• You may either hand-write or computer-format your assignments. (In either case, hardcopy is turned in.)
  • If you type them up, we highly recommend using a program with good support for mathematical symbols. Recommended: lyx (available on owlnet -- a wysiwyg inteface to LaTeX), or Mathematica).
  • If you have particularly scratchy handwriting (like Ian), we encourage you to type in your solutions! Be warned though, that while it's a valuable skill which also gives you sharp-looking homeworks, it often takes more time than expected. Just carefully re-copying messy solutions is the most time-effective way to go.
  • If hand-writing solutions, consider doing one problem per page for all but the simplest problems. That way, if you suddenly realize you need to rewrite a problem, you can just swap out a page of the assignment rather than scribble out sections, have problems out of order, and otherwise do things to confuse or annoy the graders.
  • If you have an electronic version of your file, we encourage you to keep a copy in your owlnet personal ~/comp280 directory (with a pre-due-date timestamp, preferably) -- this lets labbies look at your hw later, in case of lost hardcopy or other glitches.
• You are encouraged (not required) to re-state the problem you are solving, when convenient. You'll find that in the future, doing this will make-or-break whether you'll ever look back at your work.
• In most cases, use complete, grammatically correct English sentences. Always spell correctly. (A proof which graders have trouble understanding, is as useless as a program that doesn't compile!) Points taken off, if the reader has to re-scan your paper just to try to understand what words you're using.
• If a problem asks for a yes/no answer, or a single number, then their solution should preferably start with that one word/number (with explanation following), or (second-best) have the answer clearly circled at the end of explanation.
• Use standard notation and terms.
  • For example, once we have covered one-to-one functions in class, "… because f is one-to-one" is both clearer and more concise than "… because f doesn't map two things to the same thing."
  • Avoid notation with no standard meaning (strange arrows, etc) -- the labbies are not always good at divining what you actually meant.
  • In particular, use "=" when you mean equality (rather than "~" or "→").
  • e.g. write "T"/"F" for booleans rather than the numbers 0/1.
• Use spacing and indentation to reflect the structure of your answers (esp. true for proofs and programs). Particular examples:
  • Clearly state your proof method ("proof by contradiction:", "proof by [regular/strong/structural] induction")
  • If proving "A iff B" by showing each direction separately, clearly label those two sub-sections.
  • Include reminders of where you are in the proof ("Now we show the inductive hypothesis P(k) ⇒ P(k+1) -- that is, Sum_{i=1}^k (i) = k(k+1)/2 ⇒ ...")
  • Mention when you are using a definition: ("x in the set A-B means (by def'n of set-difference) that x ∈ A and x ∉ B. ...")
  • For more involved proofs, start with a quick outline, to convey your line of reasoning.
• Extra credit (if any) problems are graded more strictly than normal problems.

specific instructions for proofs by induction

• Clearly state what your indexed statement P(n) is.
  (Remember that P(n) will be an entire statement, not just a number or an expression.)
• Don't have unbound (undeclared) variables: ``We now show P(k)→P(k+1)'' doesn't say which k you are talking about; you want to show it ``∀k∈N''. Similarly, once you define P(n), don't say ``We now show P(n) by induction:'', but rather ``We now show ∀n∈N. P(n) by induction:''.
• Have the base case and inductive case clearly bulleted.
• When you use the inductive hypothesis, say so.
• [Repeating from earlier:]
  Use "=" to indicate two values are equal. To assert a relation between two statements, use "⇒" or "⇔". Between logic statements, it's idiomatic to instead use "|=" (⊧) and "≡", respectively.
• As a tip, in your inductive step it's worth taking a moment to confirm to yourself that actual the steps are indeed valid for all k ≥0 (or whatever) --- no hidden dividing by zero, or presuming k was at least 2 (as in the horses-of-a-color example), etc.

Your Rights

The above are your responsibilities; you also have rights. They include:

We'll fix any mistakes, and explain any points off, though we're not likely to change any partial-credit. (Remember, clarity and succinctness are a significant part of what we're grading.)