Shai Simonson

CSC 202

Discrete Math for Computer Scientists II

Assignment 3

Due:  Before Easter break.

Pettofrezzo text:  1.1 - 2, 4, 6, 7.    1.2 - 2, 3, 4, 7, 8, 10, 12.    1.3 - 2, 4.
Rosen text:        2.6 - 2a, 4a,c, 5, 10, 18, 20, 21.

My problems:

1.  How many multiplications (of numbers) occur in  the standard matrix multiplication of A (a b) times B (b c)?  Explain your answer.

2.  Using standard matrix multiplication, and considering the associativity of matrix multiplication, what are the fewest number of multiplications (of numbers) necessary to multiply three matrices together where the dimensions of the three matrices are:

        a.  20 50, 50 10, 10 40?
        b. 10 5, 5 50, 50 1?

3.  The following two problems can be solved with methods from discrete math I, and indeed, you did them for homework last semester.  Now let's solve them with linear algebra, assuming the closed form for the answers are polynomials (a correct assumption). 

     (a)  How many rectangles are there in an n by n grid of squares?  (For 2 by 2 there are 9 rectangles.)
     (b)  How many squares are there in an n by n grid of squares? (For 2 by 2 there are 5 squares.)
The technique used in the solution demonstrates that 2 points determine a line, 3 points determine a parabola (square function), and in general,  r+1 points determine an r degree polynomial.

For each problem (a) and (b):

i.  Using data you gather by hand, find out the answers for n = 0 to 5.
ii.  Using finite differences, calculate what degree polynomial r the answer should be.
iii.  Using the polynomial Arxr+ Ar-1xr-1+ ... +  A0, and r+1 data points, construct a set of r+1 equations.
iv.  Solve the system of equations, to calculate a closed form polynomial answer.  You may use the online matrix inverse calculator.  Check your answer against the solution from last semester.