Assignment Schedule
Announcements, clarifications, corrections and revisions to assigment
specifications are posted to the
Announcements page.
Please read this page regularly.
- Assignment handout (PDF)
(PS)
- Due by 12:00 noon inside CSC165 drop box in BA 2220 on
Thursday, December 7.
- Clarifications and hints:
- Q1b: If you come up with an exact expression for T(n), technically you
would need to prove that it's correct. It might be less work to bound T(n)
from above and from below.
- Q2: yes, the floating point system includes zero and positive and
negative numbers.
- Q3b: reformulate to try to reduce the error. You might not be able to
avoid error completely. (Hint: it's a difference of squares.)
- Sample solutions:
PDF or
PS
- Assignment handout (PDF)
(PS)
- Due by 12:00 noon inside CSC165 drop box in BA 2220 on
Thursday, November 16.
- Update:
Extension to Friday, November 17 at 5:00pm (in the drop box).
For 10% bonus, hand in by original due time.
No grace days can be used to further extend this assignment.
- [November 15] Clarifications and hints:
- Q1a: Keep it simple. We're asking about a single iteration
of the loop. The "express symbolically" means tell us
precisely what you're proving in part (b). This is an easy question.
- Q2a: Don't worry if functions become negative. As long as they're
eventually always nonnegative, we're okay. If the negativeness in (a)
bothers you, add a constant of a million to the function, and solve that.
- Q4: When n is not a multiple of 8, n/8 has a fractional part, so only
use that fraction of another 16-bit int. (For the example, use only 1/2
of an int, or 8 bits.) Technically, we'll need the ceiling of n/8 elements
in the array.
- Q4b: To "show how to look up" the the ith nucleotide, just describe
how to determine its value. You do not need to write code. Saying "take
integer A[x]" and "look at bit y of this int" are permitted operations
(and can easily be coded in Java/C/etc. using advanced operations).
Each of these operations take constant time (i.e., doesn't depend on n).
- Q4b: "reprent" is just a new-age spelling of "represent". Oops.
- Sample solutions:
PDF or
PS
- Assignment handout (PDF)
(PS)
- Due by 12:00 noon inside CSC165 drop box in BA 2220 on
Thursday, November 2.
- [30 October] Clarifications and hints:
- Q1a: Yes, 0 is a multiple of 3.
- Q1b: How do you negate "A ≤ B ≤ C"? Well, ≤ is a binary
predicate, so think of replacing "a ≤ b" with something like LTE(a,b).
Doesn't quite work, does it? That's because this form isn't exactly legal
according to our logical rules--it's a common shorthand for another
formula. Rewrite "A ≤ B ≤ C" in its proper form, then negate.
- Q1, Q2: Yes, you may use nested subcases. You may nest any of the proof
structures you've seen.
- Q3: More about tic-tac-toe, in case you don't know the game.
- Q3b: WX(5,7) should be true, but WX(4,8) should be false.
The domain for m1 and m2 is M.
You don't have to worry about legality of moves here (that is, assume
m1 and m2 are allowed).
Any correct answer (including a great big disjunction) is fine.
- Q3c: Don't include any specific board positions here (use
quantification instead). This is related to a question from A2.
Imagine this modified game of rock-paper-scissors: player 1 throws a shape,
then player 2 throws a shape. I might say "player 2 should win".
Formalize this statement (hint: whatever player 1 throws, there is a shape
that player 2 can throw and win the game). The answer to Q3c is similar.
- Q3c: It is optional to introduce a predicate to indicate which move
is made when (eg. a predicate that says m1 is X's next move, o1 is O's
move). We'll infer the ordering of the moves from their names or by
reading quantifiers left to right. (Strictly speaking, introducing such
predicates is necessary, but I want to keep things simple here.)
- Q3c: Yes, you may define a restriction of the domain of M
(perhaps M'={4,5,7,8,9}).
- Q4a,b: We are asking about a single iteration of the while loop.
Sometimes noting something simple about one iteration (a) allows us to
conclude something important about the entire algorithm (c,d)
that would ordinarily be hard to show.
- Sample solutions:
PDF or
PS
- Assignment handout (PDF)
(PS)
- Due by 12:00 noon inside CSC165 drop box in BA 2220 on
Thursday, October 12.
- Q5: Recall that "a divides b" means that
b = ak for some natural number k.
- [10 October] Q3: the term "class clown" means a student who acts like
a clown in class (like Bart Simpson). When formalizing,
make "student x is a class clown" a predicate.
- Q3: Use only one domain (students in the class) and only the class
clown predicate and equality (or inequality).
- Q4: The terms "first", "second" and "third" refer to the first, second
and third cards played (i.e., the first, second and third turns of the game).
Try to use predicates that are easy to determine whether true or false,
and combine them to express the meaning of the statements.
- Sample solutions:
PDF or
PS
(with rough marks break-down)
- Assignment handout (PDF)
(PS)
- Due by 12:00 noon inside CSC165 drop box in BA 2220 on
Thursday, September 28.
- Q1: There are 4 regular playing cards before you on the table.
Two have their fronts showing (K and 6), and two have their backs showing
(so you can see if they are marked or not). Initially, no relationship
between "face on front" and "marked on back" is asserted.
Which of these 4 cards must you turn over (to see the other side) to verify
or disprove the statement, in each case?
- Q2: The relationship you must express in part (a) is that nothing is
in the "X" region (equivalently, everything is outside the "X" region).
- Q3: When you formalize these statements, be sure to define any domains
or predicates you use (such as P = set of pets, S(p) = pet p is soft, ...).
- Q4: Remember, not all sentences are necessarily quantified! Don't try
to add quantification if you don't need to!
- Sample solutions:
PDF or
PS
(with rough marks break-down)
Submission instructions
Assignments will consist of
a number of "pen-and-paper" questions
(whose solution
can be handwritten or typed),
and must be handed in using the
cover sheet for assignments (Adobe PDF document)
(PS).
All assignments must be submitted
directly to the CSC 165 drop box in BA 2220
or given directly to the instructor
before the specified time on the due date.
Late assignments will not be accepted
except when using your grace day or
in truly unusual circumstances.
Each student will have one grace day to use during the term, allowing
the assignment to be handed into the drop box within 24 hours after the
due time. This one grace day is indivisible and can only be used once
(that is, you cannot use 4 hours for A1 and 20 hours for A2).
To use a grace day, indicate its usage on the cover sheet.
The cover sheet also includes a statement regarding the originality of
your work and a disclosure of resources you used to complete your
assignment (including any books, web sites, fellow students, tutors,
other people, etc.). This disclosure allows us to see that types of
resources students like to use, and gets you thinking about what is
and isn't acceptable with regard to collaboration. Failure to disclose
a collaboration may be an academic offense. Your disclosure
in no way whatsoever affects your mark on the assignment.
If you don't use any additional resources, indicate "none" in the space
provided on the cover sheet.