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

\def\Var{\operatorname{Var}}

\begin{document}

\title{General Mathematics and Computational Science II}
\author{Final Exam}
\date{May 26, 2007}
\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}

\subsection*{Notation}

\begin{itemize}
\item For $v \in \mathbb C^N$, the discrete Fourier transform of $v$
is defined
\[
  \hat v_k = \frac1N \sum_{j=0}^{N-1} \mathrm e^{-\mathrm i jkh} \, v_j 
\]
with $h = 2\pi/N$ and for $k=0,\dots,N-1$.

\item For $G$ a finite abelian group, written additively and $f \colon
G \to \mathbb C$, the Fourier transform of $f$ is defined
\[
  \hat f(\chi) = \sum_{a \in G} \chi(a) \, f(a)
\]
for $\chi \in \hat G$.
\end{itemize}



\begin{enumerate}

\item Let $H_P$ denote the central reflection about a point $P$ of the
plane. 

Show that $H_A H_B = H_B H_C$ if and only if $B$ is the midpoint of
the line segment $AC$.

\hfill(10)


\item The concept of Eulerian graphs goes back to the famous
``K\"onigsberg bridge problem'': Is it possible to take a walk of
K\"onigsberg such that every bridge in the map below is crossed
exactly once?  Answer this question giving a concise proof.
\begin{center}
\includegraphics[width=6cm]{bridges.eps} \\
\hfill \tiny (Figure from 
\texttt{http://bridges.canterbury.ac.nz/features/bridges.html})
\end{center}
\hfill(10)


\item Solve the linear programming problem
\begin{gather*}
  \text{minimize } z = 5 \, x + 2 \, y 
\intertext{subject to}
  2 \, x + 3 \, y \geq 6 \,, \\
  4 \, x + y \geq 6 \,, \\
  x \geq 0 \,, \\
  y \geq 0 \,,
\end{gather*}
using either the graphical method or the simplex method.
\hfill(10)


\item Show that the leaving variable in one iteration of the simplex
method can never be entering variable in the next iteration.
\hfill(10)


\item Let $M$ be a finite set and let $\operatorname{Sym}(M)$ denote
the permutations of $M$, i.e., the set of bijective maps from $M$ to
itself. 

\begin{enumerate}
\item Show that $\operatorname{Sym}(M)$ is a group whose group
operation is the composition of maps.

\item What is the order, i.e., the number of elements of
$\operatorname{Sym}(M)$?

\item Is $\operatorname{Sym}(M)$ abelian?  Give a proof or state a
counter-example. 

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


\item Let $G$ be a finite group, and let $g \in G$.  
\begin{enumerate}
\item Show that there exists an $n \in \mathbb N$ such that $g^n=e$,
the identity in $G$.
\item The abstract statement of part (a) actually proves something
about the Kac ring model.  What is it?  Explain the correspondence
concisely.
\end{enumerate}
\hfill(8+7)


\item Let $G$ be a finite abelian group, $\psi \in \hat G$ a
character, and $f \colon G \to \mathbb C$ a function on $G$.  Set $g =
\psi f$.

Find an expression for the Fourier transform of $g$ in terms of the
Fourier transform of $f$.
\hfill(10)


\item Let
\[
  u_j =
  \begin{cases}
  1 & \text{if } j \text{ is even} \\
  -1 & \text{if } j \text{ is odd} 
  \end{cases}
\]
and suppose that $N$ is even.  Show that its discrete Fourier
transform satisfies
\[
  \hat u_k =
  \begin{cases}
  1 & \text{if } k = N/2 + mN \text{ for some } m \in \mathbb Z \\
  0 & \text{otherwise} \,.
  \end{cases}
\]
\hfill(15)


\end{enumerate}


\end{document}
