CS673-F20-Homework Template
Author
Haden Lee
Last Updated
hace 4 años
License
Creative Commons CC BY 4.0
Abstract
CS673 F20 Homework Template (USF)
CS673 F20 Homework Template (USF)
\documentclass[10pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{latexsym}
\usepackage{graphicx}
\usepackage{comment}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,quotes}
\usepackage{hyperref}
\usepackage{algorithmic}
\usepackage{algorithm2e}
\newtheorem{theorem}{Theorem}
% Do not change the following commands.
\addtolength{\oddsidemargin}{-1.1in}
\addtolength{\evensidemargin}{-1.1in}
\addtolength{\textwidth}{2.2in}
\addtolength{\topmargin}{-1in}
\addtolength{\textheight}{1.4in}
% -------------------------------------
\newcommand{\latex}{\LaTeX\xspace}
\renewcommand{\arraystretch}{1.5}
\begin{document}
\title{CS673-F20-Homework-Template (Change this to Homework 01, e.g.)}
\author{Your Name goes here (Please write your full name here)}
\maketitle
\noindent \textbf{Instructions:}
Please answer the following questions to the best of your ability.
\begin{itemize}
\item Please read each problem's statement carefully to determine what you need to write in your answer.
\item \textbf{Cite any sources you reference} including textbook, whatever you find on the Internet, etc. A failure to cite the sources can result in an F in the course grade as it violates the Honor Code.
\item If you have any questions about \latex, please search the Internet (using your favorite search engine!) before asking on Piazza.
\end{itemize}
\section{Answer to Problem 1}
Write your answer to Problem 1 here.
You will find this quick introduction to \latex useful:
\href{https://www.youtube.com/watch?v=NXW4cbHBthY}{A link to a YouTube video (this text is a hyperlink)} .
As an example, you can use the in-line math mode as follows: $\forall x \in \mathbf{N}$, $x < x+1$ always holds.
For a longer equation, you can do something like this (and give it a unique label):
\begin{equation}\label{eqn:my_first_eqn}
\sum_{i=1}^{n} i = \frac{n \cdot (n+1)}{2}
\end{equation}
You can refer to your equation like this: Equation \ref{eqn:my_first_eqn}.
In addition, a series of inequalities or equations could be useful. Let's prove the formula above using induction.
Statement: $\sum_{i=1}^{n} i = \frac{n \cdot (n+1)}{2}$ for all integers $n \geq 1$.
Base case: When $n = 1$, the equation trivially holds.
Inductive Hypothesis: Suppose that Equation \ref{eqn:my_first_eqn} is true for some integer $k \geq 1$. We will prove for the case $n = k+1$.
By expanding the summation, we can re-write the left-hand-side as follows:
\begin{eqnarray}
\sum_{i=1}^{k+1} i
&=& \left(\sum_{i=1}^{k} i \right) + (k+1) \label{eqn:simplify} \\
&=& \frac{k \cdot (k+1)}{2} + (k+1) \label{eqn:inductive}\\
&=& \frac{(k+1)(k+2)}{2}
\end{eqnarray}
Notice that from Equation~\ref{eqn:simplify} to Equation~\ref{eqn:inductive}, we are applying the Inductive Hypothesis.
If you want to draw a diagram or a graph, using \texttt{tikz} package would be the best. Here is an example:
\begin{figure}[!h]
\begin{tikzpicture}[scale=0.85]
\tikzstyle{every node}=[draw,shape=circle];
\draw (7.5,1) node[draw=none] {~};
\path (10,2) node (s) {$s$};
\path (22,2) node (t) {$t$};
\path (13,3.5) node (A) {\small $A$};
\path (13,2) node (B) {\small $B$};
\path (13,0.5) node (C) {\small $C$};
\path (16,3.5) node (P) {\small $P$};
\path (16,2) node (Q) {\small $Q$};
\path (16,0.5) node (R) {\small $R$};
\path (19,3.5) node (X) {\small $X$};
\path (19,2) node (Y) {\small $Y$};
\path (19,0.5) node (Z) {\small $Z$};
\draw[->,thick] (s) edge (A) (s) edge (B) (s) edge (C);
\draw[->,thick] (A) edge (P) (P) edge (X) (X) edge (t);
\draw[->,thick] (B) edge (Q) (Q) edge (Y) (Y) edge (t);
\draw[->,thick] (C) edge (R) (R) edge (Z) (Z) edge (t);
\draw[->,thick] (C) edge (Q) (Q) edge (X);
\draw (11.7,3.2) node[draw=none] {1/3}; % s-A
\draw (11.7,2.2) node[draw=none] {2/4}; % s-B
\draw (11.7,0.8) node[draw=none] {2/5}; % s-C
\draw (14,3.7) node[draw=none] {1/3}; % A-P
\draw (14,2.2) node[draw=none] {2/3}; % B-Q
\draw (14,0.2) node[draw=none] {1/3}; % C-R
\draw (14.8,1.15) node[draw=none] {1/3}; % C-Q
\draw (18,3.7) node[draw=none] {1/2}; % P-X
\draw (17.1,2.8) node[draw=none] {2/2}; % Q-X
\draw (18,2.2) node[draw=none] {1/4}; % Q-Y
\draw (18,0.2) node[draw=none] {1/4}; % R-Z
\draw (20.3,3.2) node[draw=none] {3/4}; % X-t
\draw (20.3,2.2) node[draw=none] {1/4}; % Y-t
\draw (20.3,0.8) node[draw=none] {1/4}; % Z-t
\end{tikzpicture}
\end{figure}
You can also include an image (PNG file is preferred) using the \texttt{includegraphics} command. Search the Internet to learn how to use it.
\section{Answer to Problem 2}
Let's say you want to include pseudocode as a part of your answer.
Note that it's often useful to mix your code and explanations to concisely describe what your algorithm is supposed to do.
% By the way, to comment any particular line, use '%'.
\begin{algorithm}[H]{\texttt{Dummy}($l, r$) // Invariant: $0 \leq l < r \leq n$.}
\small
\begin{algorithmic}[1]
\STATE $m \gets $\texttt{RANDOM}($l,r$) // Returns an integer from $[l,r)$, uniformly at random.
\STATE $v \gets m^2$
\STATE $w \gets \lfloor m / 2 \rfloor$
\IF{$v < w$}
\RETURN{``Whaaat''}
\ELSIF{$x = v$}
\RETURN{``Huh''}
\ELSE
\RETURN{``Of Course!''}
\ENDIF
\end{algorithmic}
\end{algorithm}
Sometimes you will be asked to prove a statement.
You can use the Theorem-proof environment like below.
\begin{theorem}
For any natural number $n \in \mathbf{N}$ (in other words, $n \geq 1$ and $n \in \mathbf{Z}$, if $n^2$ is an even number, then $n$ must be an even number as well.
\end{theorem}
\begin{proof}
We will prove the contrapositive of the statement: If $n$ is NOT an even number (that is, $n$ is an odd number), then $n^2$ must NOT be an even number (that is, $n^2$ must be an odd number).
Let $n$ be an odd number, which can be written as $n = 2k + 1$ for some integer $k \geq 0$.
Then, $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2\cdot (2k^2 + 2k) + 1$, which implies that $n^2$ is also an odd number.
\end{proof}
Here is another way to prove the same theorem using contradiction.
\begin{proof}[Alternative proof]
Suppose that $n^2$ is an even number but $n$ is an odd number (which would lead to a contradiction).
Since $n$ is an odd number, we can write it as $n = 2k + 1$ for some integer $k \geq 0$.
Then, $n^2 = 2 \cdot (2k^2 + 2k) + 1$ which is an odd number -- this is a contradiction because $n^2$ is assumed to be an even number. Therefore, $n$ must be an even number.
\end{proof}
\section{Answer to Problem 3}
Some question may have sub-problems, and it will be useful to use the \texttt{enumerate} environment.
\begin{enumerate}
\item \textbf{Subtask (1)} My answer is 42.
\item \textbf{Subtask (2)} No, I would not do that.
\item \textbf{Subtask (3)} Yes, absolutely.
\end{enumerate}
\section*{References}
If you need to cite any sources, please do so here.
Recall that your answers must be in your own writing/typing (i.e., you should not copy-and-paste anything word-for-word).
\begin{enumerate}
\item In my answer to Problem 1, I used Theorem 5.x and Lemma 5.y in KT.
\item In my answer to Problem 2, I got an idea from this StackOverflow post: (provide a URL here).
\item In my answer to Problem 3-1, I learned the answer from the movie, ``The Hitchhiker's Guide to the Galaxy.''
\end{enumerate}
\end{document}