Easy PSET Template
Author:
Cameron Cruz
Last Updated:
6년 전
License:
Creative Commons CC BY 4.0
Abstract:
Easy PSET template with examples.
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
Easy PSET template with examples.
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
\documentclass{article}
\usepackage{fancyhdr}
\usepackage{extramarks}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{tikz}
\usepackage[plain]{algorithm}
\usepackage{algpseudocode}
\usetikzlibrary{automata,positioning}
%
% Basic Document Settings
%
\topmargin=-0.45in
\evensidemargin=0in
\oddsidemargin=0in
\textwidth=6.5in
\textheight=9.0in
\headsep=0.25in
\linespread{1.1}
\pagestyle{fancy}
\lhead{\hmwkAuthorName}
\chead{\hmwkClass\ (\hmwkClassInstructor\ \hmwkClassTime): \hmwkTitle}
\rhead{\firstxmark}
\lfoot{\lastxmark}
\cfoot{\thepage}
\renewcommand\headrulewidth{0.4pt}
\renewcommand\footrulewidth{0.4pt}
\setlength\parindent{0pt}
%
% 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{homeworkProblemCounter}
\setcounter{homeworkProblemCounter}{1}
\nobreak\extramarks{Problem \arabic{homeworkProblemCounter}}{}\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.
%
\newenvironment{homeworkProblem}[1][-1]{
\ifnum#1>0
\setcounter{homeworkProblemCounter}{#1}
\fi
\section{Problem \arabic{homeworkProblemCounter}}
\setcounter{partCounter}{1}
\enterProblemHeader{homeworkProblemCounter}
}{
\exitProblemHeader{homeworkProblemCounter}
}
%
% Homework Details
% - Title
% - Due date
% - Class
% - Section/Time
% - Instructor
% - Author
%
\newcommand{\hmwkTitle}{Homework\ \#NUM}
\newcommand{\hmwkDueDate}{DUE DATE}
\newcommand{\hmwkClass}{CLASSNAME}
\newcommand{\hmwkClassTime}{}
\newcommand{\hmwkClassInstructor}{CLASS INSTRUCTOR}
\newcommand{\hmwkAuthorName}{\textbf{AUTHOR}}
%
% Title Page
%
\title{
\vspace{2in}
\textmd{\textbf{\hmwkClass:\ \hmwkTitle}}\\
\normalsize\vspace{0.1in}\small{Due\ on\ \hmwkDueDate}\\
\vspace{0.1in}\large{\textit{\hmwkClassInstructor\ \hmwkClassTime}}
\vspace{3in}
}
\author{\hmwkAuthorName}
\date{}
\renewcommand{\part}[1]{\textbf{\large Part \Alph{partCounter}}\stepcounter{partCounter}\\}
%
% Various Helper Commands
%
% Useful for algorithms
\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}
% Alias for the Solution section header
\newcommand{\solution}{\textbf{\large Solution}}
% Probability commands: Expectation, Variance, Covariance, Bias
\newcommand{\E}{\mathrm{E}}
\newcommand{\Var}{\mathrm{Var}}
\newcommand{\Cov}{\mathrm{Cov}}
\newcommand{\Bias}{\mathrm{Bias}}
\begin{document}
\maketitle
\pagebreak
\begin{homeworkProblem}
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 + 1\), \(g(n) = 2n^3\)
\item \(f(n) = n\sqrt{n} + n^2\), \(g(n) = n^2\)
\item \(f(n) = n^2 - n + 1\), \(g(n) = n^2 / 2\)
\end{enumerate}
\textbf{Solution}
We solve each solution algebraically to determine a possible constant
\(c\).
\\
\textbf{Part One}
\[
\begin{split}
n^2 + n + 1 &=
\\
&\leq n^2 + n^2 + n^2
\\
&= 3n^2
\\
&\leq c \cdot 2n^3
\end{split}
\]
Thus a valid \(c\) could be when \(c = 2\).
\\
\textbf{Part Two}
\[
\begin{split}
n^2 + n\sqrt{n} &=
\\
&= n^2 + n^{3/2}
\\
&\leq n^2 + n^{4/2}
\\
&= n^2 + n^2
\\
&= 2n^2
\\
&\leq c \cdot n^2
\end{split}
\]
Thus a valid \(c\) is \(c = 2\).
\\
\textbf{Part Three}
\[
\begin{split}
n^2 - n + 1 &=
\\
&\leq n^2
\\
&\leq c \cdot n^2/2
\end{split}
\]
Thus a valid \(c\) is \(c = 2\).
\end{homeworkProblem}
\pagebreak
\begin{homeworkProblem}
Let \(\Sigma = \{0, 1\}\). Construct a DFA \(A\) that recognizes the
language that consists of all binary numbers that can be divided by 5.
\\
Let the state \(q_k\) indicate the remainder of \(k\) divided by 5. For
example, the remainder of 2 would correlate to state \(q_2\) because \(7
\mod 5 = 2\).
\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$};
\node[state] (q_2) [right=of q_1] {$q_2$};
\node[state] (q_3) [right=of q_2] {$q_3$};
\node[state] (q_4) [right=of q_3] {$q_4$};
\path[->]
(q_0)
edge [loop above] node {0} (q_0)
edge node {1} (q_1)
(q_1)
edge node {0} (q_2)
edge [bend right=-30] node {1} (q_3)
(q_2)
edge [bend left] node {1} (q_0)
edge [bend right=-30] node {0} (q_4)
(q_3)
edge node {1} (q_2)
edge [bend left] node {0} (q_1)
(q_4)
edge node {0} (q_3)
edge [loop below] node {1} (q_4);
\end{tikzpicture}
\caption{DFA, \(A\), this is really beautiful, ya know?}
\label{fig:multiple5}
\end{figure}
\textbf{Justification}
\\
Take a given binary number, \(x\). Since there are only two inputs to our
state machine, \(x\) can either become \(x0\) or \(x1\). When a 0 comes
into the state machine, it is the same as taking the binary number and
multiplying it by two. When a 1 comes into the machine, it is the same as
multipying by two and adding one.
\\
Using this knowledge, we can construct a transition table that tell us
where to go:
\begin{table}[ht]
\centering
\begin{tabular}{c || c | c | c | c | c}
& \(x \mod 5 = 0\)
& \(x \mod 5 = 1\)
& \(x \mod 5 = 2\)
& \(x \mod 5 = 3\)
& \(x \mod 5 = 4\)
\\
\hline
\(x0\) & 0 & 2 & 4 & 1 & 3 \\
\(x1\) & 1 & 3 & 0 & 2 & 4 \\
\end{tabular}
\end{table}
Therefore on state \(q_0\) or (\(x \mod 5 = 0\)), a transition line should
go to state \(q_0\) for the input 0 and a line should go to state \(q_1\)
for input 1. Continuing this gives us the Figure~\ref{fig:multiple5}.
\end{homeworkProblem}
\begin{homeworkProblem}
Write part of \alg{Quick-Sort($list, start, end$)}
\begin{algorithm}[]
\begin{algorithmic}[1]
\Function{Quick-Sort}{$list, start, end$}
\If{$start \geq end$}
\State{} \Return{}
\EndIf{}
\State{} $mid \gets \Call{Partition}{list, start, end}$
\State{} \Call{Quick-Sort}{$list, start, mid - 1$}
\State{} \Call{Quick-Sort}{$list, mid + 1, end$}
\EndFunction{}
\end{algorithmic}
\caption{Start of QuickSort}
\end{algorithm}
\end{homeworkProblem}
\pagebreak
\begin{homeworkProblem}
Suppose we would like to fit a straight line through the origin, i.e.,
\(Y_i = \beta_1 x_i + e_i\) with \(i = 1, \ldots, n\), \(\E [e_i] = 0\),
and \(\Var [e_i] = \sigma^2_e\) and \(\Cov[e_i, e_j] = 0, \forall i \neq
j\).
\\
\part
Find the least squares esimator for \(\hat{\beta_1}\) for the slope
\(\beta_1\).
\\
\solution
To find the least squares estimator, we should minimize our Residual Sum
of Squares, RSS:
\[
\begin{split}
RSS &= \sum_{i = 1}^{n} {(Y_i - \hat{Y_i})}^2
\\
&= \sum_{i = 1}^{n} {(Y_i - \hat{\beta_1} x_i)}^2
\end{split}
\]
By taking the partial derivative in respect to \(\hat{\beta_1}\), we get:
\[
\pderiv{
\hat{\beta_1}
}{RSS}
= -2 \sum_{i = 1}^{n} {x_i (Y_i - \hat{\beta_1} x_i)}
= 0
\]
This gives us:
\[
\begin{split}
\sum_{i = 1}^{n} {x_i (Y_i - \hat{\beta_1} x_i)}
&= \sum_{i = 1}^{n} {x_i Y_i} - \sum_{i = 1}^{n} \hat{\beta_1} x_i^2
\\
&= \sum_{i = 1}^{n} {x_i Y_i} - \hat{\beta_1}\sum_{i = 1}^{n} x_i^2
\end{split}
\]
Solving for \(\hat{\beta_1}\) gives the final estimator for \(\beta_1\):
\[
\begin{split}
\hat{\beta_1}
&= \frac{
\sum {x_i Y_i}
}{
\sum x_i^2
}
\end{split}
\]
\pagebreak
\part
Calculate the bias and the variance for the estimated slope
\(\hat{\beta_1}\).
\\
\solution
For the bias, we need to calculate the expected value
\(\E[\hat{\beta_1}]\):
\[
\begin{split}
\E[\hat{\beta_1}]
&= \E \left[ \frac{
\sum {x_i Y_i}
}{
\sum x_i^2
}\right]
\\
&= \frac{
\sum {x_i \E[Y_i]}
}{
\sum x_i^2
}
\\
&= \frac{
\sum {x_i (\beta_1 x_i)}
}{
\sum x_i^2
}
\\
&= \frac{
\sum {x_i^2 \beta_1}
}{
\sum x_i^2
}
\\
&= \beta_1 \frac{
\sum {x_i^2 \beta_1}
}{
\sum x_i^2
}
\\
&= \beta_1
\end{split}
\]
Thus since our estimator's expected value is \(\beta_1\), we can conclude
that the bias of our estimator is 0.
\\
For the variance:
\[
\begin{split}
\Var[\hat{\beta_1}]
&= \Var \left[ \frac{
\sum {x_i Y_i}
}{
\sum x_i^2
}\right]
\\
&=
\frac{
\sum {x_i^2}
}{
\sum x_i^2 \sum x_i^2
} \Var[Y_i]
\\
&=
\frac{
\sum {x_i^2}
}{
\sum x_i^2 \sum x_i^2
} \Var[Y_i]
\\
&=
\frac{
1
}{
\sum x_i^2
} \Var[Y_i]
\\
&=
\frac{
1
}{
\sum x_i^2
} \sigma^2
\\
&=
\frac{
\sigma^2
}{
\sum x_i^2
}
\end{split}
\]
\end{homeworkProblem}
\pagebreak
\begin{homeworkProblem}
Prove a polynomial of degree \(k\), \(a_kn^k + a_{k - 1}n^{k - 1} + \hdots
+ a_1n^1 + a_0n^0\) is a member of \(\Theta(n^k)\) where \(a_k \hdots a_0\)
are nonnegative constants.
\begin{proof}
To prove that \(a_kn^k + a_{k - 1}n^{k - 1} + \hdots + a_1n^1 +
a_0n^0\), we must show the following:
\[
\exists c_1 \exists c_2 \forall n \geq n_0,\ {c_1 \cdot g(n) \leq
f(n) \leq c_2 \cdot g(n)}
\]
For the first inequality, it is easy to see that it holds because no
matter what the constants are, \(n^k \leq a_kn^k + a_{k - 1}n^{k - 1} +
\hdots + a_1n^1 + a_0n^0\) even if \(c_1 = 1\) and \(n_0 = 1\). This
is because \(n^k \leq c_1 \cdot a_kn^k\) for any nonnegative constant,
\(c_1\) and \(a_k\).
\\
Taking the second inequality, we prove it in the following way.
By summation, \(\sum\limits_{i=0}^k a_i\) will give us a new constant,
\(A\). By taking this value of \(A\), we can then do the following:
\[
\begin{split}
a_kn^k + a_{k - 1}n^{k - 1} + \hdots + a_1n^1 + a_0n^0 &=
\\
&\leq (a_k + a_{k - 1} \hdots a_1 + a_0) \cdot n^k
\\
&= A \cdot n^k
\\
&\leq c_2 \cdot n^k
\end{split}
\]
where \(n_0 = 1\) and \(c_2 = A\). \(c_2\) is just a constant. Thus the
proof is complete.
\end{proof}
\end{homeworkProblem}
\pagebreak
%
% Non sequential homework problems
%
% Jump to problem 18
\begin{homeworkProblem}[18]
Evaluate \(\sum_{k=1}^{5} k^2\) and \(\sum_{k=1}^{5} (k - 1)^2\).
\end{homeworkProblem}
% Continue counting to 19
\begin{homeworkProblem}
Find the derivative of \(f(x) = x^4 + 3x^2 - 2\)
\end{homeworkProblem}
% Go back to where we left off
\begin{homeworkProblem}[6]
Evaluate the integrals
\(\int_0^1 (1 - x^2) \dx\)
and
\(\int_1^{\infty} \frac{1}{x^2} \dx\).
\end{homeworkProblem}
\end{document}