\documentclass{article}

\usepackage[letterpaper,top=3cm,bottom=2cm,left=3cm,right=3cm,marginparwidth=1.75cm]{geometry}

\usepackage{amsmath}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{enumitem}
\usepackage{lipsum}
\usepackage{fancyhdr}
\pagestyle{fancy}

\setlist[enumerate,1]{label=\arabic*.,itemsep=24pt}
\setlist[enumerate,2]{label=\theenumi\alph*.,itemsep=12pt}


% Some useful macros %
\newcommand{\set}[1]{\left \{ #1 \right \}}                     % Set notation: { ... }
\newcommand{\expect}[1]{\operatorname{E}\left[\,#1\,\right]}    % Expectation: E[ blah ]


\lhead{CPSC 421 Asst 0}
\chead{Fall 2018}
\rhead{PUT YOUR CSID HERE}


\begin{document}
\begin{enumerate}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Let $f : A \rightarrow B$ be a function where $A$ and $B$ are finite sets. We say $f$ is:
\begin{itemize}
\item \textbf{Injective (or ``one-to-one''):}
if $f(a) = f(a')$ then $a=a'$,
\item \textbf{Surjective (or ``onto''):}
for every $b \in B$ there exists $a \in A$ with $f(a) = b$.
\end{itemize}
If $f$ is both injective and surjective, we say that $f$ is a bijection. Let $A = \{ a, b, c \}$ and $B = \{d,e  \}$. 

\begin{enumerate}
\item Define a map which is an injection from $A$ to $B$, or explain why this is not possible.

\textbf{Solution.} \lipsum[1]

\item How many different functions are there from $A$ to $B$? How many of these are injections? How many are surjections? How many are bijections? 

\textbf{Solution.} \lipsum[2]

\end{enumerate}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item
Suppose $A$ and $B$ are finite sets and assume $x \in A \cap B$. For each question either provide a proof that the statement is true or show via counterexample that the statement is false. 
\begin{enumerate}
\item $x \in B \setminus A$.

\textbf{Solution.} \lipsum[3]

\item $x \in \{ A \} \cap \{ B \}$.

\textbf{Solution.} \lipsum[4]

\item $x \in \{ A \cup B\}$.

\textbf{Solution.} \lipsum[5]
\end{enumerate}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item
Suppose $X$ is a random variable which takes values $0$ and $1$ with probability $1/2$ each. What is $\expect{2^{X^{100}}}$? (Here the symbol $\expect{}$ denotes the expected value operator).

\textbf{Solution.} \lipsum[6]


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item
Consider the following algorithmic problem.
The input is a graph with $n$ nodes (and no multi-edges).
A \emph{rectangle} in the graph is a sequence of four distinct vertices $(v_1,v_2,v_3,v_4)$ such that
the edges $\set{v_1,v_2}$, $\set{v_2,v_3}$, $\set{v_3,v_4}$ and $\set{v_1,v_4}$
are all present in the graph.
(We do not care whether $\set{v_1,v_3}$ or $\set{v_2,v_4}$ are edges.)

Give an algorithm to decide if the given graph contains a rectangle.
The running time of your algorithm should be polynomial in $n$.
You may assume whatever computational model you like, and assume that the graph is represented
however you like.

\textbf{Solution.} \lipsum[7]


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item 
Let $S(n) = 1 + 2 + \cdots + n$ be the sum of the first $n$ natural numbers and let $C(n) = 1^3 +
2^3 + \cdots + n^3$ be the sum of the first $n$ cubes.
Prove the following equalities by induction on $n$, to arrive at the curious conclusion that $C(n) =
\big(S(n)\big)^2$ for every $n \geq 1$.

\begin{enumerate}
\item $S(n) = n(n+1)/2$.

\textbf{Solution.} \lipsum[8]

\item $C(n) = (n^4 + 2n^3 + n^2)/4 = n^2(n+1)^2/4$.

\textbf{Solution.} \lipsum[9]

\end{enumerate}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item
Let 
$$
A ~=~ \begin{bmatrix}
3 & 6 & 0 \\ 0 & 0 & 0 \\ 2 & 4 & 3
\end{bmatrix}.
$$

\begin{enumerate}
\item Find a non-singular sub-matrix of $A$ that has maximum size.

\textbf{Solution.} \lipsum[10]

\item Let $I$ be the $2 \times 2$ identity matrix. Find a matrix $B$ for which the rank of $B-I$ is strictly less than the rank of $B$. Find a matrix $C$ for which the rank of $C-I$ is strictly greater than the rank of $C$.

\textbf{Solution.} \lipsum[12]

\end{enumerate}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item
Your friend has an interview with a large tech company and they will be quizzing her on some basic
graph theory. He has lost his notes and doesn't have any cellular data or internet connection.
Therefore, you are his last hope. He needs to know whether the following are true and false and
needs a satisfying explanation. Can you help him out? 

If the statement is true, explain in one or two sentences.
If the statement is false, give a counterexample in one or two sentences.

\begin{enumerate}
\item If $G$ is connected, the the complement of $G$ is disconnected. 

\textbf{Solution.} \lipsum[13]

\item Removing an edge from a tree creates two trees. 

\textbf{Solution.} \lipsum[14]

\item The edges of every cycle can be colored using two colors so that no two edges sharing a vertex are colored by the same color. 

\textbf{Solution.} \lipsum[15]
\end{enumerate}




\end{enumerate}  % End of all homework questions


\end{document}
