Homework Assignment #1
Assigned: Fri 27 Sep 2002
Due: Wed 9 Oct 2002
Problem 1:
Determine the cardinality (size) of each of the following sets. For the purposes of
this problem, assume that the sets A, B and C are disjoint and have the
following cardinalities:
Note:
If you need to describe infinite cardinalities, use the notation from problem 2 below.
Problem 2:
Describe the cardinalities of the sets from problem 1 above, but now using the
more general characterizations finite,
countably infinite or uncountable, and assuming
these cardinalities for the sets A, B and C:
Problem 3:
What is the cardinality of the following set, given that A = {a,b,c}?
Hint: answering this question involves a little combinatorics, which we
haven't reviewed, but you don't need to be an expert (we'll need very little
combinatorics in the class). Think in terms of numbers of strings of each possible
length, counting both the "candidate" strings and the ones eliminated because of
the restriction involving the substring (be careful not to over-count or under-count!).
Problems 4-10:
Do the following exercises and problems from the textbook (on pages 83-90).
Note: you may of course wish to do additional exercises and problems form
the text to hone your skills for the exam.
| A | = 3;
| B | = 2; and
| C | = 4.
| A | = finite;
| B | = countably infinite; and
| C | = uncountable.
{ w Î A* |
abc is not a substring of w
and | w | £ 6 }
