Parts 1, 2 and 3 are due Thursday, September 4. Parts A, B, C, ... are Tuesday, September 9.

Written work must be

• legible - handwritten papers are OK since writing mathematics in most word processing systems is a painful distraction from the ideas.

• logically clear (of course) - the point of the arguments you make is not to convince me (I already know) or even to convince yourself (it may be obvious to you) but to convince me that you have convinced yourself for good reasons.

• free of spelling and grammatical errors - I will make some allowance made for non native speakers of English, but I expect your English to improve as the semester progresses.

• honest - if you are confused at some point, say as clearly as you can what you are confused about. Don't guess - a correct guess without a good reason may convince you that you understand the problem when that is not in fact true. An honest description of what puzzles you will teach you more, and let me teach you more.

1. Apply for a cs320 account on the CS Department's unix system. Apply for that account even if you already have a unix account, so that you are put on the proper mailing lists.

   I will use your cs email address for all electronic communication, so be sure to check it regularly, or forward from it. If you write me from that address I will surely get your email. If you write me from some other address your mail may end up in my spam bucket.

2. Answer the question I've asked about the sudoku puzzle from the Globe.

3. Fill out the questionnaire on the course web page at www.cs.umb.edu/~eb/320/questionnaire.html

You should read the book if you find that it helps you understand the material and do the problems. You may find that you don't need to.

1. B&W Lo-10,11/11,12,14,16,23 (for 12 do the converse only, not the inverse).

2. B&W SF-12/5

3. B&W SF-14/13. (If you can, prove (e) two ways, first directly using some method of your choice, then as a consequence of (a)-(d).

4. In class we discussed representing subsets of a (finite) set as bit vectors. How might this representation provide another way to attack the previous problem. (If you've had abstract algebra you should be able to answer this in one line. If not, try to find an answer anyway.)

5. If you ask n people a yes/no question, there are |P([n])| = 2ⁿ ways the answers could turn out - each person could answer "yes" or "no". Another way to say that is that there are 2ⁿ ways to divide an n element set in two pieces, if the pieces are to be labelled and empty pieces are allowed - the "yes" piece and the "no" piece.

   Suppose the question could be answered yes/no/maybe. Then how many ways are there. That is, how many ways are there to divide a set with n elements into three labelled subsets, empties allowed?

6. Counting the number of ways to divide a set with n elements into k unlabelled pieces with no empty pieces allowed is a very hard problem. But you can do a few computations. Work out the answer for n = 3, 4 and 5, k = 1, 2 and 3.

   I suggest you do this with a classmate, or at least check your answer with a classmate.

   If you work out a few more examples you might be able find out some cool stuff from The On-Line Encyclopedia of Integer Sequences

From: Ethan Bolker 
To: "Henry Z. Lo" 
CC: cs320-1@cs.umb.edu, "Shane C Woods" ,
        "Julia Strangie-Brown" ,
        "Johnston, Mary Jane" , eb@cs.umb.edu
Subject: HW1
Date: Mon, 8 Sep 2008 08:31:32 -0400 (EDT)


 > From: "Henry Z. Lo" 
 > To: eb@cs.umb.edu
 > Subject: HW1
 > Date: Sun, 7 Sep 2008 21:58:49 -0400 (EDT)
 > 
 > Hi Professor,
 > 
 > On part D, do you mean using bit vector representations of subsets
 > in order to solve Part C of the homework?  I can't seem to think of
 > how I can prove equality using bit vectors. 

Yes, that's what I mean. Here's a hint about how bit vectors might
help: think about how to compute the bit vector representation of 
A +O B from the bit vector representations of A and B.

(A +0 B is the best I can do in ascii to get the + inside the circle.)

 > On part E of the HW1, what does it mean if the pieces of the set
 > are labeled or unlabeled? 

They're labelled - the problem says so.

 > Thanks,
 > Henry