CSC 236 -- Assignments

Submission Instructions

Here is the Cover Page in Postscript and PDF.

Deposit your assignment in the "CSC 236" drop-box in BA 2210/20 any time before the due time. You may also submit it early in lecture.

Assignment 2c and 5

Due: Friday, April 8th.

In Postscript or PDF format.

Solutions in Postscript or PDF format.

Notes

Question 3(a). Make a few long strings that are in L. As you write down your 0s and/or 1s, when do you have to worry? When are you safe? Hint: think about how many 0s or 1s in a row you are allowed. Alternatively: do part (b) first.

Question 3(b, c). Write a program for it in the form I showed in class (always good advice if you have trouble with a DFSA, and sometimes for an NFSA). Work on (b) and (c) at the same time: every time you convince yourself that two strings need a different state, make those states in your DFSA! For each state in your DFSA, find a string that goes into it: then for (c), show that you definitely had to have different states for all those strings (and if you can't show that, then combine those states in your DFSA!).

Assignment 2b and 4

In Postscript or PDF format.

Solutions in Postscript or PDF format.

Notes

More Hints for the Java Model

Some students are trying to do the question without properly understanding Propositional Logic, or at least the terminology involved! So a short hint: review my lecture notes! It's all in there.

Find the definition of Propositional Formula in my notes and in the textbook. Identify the six ways to construct (!) a propositional formula. Also, make sure you understand the difference between a Propositional Formula and a Propositional Variable.

Find the sample representation of a Propositional Formula as a tree in my notes and in the textbook. Remind yourself how this would be represented in Java in CSC148/150 (what are the nodes? what are the links?).

Remind yourself how to extend an abstract class: write as much of the `skeleton' of each subclass as possible even if you have no idea what the subclass does!

Find the definition of t and t* in my notes, and tau and tau* in the lecture notes. What is such a t called? What is one way to "think of" such a t? Does anything in the code use that term? What Java datatype is being used for t? How could you picture that datatype? Is that datatype used anywhere else in the code?

What is a Truth Assignment? Is there anything in the notes that requires looking at all truth assignments? Do I give you anything to generate all truth assignments?

Run the TruthAssignmentIterator and print out its values. Look at my lecture notes: is there anything that looks like the output?

Corrections

toString() should be abstract in PropositionalFormula.

Clarifications

For 4Q2, comments are not required except for a header comment for tStar that should state the preconditions on t.

For 4Q3, "complete" means that every boolean function can be represented using the connectives. This term is in the textbook, but I may not have mentioned it that way in lecture.

Hints

For 2BQ1, prove one or both of the following:

P /\ (P \/ Q) LEQV P.
P \/ (P /\ Q) LEQV P.

To prove the first:

Add on \/ (Q /\ ~Q) by an identity law.
Break the result down to CNF form using the distributive laws.
Do some simple simplifications; make sure to end up with something symmetric in Q and ~Q.
Recombine using the distributive and identity laws.

Also, though there are 25 pairs of formulas to compare, you can cut down the number that you have to think about to very few, and your justifications should reflect that.

For 2BQ2, your work for 2BQ1 should make most or all of this very quick.

For 4Q1, use structural induction. As usual, convince yourself first. For example, if it's true for P and Q, why is it true for (P /\ Q)? If you split (P /\ Q) into two substrings, does that split P and/or Q?

For 4Q3, as probably discussed in tutorial, it is complete for one propositional variable. So make as many different boolean functions as you can using only two variables and the two connectives: look for a property that all the outputs have. Unlike our example in lecture, it won't be a property of just a single truth assignment.

Assignment 2a and 3

In Postscript or PDF format.

Page 1/2 of solutions in Postscript or PDF format.

Page 2/2 of solutions in Postscript or PDF format.

Notes

Corrections

Just one, for A3 Q1: Assume m and n are both non-zero. In particular, the postcondition will be vacuously true if m = n = 0.

Finding invariants

Some general advice about invariants that I posted to the newsgroup:

For the invariant, like with so many things in computing and life:
  try both bottom-up (from given to goal), and
           top-down  (`from' goal `to' given - but be careful about the logic,
                        and don't take `from' and 'to' too literally)
   approaches.

   Bottom-up:

     trace the code

     the code gives you an inductive/recursive relationship between
      v_k+1 and v_k, where v is a variable

       E.g. n_0 = 0, n_k+1 = n_k + 1 in the first question

     but summarize what you see during the trace in non-inductive terms

       E.g. n_k = k + 1

   Top-down:

     take the postcondition

     try to remove the part of it that comes from
      the negation of the loop condition

     pretend what is left is the loop invariant

     it can't be (well, I suppose it could be if the loop is pointless)

     remove the parts that are not true at every iteration

Common mistakes

You should not mention the values of the k-1 or k+1 iteration in I(k). The point of the invariant is to not mention the change from k-1 to k or k to k+1. Instead, the proof of the invariant mentions this change (since that is what is given explicitly in the code).

Similarly, I(k) should not mention what will happen after the loop ends. For example, it should not say anything like "will return ...". If you could in fact prove an invariant that mentions what will happen at the end, then all you would have to prove is I(0) and then you would know what happens at the end. This is unlikely!

In summary: I(k) should be only about the current values of the variables after the kth iteration, in terms of the initial inputs.

More about finding a good loop invariant

First: convince yourself that the code works! Pretend to explain it to someone else.

Second: look at the values of the variables when you trace the code. Summarize what the possibilities are so that a stupid/uncreative person can take a set of values and say whether or not they can occur. For example, do not say "check whether x is the result of repeatedly adding 2 to 5", instead say "check whether x is odd and at least as large as 5".

Assignment 1

Due: Wednesday February 9th, with late penalties as described in the course outline.

In Postscript or PDF format.

Solutions in Postscript or PDF format.

Notes

Question 1: in case the meaning is not clear, the "exists c" is outside/before the "for all n". In other words: -]c in N, \-/n in N, f(n) <= cn^4. If you're wondering how to find c, try proving the result without picking c first: at some point(s) you will discover that you want certain conditions on c. Then go back and replace c with one satisfying those conditions.

Question 2: in lecture we saw a (harder?) example of induction for a claim involving two variables.

Question 3: by non-trivial I mean something that someone won't look at and immediately say "of course they're equal". Hint: look at some of the algebra from the first tutorial. For part (a) you want sqrt(3) = f(sqrt(3)) for some f. For part (b), replace one of the sqrt(3)s (so there are actually two possible answers for (b)). For part (c), practice with this thought experiment: prove that sqrt(3) is not 236/136, using (b).

Question 4: You may put your answers to all the parts together into one answer.

Question 4(a): I do mean simple; think CSC108.

Question 4(b): I've been emphasizing that your predicates in induction should `return a boolean', but there is something more appropriate here, since you are using the result that P is true, not proving it. Notice that P is an existential statement. Think about what we did with n % m in lecture:

        \-/m in N, \-/n in N, m != 0 ->
          -]r in N,
            r < m /\ -]q in N, n = qm + r.

We proved this (using the Well-Ordering Principle), and then we implemented a method to calculate r from m and n. The algorithm was similar to the proof (or at least the discussion of the proof). Compare the form of P with the above.

Question 5: Remember from lecture and perhaps an example in tutorial that the way to think about trees inductively by height is usually to think of building them from the root's subtrees (which have smaller height). You can check your formula for b_h by comparing its values against the values produced in (b).