COMP280: Homework Page

Spring 2004

• Clarity and succinctness are a large part of the grading criteria.
• Homework not retrieved in class will be placed in Duncan 3142.
• You can check your grades online once you register yourself.
  Please inform us promptly of any discrepancy.
• See further guidelines below, on writing up good homeworks.

• hw01 [archive pdf], Propositional Logic.
  In future years: also include hw04's exercises 1-3 (newsgroup, feedback form, learning style survey).
  Due 2004.Jan.27 (Tue) 17:00.
  hw01 solution [archive pdf].

• hw02 [archive pdf], Reasoning with inference rules; some Quantifiers.
  Due 2004.Feb.03 (Tue) 17:00.
  hw02 solution [archive pdf].

• hw03 [archive pdf], First order logic.
  Due 2004.Feb.10 (Tue) 17:00.
  hw03 solution [archive pdf].

• hw04, Sets.
  Due 2004.Feb.17 (Tue) 17:00.
  Some common problems with this hw.
  hw04 solution (ps, pdf)
  [Ghostview, a postscript (.ps) viewer.]

• hw05, Relations, functions.
  Due 2004.Feb.24 (Tue) 17:00.
  hw05 solution (ps, pdf)

• hw06, Cardinalities; mathematical induction.
  Due 2004.Mar.16 (Tue) 17:00.
  hw06 solution (ps, pdf)

• hw07, Structural Induction, Program correctness I.
  Due 2004.Mar.23 (Tue) 17:00.
  hw07 solution

• hw08, Program Correctness II; big-Oh.
  Due 2004.Mar.30 (Tue) 17:00.
  hw08 solution

• hw09, Modular Arithmetic.
  Due 2004.Apr.06 (Tue) 17:00.
  hw09 solution

• hw10, counting.
  Due 2004.Apr.13 (Tue) 17:00.
  hw10 solution

• hw11, counting II, FSM.
  Due 2004.Apr.20 (Tue) 22 (Thu) 17:00.
  hw11 solution

• extra-credit homework.
  Due 2004.May.05 (Wed) 17:00.

General Homework policies

• 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 can be turned in in-class on the due-date, or under the instructor's door (DH3117) by 17:00 of 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 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 this makes or breaks whether you'll ever look back at your work in the future.
• 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: in particular, use "=" when you mean equality (rather than "~" or "-->"). Write what you mean: e.g. write "T"/"F" for booleans rather than the numbers 0/1. Avoid notation with no standard meaning (strange arrows, etc) -- the labbies are not always good at divining what you actually meant.
• Use spacing and indentation to reflect the structure of your answers (esp. true for proofs and programs). Particular examples:
  • If proving "A iff B" by showing each direction separately, clearly label those two sub-sections.
  • Clearly state your proof method ("proof by contradiction:", "proof by [regular/strong/structural] induction")
  • 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 in A and x not-in B. ...")
  • For more involved proofs, start with a quick outline, to convey your line of reasoning.
• Extra credit 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.)
• 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.

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.)