CSE 321 Assignment #1
Spring 2001

Due: Friday, April 6, 2001 at the beginning of class.

Reading assignment: Read the text, Discrete Mathematics and Its Applications, sections 1.1 - 1.3. Skim sections 1.4-1.8 of the text (except for cardinality on pages 76-78.) The following problems are from the 4th edition of the text. They have the same numbers in the 3rd edition of the text unless otherwise noted.

Practice Problems answered in the back of the book: Section 1.1, problems 7, 15, 35 (3rd edition 27); Section 1.2, problems 7, 9, 25; Section 1.3, problem 9 (3rd edition 7)

Problems:

  1. Section 1.1, Problem 8, all parts except (d).

  2. State in English the converse and contrapositive of each of the following implications:

    1. If a is pushed onto the stack before b, then b is popped before a.

    2. If the input is correct and the program terminates, then the output is correct. (Be sure to use De Morgan's Law to simplify the contrapositive.)

  3. Section 1.1, Problem 36. (In 3rd edition problem 28.)

  4. Section 1.2, Problem 8, parts (b) and (d).

  5. Section 1.2, Problem 10, parts (c) and (d).

  6. Section 1.2, Problem 26. (Hint: First do practice problem 25 and check your answer.)

  7. Section 1.3, Problem 10. (In the 3rd edition, problem 8.)

  8. (Bonus) Section 1.1, Problem 34. (In the 3rd edition, problem 26.)

  9. (Bonus) Show how to swap the contents of two n-bit registers using no extra storage and only the bit operators AND, OR, and XOR. For an example of the use of these operations, if register 1 contains X and register 2 contains Y, then you can perform the bitwise XOR of X and Y and store the result in register 1. After this, the contents of register 1 is X XOR Y and the contents of register 2 is Y.

  10. (Bonus) Section 1.1, Problem 42. (Not in the 3rd edition.)