Homework.tex

%%%%%%%%%%%%%%%%%%
% Based on https://github.com/jdavis/latex-homework-template
%%%%%%%%%%%%%%%%%%

\documentclass{article}

\usepackage{fancyhdr}
\usepackage{extramarks}

\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}

\usepackage{tikz}
\usepackage[plain]{algorithm}
\usepackage{algpseudocode}

\usetikzlibrary{automata,positioning}

\usepackage{wrapfig}

\usepackage{lipsum}

%for urls
\usepackage{hyperref}
\hypersetup{
	colorlinks = true,
	linkcolor = teal,
	anchorcolor = teal,
	citecolor = teal,
	filecolor = teal,
	urlcolor = teal
}

\usepackage{booktabs, tabularx}
\usepackage{stfloats}

%%%%%% Basic Document Settings %%%%%%%%%

\topmargin=-0.45in
\evensidemargin=0in
\oddsidemargin=0in
\textwidth=6.5in
\textheight=9.0in
\headsep=0.25in

\linespread{1.1}

%%%%%%%%%%%%%%%%%% Homework Details %%%%%%%%%%%%%%%
% University Seal
% Title
% Due date
% University
% Class
% Instructor
% Author
% Author ID 
\newcommand{\hmwkSeal}{images/logo.png}
\newcommand{\hmwkTitle}{Homework Set\ \#17}
\newcommand{\hmwkDueDate}{March 14, 3141}
\newcommand{\hmwkClass}{Course Title (CS-3.14) }
\newcommand{\hmwkClassInstructor}{Professor Augustin-Louis Cauchy}
\newcommand{\hmwkUniversity}{University of Crete \\Department of Computer Science}
\newcommand{\hmwkAuthorName}{John Doe}
\newcommand{\hmwkAuthorID}{ID XXXX}


%fancyhdr
\pagestyle{fancy}
\lhead{\hmwkAuthorName\ (\hmwkAuthorID)} %left head
%\chead{\hmwkClass\ \hmwkTitle} %center head
%\rhead{\date{\today}} %right head
\rhead{\hmwkClass\ \hmwkTitle} 
\lfoot{\lastxmark}
\cfoot{\thepage}

\renewcommand\headrulewidth{0.4pt}

% Create Problem Sections %

\newcommand{\enterProblemHeader}[1]{
	\nobreak\extramarks{}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
	\nobreak\extramarks{Problem \arabic{#1} (continued)}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
}

\newcommand{\exitProblemHeader}[1]{
	\nobreak\extramarks{Problem \arabic{#1} (continued)}{Problem \arabic{#1} continued on next page\ldots}\nobreak{}
	\stepcounter{#1}
	\nobreak\extramarks{Problem \arabic{#1}}{}\nobreak{}
}

\setcounter{secnumdepth}{0}
\newcounter{partCounter}
\newcounter{exerciseCounter}
\setcounter{exerciseCounter}{1}
\nobreak\extramarks{Problem \arabic{exerciseCounter}}{}\nobreak{}

% Homework Problem Environment %
% This environment takes an optional argument. When given, it will adjust the problem counter. This is useful for when the problems given for your
% assignment aren't sequential. See the last 3 problems of this template for an example.
%

\newcommand{\enterExerciseHeader}[1]{
	\nobreak\extramarks{}{Exercise \arabic{#1} continued on next page\ldots}\nobreak{}
	\nobreak\extramarks{Exercise \arabic{#1} (continued)}{Exercise \arabic{#1} continued on next page\ldots}\nobreak{}
}

\newcommand{\exitExerciseHeader}[1]{
	\nobreak\extramarks{Exercise \arabic{#1} (continued)}{Exercise \arabic{#1} continued on next page\ldots}\nobreak{}
	\stepcounter{#1}
	\nobreak\extramarks{Exercise \arabic{#1}}{}\nobreak{}
}

\newenvironment{Exercise}[1][-1]{
	\ifnum#1>0
	\setcounter{exerciseCounter}{#1}
	\fi
	\section{Exercise \arabic{exerciseCounter}}
	\setcounter{partCounter}{1}
	\enterExerciseHeader{exerciseCounter}
}{
	\exitExerciseHeader{exerciseCounter}
}

% Title Page %
\title{
	\centering
	\includegraphics[height=1.5in]{\hmwkSeal}
	
	\vspace{1in}
	\textmd{\textbf{\hmwkClass\ \hmwkTitle}}\\
	
	\normalsize\vspace{0.1in}\small{Due\ on\ \hmwkDueDate}\\
	
	\vspace{0.1in}
	\large{\textit{\hmwkClassInstructor}} \\
	\vspace{0.5in}
	
	\large{\hmwkUniversity}
	
	\vspace{3in}
	
	\author{\textbf{\hmwkAuthorName} (\hmwkAuthorID)}
	\date{\today}
}

% Various Helpers %
\newcommand{\alg}[1]{\textsc{\bfseries \footnotesize #1}}
% For derivatives
\newcommand{\deriv}[1]{\frac{\mathrm{d}}{\mathrm{d}x} (#1)}
% For partial derivatives
\newcommand{\pderiv}[2]{\frac{\partial}{\partial #1} (#2)}
% Integral dx
\newcommand{\dx}{\mathrm{d}x}
\newcommand{\E}{\mathbb{E}}
\newcommand{\Var}{\mathrm{Var}}
\newcommand{\Cov}{\mathrm{Cov}}
\newcommand{\Bias}{\mathrm{Bias}}

\def\code#1{\texttt{#1}}

%for code listings
\usepackage{listings}
\usepackage{xcolor}

\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.99,0.99,0.99}

\lstdefinestyle{mystyle}{
	backgroundcolor=\color{backcolour},   
	commentstyle=\color{codegreen},
	keywordstyle=\color{magenta},
	numberstyle=\tiny\color{codegray},
	stringstyle=\color{codepurple},
	basicstyle=\ttfamily\footnotesize,
	breakatwhitespace=false,         
	breaklines=true,                 
	captionpos=b,                    
	keepspaces=true,                 
	numbers=left,                    
	numbersep=5pt,                  
	showspaces=false,                
	showstringspaces=false,
	showtabs=false,                  
	tabsize=2
}

\lstset{style=mystyle}

\begin{document}
	
	\maketitle
	
	\pagebreak
	
	\begin{Exercise}
    Give an appropriate positive constant $c$ such that $f(n) \leq c \cdot g(n)$ for all $n > 1$.

    \begin{enumerate}
        \item $f(n) = n^2 + n + 5$, $g(n) = 3n^2$
        \item $f(n) = n\sqrt{n} + n^2$, $g(n) = n^2$
        \item $f(n) = n^2 - n$, $g(n) = n^2 / 2$
    \end{enumerate}

    \textbf{Solution} \\


    \textbf{Part One}

    \[
        \begin{split}
            n^2 + n + 5 &=
            \\
            &\leq n^2 + n^2 + n^2
            \\
            &= 3n^2
            \\
            &\leq c \cdot 3n^2
        \end{split}
    \]

    choose $c = 1$.
    \\

    \textbf{Part Two}

    \[
        \begin{split}
            n\sqrt{n} + n^2 &=
            \\
            &= n^{3/2} + n^2
            \\
            &\leq n^{4/2} + n^2
            \\
            &= 2n^2
            \\
            &\leq c \cdot n^2
        \end{split}
    \]

    choose $c = 2$.
    \\

    \textbf{Part Three}

    \[
        \begin{split}
            n^2 - n &=
            \\
            &\leq n^2
            \\
            &\leq c \cdot \frac{n^2}{2}
        \end{split}
    \]

    again choose $c = 2$.

\end{Exercise}

\pagebreak

\begin{Exercise}
    Let $\Sigma = \{0, 1\}$. Construct a DFA $A$ that recognizes all binary numbers with even number of ones. \\
    
    \textbf{Solution} \\

    Let $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$ be the desired automaton, and let $Q = \left\{ q_0, q_1 \right\}$ where state $q_0$ corresponds to a binary number with even number of ones and $q_1$ the vase of odd number of ones. We obviously have $\Sigma = \left\{ 0,1 \right\}$ and $F=\left\{ q_0 \right\}$. 

    \begin{figure}[h]
        \centering
        \begin{tikzpicture}[shorten >=1pt,node distance=2cm,on grid,auto]
            \node[state, accepting, initial] (q_0)   {$q_0$};
            \node[state] (q_1) [right=of q_0] {$q_1$};
            \path[->]
                (q_0)
                    edge [loop above] node {0} (q_0)
                    edge [bend right=+30] node {1} (q_1)
                (q_1)
                    edge [loop above ] node {0} (q_1)
                    edge [bend left=-30] node {1} (q_0);
        \end{tikzpicture}
        \caption{The DFA $\mathcal{A}$}
        \label{fig:multiple5}
    \end{figure}

If $A$ is in state $q_0$, inputting 1 transists to state $q_1$, while by having even number of ones (state $q_0$), inputting 1 does not result in a change of state etc, as in Figure~\ref{fig:multiple5}. Hence the transition matrix of $\delta$ is 

    \begin{table}[ht]
        \centering
        \begin{tabular}{c || c | c | c | c | c}
        	$\delta$
            & $0$
            & $1$  
            \\
            \hline
            $q_0$ & $q_0$ & $q_1$ \\
            $q_1$ & $q_1$ & $q_0$ \\
        \end{tabular}
    \end{table}

Therefore a word $w \in \left\{ 0,1 \right\}^{\star}$ is recognizable by $\mathcal{A}$ if-f $ \delta^\star (q_0, w) = q_0$, which is exactly when $w$ consists of an even number of ones.

\end{Exercise}

\pagebreak

\begin{Exercise}
    Write a pseudocode for the \alg{Insertion-Sort} algorithm. \\
    
    \textbf{Solution} \\
    
    \begin{algorithm}[]
        \begin{algorithmic}[1]
            \Function{Insertion-Sort}{Array A}
                \State{} $i=1$
                \While{$i < \text{length(A)}$}
                \State{} $j=i$
                \While{$j > 0$ and $A[j-1] > A[j]$}
                \State{}$\text{swap}(A[j],A[j-1])$
                \State{} $j \leftarrow j - 1$
                \EndWhile{}
                \State{} $i \leftarrow i + 1$
                \EndWhile{}
            \EndFunction{}
        \end{algorithmic}
        \caption{Insertion-Sort}
    \end{algorithm}
\end{Exercise}

\pagebreak

\begin{Exercise}
    Given a first order linear regression $Y_i = \beta_0 + \beta_1 x_i + e_i$ with $i = 1, \ldots, n$, $\E [e_i] = 0$, with $\Var [e_i] = \sigma^2_e$ and $\Cov[e_i, e_j] = 0, \forall i \neq j$, where $\epsilon_i$ is an error term. Obtain the least squares estimators (LSE) $\hat{\beta_0}$, $\hat{\beta_1}$.

    \begin{proof}

    \item We should minimize the Residual Sum of Squares (RSS):

    \[
            RSS = \sum_{i = 1}^{n} {(Y_i - \hat{Y_i})}^2 = \sum_{i = 1}^{n} {(Y_i - \hat{\beta_0} - \hat{\beta_1} x_i)}^2
    \]

    taking the partial derivatives with respect to $\hat{\beta_0}$ and $\hat{\beta_1}$ , we get:
    	
    \[
    \pderiv{
    	\hat{\beta_0}
    }{RSS}
    = -2 \sum_{i = 1}^{n} {(Y_i - \hat{\beta_0} - \hat{\beta_1} x_i)}
    \]
    
    \[
        \pderiv{
            \hat{\beta_1}
        }{RSS}
        = -2 \sum_{i = 1}^{n} {x_i (Y_i - \hat{\beta_0} - \hat{\beta_1} x_i)}
    \]
    
    which means
    
    \begin{equation}
    	\sum_{i = 1}^{n} {(Y_i - \hat{\beta_0} - \hat{\beta_1} x_i)} = 0 
    \end{equation}
    
    \begin{equation}
    	\sum_{i = 1}^{n} {Y_ix_i- \hat{\beta_0}x_i - \hat{\beta_1} x_i^2)} = 0 
    \end{equation}

    Expanding the sums and solving for $\hat{\beta_0}$ and $\hat{\beta_1}$ we obtain \[ \hat{\beta_0} = \overline{Y} - \hat{\beta_1}\overline{x} \]

    \begin{equation}
        \begin{split}
            \hat{\beta_1}
            &= \frac{
                \sum_{i=1}^{n} {x_i Y_i} - \frac{\sum_{i=1}^{n}x_i \sum_{i=1}^{n} Y_i}{n} 
            }{
                \sum_{i=1}^{n} x_i^2 - \frac{\left( \sum_{i=1}^{n} x_i \right)^2}{n}
            }
        \end{split}
    \end{equation}
    
\end{proof}
\end{Exercise}

\pagebreak

\begin{Exercise} Prove \textit{Liouville's Theorem}: Every bounded entire function in the complex plane $\mathbb{C}$ is constant (every holomorphic function $f$ for which there exists $M > 0$ such that $|f(z)| \leq M ~\forall z \in \mathbb{C}$ is constant).
	
	\begin{proof} Let $f$ be an entire function. Then it can be represented by its Taylor series around zero: 
		
		$$f(z) = \sum_{k=0}^\infty a_k z^k$$
		
		by Cauchy's integral formula:
		
		\[
		a_k = \frac{f^{(k)}(0)}{k!} = {1 \over 2 \pi i} \oint_{C_r} \frac{f( \zeta )}{\zeta^{k+1}}\,d\zeta
		\]
		
		where $C_r$ is the positively oriented circle around 0 of radius $r >0$. Suppose $f$ is bounded: i.e. there exists a positive constant $M$ such that $|f(z)| \leq M ~\forall z$. Then
		
		  \[
		\begin{split}
		| a_k | 
		&\le \frac{1}{2 \pi} \oint_{C_r} \frac{ | f ( \zeta ) | }{ | \zeta |^{k+1} } \, |d\zeta| \\
		&\le \frac{1}{2 \pi} \oint_{C_r} \frac{ M }{ r^{k+1} } \, |d\zeta| \\
		&= \frac{M}{2 \pi r^{k+1}} \oint_{C_r} |d\zeta| \\
		&= \frac{M}{2 \pi r^{k+1}} 2 \pi r \\
		&= \frac{M}{r^k} \\
		&\rightarrow 0
    	\end{split}
        \]
		
		as $r$ goes to infinity (since f is analytic on the entire compelx plane). Hence $a_k = 0 ~\forall k \geq 1$. Thus $f(z) = a _0$.
	\end{proof}
\end{Exercise}

\begin{Exercise}Prove the fundamental theorem of algebra using Liouville's Theorem. 
\end{Exercise}

\pagebreak
	
	\begin{Exercise}
		Show that any prime $p>3$ is next to a multiple of 6. \\
		
		\begin{proof}
		We equivalently show that every prime $p>3$ is either $p \equiv 1\text{mod}6$ or $p \equiv -1\text{mod}6 \equiv 5\text{mod}6$, that is, of the form $p = 6n + 1$ or $p=6n + 5$. By Euclidean division, every integer is of the form $n = 6q + r$ where $q$ is non-negative integer and $r =0,1,\ldots,5, ~r \leq q$. If $p$ is of of the form $6q$ or $6q+2$ or $6q+4$, then p is even, therefore not prime. If $p$ is of the form $6q+3$, then $q$ is divisible by 3 and greater than 3, and therefore not prime. The above leaves as the only candidates for primality greater than 3 integers of the form $p = 6q+1$ and $p = 6q+5 = 6(q+1) -1$. In fact, by Dirichlet's Theorem an arithmetic progression $an + b, ~n=1,2,\hdots$ generates infinitely many primes if-f $(a,b)=1$\footnote{\url{https://mathworld.wolfram.com/DirichletsTheorem.html}}.
	
    	\end{proof}

	\end{Exercise}

    \begin{Exercise}
    	In a bin there are 6 black socks and 4 blue socks. If you select two socks at random, find the probability that you select two socks of the same color. \\
    	
    	\textbf{Solution} \\
    	
    	Picking two socks of the same color means picking either two black or two blue socks. The probability of picking the first black sock is $6/10$ and $5/9$ for picking the second black sock due to sampling without replacement. So the probability of picking a black pair is $\frac{6}{10}*\frac{5}{9} = \frac{1}{3}$. Similarly, the probability of picking a blue pair is $\frac{2}{15}$. Total probability of picking a pair of black or red socks is $p=\frac{1}{3} + \frac{2}{15} = \frac{7}{15}$. Another solution using binomial coefficients instead of counting yields 
    	
    	\[
    	\frac{\binom{6}{2}}{\binom{10}{2}} + \frac{\binom{4}{2}}{\binom{10}{2}} = \frac{21}{45} = \frac{3}{15}
    	\]
    	
    \end{Exercise}

	% Non sequential homework problems
	\begin{Exercise}[224]
		Evaluate $\displaystyle \sum_{k=1}^{5} k^2$ and $\displaystyle \sum_{k=1}^{5} (k - 1)^2$.
	\end{Exercise}
	
	% Continue counting
	\begin{Exercise}
		Find the derivative of $f(x) = x^4 + 3x^2 - 2$.
	\end{Exercise}
	
	% Go back to where we left off
	\begin{Exercise}[9]
		Evaluate the integrals
		$\displaystyle \int_0^1 (1 - x^2) \dx$ and $\displaystyle \int_1^{\infty} \frac{1}{x^2} \dx$.
	\end{Exercise}

	\begin{Exercise}
		Find the derivative of $\alpha^{x}, ~a \in \mathbb{N}$. \\
		
		\textbf{Solution} \\
		
		Rewrite $\alpha^{x} \equiv e^{\ln \alpha^{x}}$, hence $e^{\ln \alpha^{x}} = e^{x\ln \alpha}$. Differentiating with respect to x, we obtain  
		
		\[
		\frac{d}{dx} e^{x\ln \alpha} = \ln (\alpha) e^{x\ln \alpha} = \ln (\alpha) \alpha^x
		\]
		
	\end{Exercise}
	
	\begin{Exercise}[243]
		Prove Goldbach's conjecture, that every even integer greater than 2 is the sum of two prime numbers.
	\end{Exercise}
	
	\begin{Exercise}[250] Prove the Riemann Hypothesis.
	\end{Exercise}
	
\end{document}