homework.tex

\documentclass{article}

%
% 引入模板的style文件
%
\usepackage{homework}


%
% 封面
%

\title{
	\includegraphics[scale = 0.45]{images/title/ucas-logo.png}\\
    \vspace{1in}
    \textmd{\textbf{\hmwkClass\ \hmwkTitle}}\\
    \textmd{\textbf{\hmwkSubTitle}}\\
    \normalsize\vspace{0.1in}\small{\hmwkCompleteTime }\\
    \vspace{0.1in}\large{\textit{\hmwkClassInstructor\ }}\\
    \vspace{3in}
}

\author{\hmwkAuthorName \\ 
	\hmwkAuthorStuID}
\date{}

\renewcommand{\part}[1]{\textbf{\large Part \Alph{partCounter}}\stepcounter{partCounter}\\}


%
% 正文部分
%
\begin{document}


\maketitle


\include{chapters/ch01}
%\include{chapters/ch02}
%\include{chapters/ch03}
%\include{chapters/ch04}
%\include{chapters/ch05}


\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}
	伪代码、算法示例，如算法\ref{alg:Reliable Negative Instances Selection}所示：
	
	\begin{algorithm}[H]
		\begin{algorithmic}[1] %每行显示行号
			\Require{Positive Instance Set $ P $, Unlabeled Instance Set $ U $ , Sample Ratio s.}
			\Ensure{Reliable Negative Instance Set $ RN $.}
			
			\State{$set  RN = \emptyset $}
			\State{Sample $ s $ of the instances from $ P $ as $ S $}
			\State{Set $ P_s  = P − S$ with label $ 1 $, $ U_s = U \cup S $ with label $ -1 $}
			\State{Train a classifier $ g $ with $ P_s $ and $ U_s $}
			\State{Classify instances in $ U $ using $ g $, output the class-conditional-probability}
			\State{Select a threshold $ \theta $ according to the class-conditional-probability of
				instances in $ S $}
			\For{$ d \in U $ do}
			\If{$ Pr(1|d) \leq \theta, RN = RN \cup d $}
			\EndIf
			\EndFor
			\State{Output RN}
		\end{algorithmic}
		\caption{Reliable Negative Instances Selection}
		\label{alg:Reliable Negative Instances Selection}
	\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}


\begin{homeworkProblem}
	表格的示例，单元格内换行示例：\\
	
	\begin{tabular}{|c|c|c|c|}
		\hline 
		方法 & 特点 & 优点 & 缺点  \\ 
		\hline 
		有监督学习 & \tabincell{c}{对数据进行标注，\\ 通过有监督学习的方式\\ 来检测恶意URL} & 更强的泛化能力 & \tabincell{l}{现实生活中很难获得\\ 精准的标注数据。\\ 在更多时候，我们可能\\ 只得到一小部分恶意URL\\ 和大量未标记的URL样本，\\ 缺乏足够可靠的负例样本} \\ 
		\hline 
		无监督学习 & 不需要对数据进行标注 & 无需标注的数据即可进行训练 & \tabincell{c}{已知恶意URL的标注信息\\ 就难以充分利用，可能\\ 无法达到令人满意的识别能力} \\
		\hline
	\end{tabular} 
\end{homeworkProblem}


\begin{homeworkProblem}
	插入图片的示例，图片强制在当前位置的示例，如图\ref{fig:ucas-logo}所示：\\
	
	\begin{figure}[H]  % 这里记得用[H]
		\centering
		\includegraphics[width=0.7\linewidth]{images/title/ucas-logo}
		\caption{ucas-logo}
		\label{fig:ucas-logo}
	\end{figure}
	
\end{homeworkProblem}


\begin{homeworkProblem}
	代码的示例：\\
	
\begin{lstlisting}[language = HTML, numbers=left, 
numberstyle=\tiny,keywordstyle=\color{blue!70},
commentstyle=\color{red!50!green!50!blue!50},frame=shadowbox,
rulesepcolor=\color{red!20!green!20!blue!20},basicstyle=\ttfamily]

scheme:[//[user[:password]@]host[:port]][/path][?query][#fragment]


\end{lstlisting}
	
	
\end{homeworkProblem}

\begin{homeworkProblem}
	引用文献示例:\cite{prakash2010phishnet}中提到balabalabalhh
	
	
\end{homeworkProblem}



% 引用文献
\bibliographystyle{unsrt}  % unsrt:根据引用顺序编号
\bibliography{refs}


\end{document}