CSPP 512 Mathematics for Computer Science - Summer 2001

Homework 7 (assigned August 1, due August 8)

This homework assignment covers the material in sections 2.5 and 2.6 of the textbook and includes one problem on induction.

1. Do problems 32 and 34 on page 90. (Each problem is worth 4 points.)

2. (Hard) Do problems 38, 39, and 43 on page 90. (Each problem is worth 3 points.)

3. Do problems 6, 7, 10, 12, 13, 17, 18, 23, and 24 on pages 96-97. (Each problem is worth 4 points.)

4. Let A be a m x n matrix, B be a n x p matrix, and C be a p x r matrix. Show that A(BC) = (AB)C. (3 points)

5. Let A be a 3 x 2 matrix, B be a 2 x 4 matrix, and C be a 4 x 1 matrix. A, B, and C all have integer entries. In which order should A, B, and C be multiplied to use the least number of multiplications of integers? How many mutiplications of integers are used to compute A(BC)? How many to compute (AB)C? (4 points)

6. Evaluate the following expressions, where AND, OR, and XOR denote bitwise "and", bitwise "or", and bitwise "exclusive or", as defined in class:
   (a) 11000 AND (01011 OR 11011)
   (b) (01111 AND 10101) OR 01000
   (c) (01010 XOR 11011) XOR 01000
   (d) (11011 OR 01010) AND (10001 OR 11011)
   (Each problem is worth 2 points.)

7. How many bit operations are needed to find A * B, where A and B are n by n matrices and * denotes Boolean product as defined in class? (4 points)

8. Find the lexicographic ordering of the bit strings 0, 01, 11, 001, 010, 011,0001, and 0101 based on the ordering 0 < 1. (2 points)

9. Prove that 3ⁿ < n! whenever n is natural number greater than 6 using mathematical induction. (5 points)