\documentclass[12pt]{article}
%\usepackage{ccfonts,euler}
\usepackage{fullpage,amsmath,amssymb,amsfonts,graphicx,url}
\usepackage[version=3]{mhchem}
\def\suptilde{\raisebox{-2pt}{$\displaystyle \tilde \null$}}
\begin{document}

\title{General Mathematics and Computational Science II}
\author{Final Exam}
\date{May 22, 2015}
\maketitle

% \vspace*{\fill}
% {\baselineskip=40pt
% \begin{tabbing}
% Student ID Number: \= \kill
% Last Name: \> \rule[-2pt]{10cm}{0.3pt} \\
% First Name:  \> \rule[-2pt]{10cm}{0.3pt} \\
% Signature: \> \rule[-2pt]{10cm}{0.3pt} \\
% %Code: \> \fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% \end{tabbing}}


% \vspace*{\fill}

% \newpage

\begin{enumerate}

\item A bipartite graph with vertex sets $V_1$ and $V_2$ is
\emph{regular} if every vertex in $V_1$ has degree $d_1$ and every
vertex in $V_2$ has degree $d_2$.

Show that there exists a matching from $V_1$ into $V_2$ provided $d_1
\geq d_2>0$.
\hfill(10)
%\newpage

\item Let $H_A$ denote the point reflection about a point $A$ with
coordinates $\boldsymbol{a}$.  Let $\Pi_{\boldsymbol{v}}$ denote the
translation by a vector $\boldsymbol{v}$.
\begin{enumerate}
\item Show that $H_A \circ H_B = \Pi_{2(\boldsymbol{a} -
\boldsymbol{b})}$.
\item Show that $H_A \circ H_B = H_B \circ H_C$ if and only if $B$ is
the midpoint of the line segment $AC$. 
\item What can you say about the relative locations of $A$, $B$, $C$,
and $D$ in the case
$H_A \circ H_B \circ H_C \circ H_D = \operatorname{Id}$?
\end{enumerate}
\hfill(5+5+5)

%\newpage

\item Let $G_1$ and $G_2$ be two finite Abelian groups, written
additively.  We define the direct sum $H=G_1 \oplus G_2$ as the set of
ordered tuples $h=(g_1,g_2)$ with $g_1 \in G_1$ and $g_2 \in G_2$.
\begin{enumerate}
\item Define a $+$-operation on $H$ that makes it an Abelian group.  
\item Verify explicitly that with your definition you indeed obtain an
Abelian group.
\item What is the order of $H$?
\item Let $\chi_i \colon G_i \to \mathbb{C}\backslash \{0\}$ be a
character for $i=1,2$.  Show that
\[
  \psi(h) = \chi_1(g_1) \cdot \chi_2(g_2)
\]
defines a character on $H$.

(Recall that $\chi_i \colon G_i \to \mathbb{C}\backslash \{0\}$ is a
character if it is a group homomorphism into
$\mathbb{C}\backslash \{0\}$, the group of nonzero complex numbers
endowed with multiplication.)

\item Show that every character on $H$ is of this form.

\end{enumerate}
\hfill(5+5+5+5+5)

% \newpage
% \mbox{}

% \newpage
\item Consider the linear programming problem 
\[
  \text{maximize } z = 2 \, x_1 + x_2
\]
subject to
\begin{gather*}
  -x_1 + x_2 \leq 1 \,, \\
  x_1 - 2 \, x_2 \leq 2 \,, \\
  x_1, x_2 \geq 0 \,.
\end{gather*}
\begin{enumerate}
\item Determine the solvability of this problem and find the solution
if it exists, using the simplex method.
\item Draw the feasible region and the level lines of the objective
function; check for consistency with your answer in part (a).
\item Write out the dual problem and determine its solvability.  (No
computation required.)
\end{enumerate}
\hfill(10+5+5)

% \newpage
% \mbox{}

% \newpage
\item Show that the problems
\[
  A \boldsymbol{x} = \boldsymbol{b} \,, 
  \qquad \boldsymbol{x} \geq \boldsymbol{0}
\]
and
\[
  \boldsymbol{y}^T A \geq \boldsymbol{0} \,, 
  \qquad \boldsymbol{y}^T \boldsymbol{b} < 0
\]
cannot both have a solution.
\hfill(10)

(In fact, \emph{Farkas' lemma} states that excatly one of the two has
a solution, but the complete proof is substantially more difficult.)

%\newpage
\item Recall that
\[
  \tilde v_k = \frac1N \sum_{j=0}^{N-1} \mathrm e^{-\mathrm i k j h} \, v_j
\]
with $h=2\pi/N$ denotes the discrete Fourier transform of the complex
numbers $v_0, \dots, v_{N-1}$.

Define the discrete convolution of vectors
$\boldsymbol{v}=(v_0, \dots, v_{N-1})$ and
$\boldsymbol{w}=(w_0, \dots, w_{N-1})$ by
\[
  (\boldsymbol{v} \circledast \boldsymbol{w})_j
  = \frac1N \sum_{\ell=0}^{N-1} v_\ell \, w_{j-\ell}
\]
where all indices are understood modulo $N$.

Show that
\[
  (\boldsymbol{v} \circledast \boldsymbol{w})_k^{\suptilde}
  = \tilde v_k \, \tilde w_k \,.
\]
\hfill(10)

%\newpage

\item A $2\pi$-periodic signal is sampled $N$ times in the interval
$2\pi$.  Suppose the signal contains only a fundamental frequency with
wavenumber $k_0 = \tfrac25 \, N$ and its first harmonic at
$k_1 = \tfrac45 \, N$.

\begin{enumerate}

\item Which frequencies does the trigonometric interpolant of the
samples contain?

\item \emph{Extra credit.} What does the reconstruction sound like?
And what happens for different fundamental frequencies $k_0$? 
\end{enumerate}
\hfill(10+\emph{10})

\emph{Hint:} Recall the aliasing formula
\[
  \tilde u_k = \sum_{m \in \mathbb Z} \hat u_{k+ mN}
\]
for $k = -N/2, \dots,N/2-1$.

\end{enumerate}
%  \newpage

% \hfill{}
% \newpage



\end{document}
