COMP280: Homework Page

Spring 2003; see most recent

• Grades have been posted (as a gradepoint in [0,13/3]).
  My congratulations to all of you; I know that I demand a lot of work and thought from my classes, and am proud of how you all did. Thank you all for a good semester, and have a relaxing summer!
• All homework is due at the beginning of class on the due date.
• You can check your grades online; As of feb.24, you should have grades for homeworks 1-4; please inform us promptly of any discrepancy. Homework not retrieved in class will be placed in Duncan 3142.
• Clarity and succinctness are a large part of the grading criteria.
• Ghostview, a postscript (.ps) viewer.
• See further guidelines below, on writing up good homeworks.

• hw01, due jan.23 (thu): sets and functions. (Soln: postscript; set-, cross (.ss) (includes full test cases))

• Hw02, due jan.30 (thu) (22pts): properties of relations; propositional formulas and truth tables.

  • From Rosen section 7.1, exercises 2, 4, and 10. (4ed: section 6.1: exercises 2,4,8.)
    (For ease of grading, make a table combining 4 and 10, with rows "(a)"..."(d)", and columns "reflexive",...,"transitive","irreflexive", in that order. Thanks!)
  • From teachLogic [archive copy], problems {1..13} - {practice problems} = {2,4,6,8,9,10,11,12,13}. (Soln: .ps, .pdf.)

• Hw03, due feb.06 (thu) (24pts): reasoning with boolean algebra; reasoning with inference rules. From teachLogic (pdf, ps) [archive copy], problems {15..22}. (Soln: .ps, .pdf.)
  Do not do problem 23 (it has a typo); though you can do an extra-credit-version.

• Hw04, due feb.13 (thu): A shorter one (15pts)
  teachLogic hwA [archive copy]: 25,27,28,29; (pdf, ps) (soln .ps,archived .pdf)
  teachLogic hwB: 3,4. [archive copy]: 25,27,28,29; (pdf, ps) (soln .ps,archived .pdf)

  [an error occurred while processing this directive]

• Hw05, due feb.20 (thu)
  teachLogic hwC: [archive copy]: all (1-9) pdf, ps; (solution archived pdf, ps)
  Rosen 3.3: 10, 18. (4th ed 3.2: 10,18). (solution ps)

• Hw06, due feb.27 (thu); soln (ps)
  Rosen section3.3 #32;
  section3.4 #18, 36, 38, 44;
  Optionally postponed until next hw: section3.6 #12 (p.290)
  supplementary exercise #44 (*) (p.294).
  
  (4ed, respectively: p.200 #32; p.210 #16, 28, 30, does-not-exist; p.225 #12; p.228 #32; Please use the 5th ed. numbering for the graders, thanks.)

• Hw07, due mar.06 (thu).
  Solution in html, or better-formatted ps.

• Exam topics & Rosen problems and additional study-questions (.ps); some selected additional study-question solutions(.ps)
  (If you can't read postcript files, you can download ghostview, or view from an owlnet lab.)
• Exam 1 solutions
• exam1 re-do (up to 12pts extra credit; due 2003.Apr.15.)
  Standard handouts: algebra laws (propositional), inference rules (propositional), algebra laws (first-order), inference rules (first-order).

• Hw08, due mar.27 (thu). Cardinality, big-Oh, mod.
  Solution.

• Hw09, due apr.03 (thu). Counting I.
  Solution.

• Hw10, due apr.10 (thu). Counting II; Recurrence Relations
  Solution.

• Hw11, due apr.17 (thu).
  Solution.

• Hw12, due apr.24 (thu).
  Solution.

• extra-credit homework

• Exam2 study guide.

• Question/answer session -- Wed. Apr.29, 14:00-15:00, in the usual classroom. (See newsgroup.)

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 pages together before coming to class. There is no stapler in the classroom. (-10% otherwise)
• 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.
• Late policy & turn-in as per class-info sheet.
• For yes/no questions, you don't need to show any reasoning (there is no partial credit for those problems).
• For problems that ask you to "show" something, you don't need to be as meticulous as for problems that ask you to "prove".
• 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 can sometimes take more time than expected, to do so.
  • 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 useful as a program that doesn't compile!)
• 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.
• To assert a relation between two statements, use "==>" or "<==>" (between logic statements, it's idiomatic to instead use "|=" and "|= =|", respectively).
• Use spacing and indentation to reflect the structure of your answers (esp. true for proofs and programs).
• For more involved proofs, start with a quick outline, to convey your line of reasoning.
• Problem statements are always intended to be clear; if you have any questions about what's expected, please ask.

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 the right to understand any grading comment. If you have a question on the grading, you can see me or any labby; the preferred approach is to go to the office hours of that particular grader (match the initials to the list of tas/labbies). (During my own non-office-hours, feel free to drop by, though before trekking across campus you can ring to see if i'm in).

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