\documentclass[12pt]{article}
%\usepackage{ccfonts,euler}
\usepackage{fullpage,amsmath,amsfonts,colortbl,graphicx}

\def\e{\mathrm{e}}
\def\i{\mathrm{i}}

\begin{document}

\title{General Mathematics and Computational Science II}
\author{Final Exam}
\date{May 23, 2014, 12:30--14:30}
\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 connected graph $G$ is called $2$-connected if it remains
connected after removal of any one of its vertices.

\begin{enumerate}
\item Give an example of a graph that is connected, but not
$2$-connected.
\hfill(5)
\item Show that a graph with at least three vertices is $2$-connected
if and only if every pair of vertices lies in a cycle.
\hfill (5+5)
\end{enumerate}


%\newpage

\item If $A$ and $B$ are points in the plane, let $U_{AB}$ denote the
glide reflection along the line $AB$ which maps $A$ to $B$.
\begin{enumerate}
\item Given a rectangle with vertices $A$, $B$, $C$, and $D$, show
that 
\[
  U_{CD}\circ U_{BC} \circ U_{AB} \circ U_{DA} = e .
\]  
(In other words, ``gliding around the a rectangle'' is the identity.)

\item Find a condition for a more general quadrilateral that ensures
that gliding around it also results in the identity.

\emph{Hint:} If the angle between $AB$ and $BC$ is $\alpha$, by which
angle does $U_{BC} \circ U_{AB}$ rotate a vector?
\end{enumerate}
\hfill (5+5)

%\newpage


\item 
\begin{enumerate}
\item Characterize the group of motions of the line, i.e., the group
of maps $\phi \colon \mathbb R \to \mathbb R$ which preserve the
distance between points.

\item Prove that the set of matrices 
\[
G = \left\{
\begin{pmatrix}
  \pm 1 & \lambda \\ 0 & 1
\end{pmatrix}
\colon \lambda \in \mathbb R \right\}
\]
is a group with respect to the usual matrix multiplication.  Is it
Abelian?

\item Show that the group of motions of the line is isomorphic to $G$.

\emph{Hint:} Show that the set
\[
L = \left\{
\begin{pmatrix}
  x \\ 1
\end{pmatrix}
\colon x \in \mathbb R \right\}
\]
is invariant under $G$.  

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

\item

A tailor makes jackets and pants.  There is enough demand that she
sells everything she produces.  It takes an hour to make a jacket and
half an hour to make a pair of pants.  She can spare 10 hours per week
for sewing and has a long-running supply contract that provides cloth
for 15 pieces per week altogether.  The profit on a pair of pants is
EUR 15 and the profit on a jacket is EUR 20.  How many pieces of each
per week should she produce to maximize profit?
\hfill(10)
%\newpage

\item Suppose each of the following tableaus occurs in the course of
performing the simplex algorithm on a linear programming problem in
standard form.
\begin{enumerate}
\item\newcolumntype{B}{%
  >{\columncolor[gray]{.8}[.5\tabcolsep]}c}
\begin{tabular}{BcBc|c}
  $x_1$ & $x_2$ & $x_3$ & $x_4$ \\
  \hline
  $0$ & $-1$ & $1$ & $-1$ & $2$  \\
  $1$ & $0$ & $0$ & $2$ & $3$ \\
  \hline
  $0$ & $-1$ & $0$ & $3$ & $4$
\end{tabular}
\item
\begin{tabular}{ccBB|c}
  $x_1$ & $x_2$ & $x_3$ & $x_4$ \\
  \hline
  $0$ & $0$ & $0$ & $1$ & $-1$  \\
  $0$ & $0$ & $1$ & $0$ & $1$ \\
  \hline
  $2$ & $1$ & $0$ & $0$ & $10$
\end{tabular}
\item
\begin{tabular}{cBBc|c}
  $x_1$ & $x_2$ & $x_3$ & $x_4$ \\
  \hline
  $2$ & $1$ & $0$ & $1$ & $0$  \\
  $1$ & $0$ & $1$ & $4$ & $3$ \\
  \hline
  $2$ & $0$ & $0$ & $0$ & $8$
\end{tabular}
\end{enumerate}

State, for each case, whether
\begin{itemize}
\item The feasible region is empty or nonempty;
\item The problem has a finite solution;
\item if so, whether the solution is degenerate or nondegerate.
\end{itemize}
\hfill (10)



%\newpage

\item Let 
\[
  \tilde v_k = \frac1N \sum_{j=0}^{N-1} \e^{-\i k j h} \, v_j
\]
denote the discrete Fourier transform of the complex numbers $v_0,
\dots, v_{N+1}$.

Prove the discrete Parseval identity
\[
\sum_{k=0}^{N-1} \lvert \tilde v_k \rvert^2
  = \frac1N \sum_{j=0}^{N-1} \lvert v_j \rvert^2 .
\]

\hfill(10)
%\newpage

\item Let $G$ be a finite Abelian group of order $N$, and let $\chi$
be a character, i.e., a group homomorphism from $G$ to $\mathbb C
\backslash \{0\}$.  Show that $\chi(a)$ is a root of unity for every
$a \in G$.
\mbox{~~~~}\hfill(10)


%\newpage
%\hfill{}
%\newpage
\end{enumerate}
\end{document}
