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

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

\begin{document}

\title{General Mathematics and Computational Science II}
\author{Final Exam}
\date{May 25, 2012}
%\date{May 31, 2012}
%\date{September 12, 2012}
\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 Can you draw a path in the plane which crosses each edge of the
following graph exactly once and crosses none of the vertices (marked
as dots)? 
\hfill (10)

\begin{center}
\includegraphics[width=5cm]{graph}
\end{center}

%\item Prove that the figure formed by any number of intersecting circles can
%be drawn with one stroke of the pen.
%\hfill (10)

%\newpage
\item Let $\ell$ denote the line through the origin in the direction
of unit vector $\boldsymbol u$. 

Show that the reflection of a point with coordinates $\boldsymbol p$
about $\ell$ is given by
\[
  R_\ell(\boldsymbol p) = 2 \, \boldsymbol u \, \boldsymbol u^T
  \boldsymbol p - \boldsymbol p \,.
\]
\hfill (10)

%\newpage
\item 
\begin{enumerate}
\item
Show that symmetric group $S_3$, the group of permutations of a
three-element set, and the dihedral group $D_3$, the group of
symmetries of an equilateral triangle, are isomorphic.
\item Are $S_4$ and $D_4$ isomorphic?  

(The symmetric group $S_4$ denotes the group of permutations of a
four-element set and the dihedral group $D_4$ denotes the group of
symmetries of a square.)
\end{enumerate}
\hfill (10+5)

%\newpage
\item Consider the linear programming problem of minimizing
\begin{gather*}
  z = -3 \, x - 2 \, y 
\intertext{subject to }  
  x + 3 \, y \leq 15 \,, \\
  4 \, x + y \leq 16 \,, \\
  x, y \geq 0 \,.
\end{gather*}

\begin{enumerate}
\item Solve this problem \emph{using the simplex method}.
\item Write out the dual problem and solve the dual problem
\emph{using the graphical method}.
\item State the relation you expect between (a) and (b) and verify
that your solution meets your expectation.
\end{enumerate}
\hfill (10+10+5)

%\newpage\mbox{}
%\newpage
\item Assume that $\boldsymbol{x}, \boldsymbol{y} \in \mathbb{R}^n$
are two solutions to the linear programming problem in standard form,
\begin{gather*}
  \text{minimize } \boldsymbol{c}^T \boldsymbol{x} \\
  \text{subject to } A \boldsymbol{x} = \boldsymbol{b} \\
  \text{and } \boldsymbol{x} \geq \boldsymbol{0} \,.
\end{gather*}

Show that any convex combination $\boldsymbol{z} = t \, \boldsymbol{x}
+ (1-t) \, \boldsymbol{y}$ for $ t \in [0,1]$ is also a solution.

\hfill (10)

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

Compute the discrete Fourier transform when $N$ is even and
\[
  v_j =
  \begin{cases}
    1 & \text{for } j < N/2 \,, \\
    0 & \text{otherwise} \,.
  \end{cases}
\]

\emph{Hint:} The case $k=0$ is special, but if you think of your
expression for $\hat v_k$ as being defined for arbitrary $k \in
\mathbb R$, you should find that $\lim_{k \to 0} \hat v_k = \hat v_0$.
(There is no need to compute this, but you may want to use it as a
consistency check.)
\hfill (10)

%\newpage
\item For a nonnegative integer $a$ of at most $N$ decimal digits, let
$a_0, \dots, a_{N-1}$ denote its decimal digits, so that
\[
  a = \sum_{i=0}^{N-1} a_i \, 10^i \,,
\]
likewise for nonnegative integers $b$ and $c$.

\begin{enumerate}
\item Suppose that $c=a \cdot b$, write out an expression for $c_i$ in
terms of $a_i$ and $b_i$, where $i = 0, \dots, N-1$.

\item Given your answer to (a), how can you use the Fast Fourier
Transform to speed up the multiplication of large integers?

\item How should $N$ be chosen such that your proposed algorithm from
part (b) computes a product of integers correctly?

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


\end{enumerate}

%\newpage
%\hfill{}
%\newpage

\end{document}
