The Problem

Consider the following "proof":

• Brad Pitt has a beard:

  


• Every goat has a beard:

  


• Hence, Brad Pitt is a goat.

The Question

State precisely where the ``proof" above fails logically.

Follow-up question

Can you prove that Brad Pitt is not a goat?

The Problem

For this and the remaining problems, we will be working with $n\times n$ matrices (or two-dimensional arrays). So for example the following is a $3\times 3$ matrix \[ \mathbf{M}=\begin{pmatrix} 1 & 2 & -3\\ 2 & 9 &0\\ 6 & -1 & -2 \end{pmatrix}. \] Given an $n\times n$ matrix $\mathbf{A}$, we will refer to the the entry in the $i$th row and $j$th column (for $0\le i,j<n$) as $\mathbf{A}[i][j]$. So for example, for the matrix $\mathbf{M}$ above, $\mathbf{M}[1][2]=0$. (We will use the convention that the top left element is the $[0][0]$ element.) We will also work with vectors of length $n$, which are just arrays of size $n$. For example the following is a vector of length $3$ \[\mathbf{z}= \begin{pmatrix} 2\\ 3\\ -1 \end{pmatrix}. \] As usual we will use $x[i]$ to denote the $i$th entry in the array/vector. For example, in the vector/array $\mathbf{z}$ above, we have $\mathbf{z}[2]=-1$.

We are finally ready to define the matrix-vector multiplication problem. Given an $n\times n$ matrix $\mathbf{A}$ and a vector $\mathbf{x}$ of length $n$, their product is denoted by \[\mathbf{y} =\mathbf{A}\cdot \mathbf{x},\] where $\mathbf{y}$ is also a vector of length $n$ and its $i$th entry for $0\le i< n$ is defined as follows: \[\mathbf{y}[i] =\sum_{j=0}^{n-1} \mathbf{A}[i][j]\cdot \mathbf{x}[j].\] For example, here is the worked out example for $\mathbf{M}$ and $\mathbf{z}$ above: \[ \begin{pmatrix} 1 & 2 & -3\\ 2 & 9 &0\\ 6 & -1 & -2 \end{pmatrix} \cdot \begin{pmatrix} 2\\ 3\\ -1 \end{pmatrix} = \begin{pmatrix} 1\times 2 + 2\times 3 + (-3)\times(-1)\\ 2\times 2+ 9\times 3+0\times (-1)\\ 6\times 2+(-1)\times 3+ (-2)\times(-1) \end{pmatrix} = \begin{pmatrix} 11\\ 31\\ 11 \end{pmatrix}. \]

Finally, we come to the actual question:

1. Design an $O(n^2)$ algorithm, which given any $n\times n$ matrix $\mathbf{A}$ and vector $\mathbf{x}$ of length $n$ correctly computes $\mathbf{A}\cdot \mathbf{x}$.

   Note

   This is exactly Exercise 1 in the support page on matrix vector multiplication.

   Hint

   The obvious algorithm works for this problem.

2. Argue that your algorithm in part above runs in time $\Omega(n^2)$. (Hence, conclude that your algorithm runs in time $\Theta(n^2)$.)
3. (Only think about this if you have time to spare.) Argue that any algorithm that solves the matrix vector multiplication problem (for arbitrary $\mathbf{A}$ and $\mathbf{x}$) needs to take $\Omega(n^2)$ time.

   Note

   This is the same as Exercise 2 in the support page on matrix vector multiplication. Further, note that this part implies the second part but if you want to use third part to solve the second part, then you will have to present the solution to third part too. I would recommend that you solve part three only if you want to stretch your algorithmic thinking.

The Problem

Let $n\ge 1$ be an integer. Given $n$ men and $n$ women, a perfect matching is a way to assign every man to a unique woman and vice-versa. For example for $n=2$, where Brad Pitt and Billy Bob Thornton are the two men and Jennifer Aniston and Angelina Jolie are the two women, one possible perfect matching consist of the two pairs (Brad Pitt, Jennifer Aniston) and ( Billy Bob Thornton, Angelina Jolie).

Here are the two parts:

• Part (a): Argue that the number of perfect matching just depends on $n$ and is independent of the identities of the men and women.

  Note

  Since HW 0 tests your prior knowledge, part (a) will not be explicitly discussed in the recitations. Starting with HW 1, part (a) will be discussed in recitations.

• Part (b): Prove that the total number of perfect matchings when you have $n$ men and $n$ women is $n!$. (Recall that $1!=1$ and for $n\ge 2$, we have $n!=n\times (n-1)\times (n-2)\times\cdots \times 2\times 1$.)

  Hint

  Use proof by induction.

The Problem

Order the following running times in ascending order so that if one (let's call it $f(n)$) comes before another (let's call it $g(n)$), then $f(n)$ is $O(g(n))$: \[2^{n^{1.00001}},~n^{3^{10}},~2^{(\log_{96}{n})^{\sqrt{2}-0.4}},~9^{\log_{10.1}{n}},~n^n,~10^{1000}\cdot n!.\] Briefly argue why your order is correct (formal proof is not needed).

(For this problem, it might help to know Stirling's approximation: \[n!=\sqrt{2\pi n}\left(\frac{n}{e}\right)^ne^{\lambda_n},\] where \[\frac{1}{12n+1}<\lambda_n<\frac{1}{12n}.\] Also recall that $x=\log_a{b}$ implies that $a^x=b$.)

The Problem

In this problem we will consider matrix and vector multiplication, but with the caveat that we already know something about the matrix. In particular for any $0\le i, j\le n-1$, we have \[\mathbf{U}_n[i][j]=\begin{cases} 0 & \text{if } j< i\\ 1 & \text{otherwise}.\end{cases}\] If you "draw" this matrix you will note that all of the elements below the diagonal is zero: such matrices are called upper triangular matrices. Further, all non-zero values (in the "upper triangular" part) are all $1$. Note that we only need to know the value of $n$ to completely determine $\mathbf{U}_n$.

You have to write code to solve the following computational problem: given any integer $n\ge 1$ and a vector $\mathbf{x}$ of length $n$, return the vector $\mathbf{y}=\mathbf{U}_n\cdot \mathbf{x}$. Read on for more details on the format etc.

Sometimes it is easier to visualize a specific $\mathbf{U}_n$. Below is $\mathbf{U}_5$ written down in a 2D-array form:

                 1   1   1   1   1   
                 0   1   1   1   1  
                 0   0   1   1   1 
                 0   0   0   1   1
                 0   0   0   0   1 
            

Input

You will not receive the matrix as the input.

What you will receive is the vector itself. Each input file will contain one vector. The length of the vector will be on the first line of the file. The vector itself will take up the remaining lines. Once again, you will not have to handle the file reading and the creation of data structures. The packaged driver will handle that for you.

The input file can be summed up in the following format:

                n
                x0
                x1
                x2
                .
                .
                .
                xn-1
            

This is an example of what a file may look like, for size $n=5$:

                 5
                43
               234
               -12
                32
               -44
            

Output

The output will be the vector $\mathbf{y}$ in vertical order. I.e.

                y0
                y1
                y2
                .
                .
                .
                yn-1
            

The correct result for the earlier example of $\mathbf{x}$ would be:

               253
               210
               -24
               -12
               -44
            

The Problem

Deep in the Pacific ocean you discover the RapidGrowers bacteria. These are single cell organism that divide themselves into two (identical) organisms/cells in one second. When you start going back to the surface you store one organism in a special container that exactly replicates their habitat. From the moment you put the organism in, it takes you $s$ seconds to come back to Buffalo to find your container bursting at its seams. ¹

Prove or disprove the following: