CS170 - Homework Template
Författare
CS 170 course staff
Last Updated
för 8 år sedan
Licens
Creative Commons CC BY 4.0
Sammanfattning
a helpful LaTeX template for your [CS 170] homework
a helpful LaTeX template for your [CS 170] homework
\documentclass[11pt]{article}
\usepackage{amsmath,textcomp,amssymb,geometry,graphicx,enumerate}
\usepackage{algorithm} % Boxes/formatting around algorithms
\usepackage[noend]{algpseudocode} % Algorithms
\usepackage{hyperref}
\hypersetup{
colorlinks=true,
linkcolor=blue,
filecolor=magenta,
urlcolor=blue,
}
\def\Name{PUT SOMETHING HERE} % Your name
\def\SID{PUT SOMETHING HERE} % Your student ID number
\def\Login{PUT SOMETHING HERE} % Your login (your class account, cs170-xy)
\def\Homework{N} % Number of Homework
\def\Session{Spring 2015}
\title{CS170 -- Fall 2016 --- Homework \Homework}
\author{\Name, SID \SID, \texttt{\Login}}
\markboth{CS170--\Session\ Homework \Homework\ \Name}{CS170--\Session\ Homework \Homework\ \Name, \texttt{\Login}}
\pagestyle{myheadings}
\date{}
\newenvironment{qparts}{\begin{enumerate}[{(}a{)}]}{\end{enumerate}}
\def\endproofmark{$\Box$}
\newenvironment{proof}{\par{\bf Proof}:}{\endproofmark\smallskip}
\textheight=9in
\textwidth=6.5in
\topmargin=-.75in
\oddsidemargin=0.25in
\evensidemargin=0.25in
\begin{document}
\maketitle
Collaborators: PUT SOMETHING HERE (LIST OF YOUR COLLABORATORS, OR WRITE NONE)
\section*{1. First Question}
\begin{qparts}
\item
Your answer to the first part.
\item
Your answer to the second part.
\end{qparts}
\newpage
\section*{Question Asking for an Algorithm}
\textbf{Main idea}\\
Explain, in a few sentences, the key steps of your algorithm, focusing on the (usually) single key insight that would be a total giveaway to the problem if you shared it with a classmate. This is the single most important part of your solution, because if you clearly demonstrate your understanding of the solution here, the readers tend to be more forgiving of small errors elsewhere.\\
\noindent
\textbf{Pseudocode}\\
Write pseudocode for your algorithm here. A fellow CS 170 student should be able to generate working code from your pseudocode. However, the pseudocode itself should not be working code, as this is usually too detailed. Feel free to abstract away basic operations. For example:\\
\begin{algorithmic}[0]
\Procedure{Pokemon Nonsense}{array $P$, height $h$}
\State Set maxHeight := $0$
\For{$p$ in $P$}
\If{height($p$) $>$ maxHeight}
\State Set maxHeight := height($p$)
\Else
\State I wanted to demonstrate an else clause.
\EndIf
\EndFor
\While{There are two Pokemon $p_1$ and $p_2$ in $P$ who haven't been paired up}
\State Pair up $p_1$ and $p_2$.
\EndWhile
\State Set singleHeight := height($p$) if there is an unpaired Pokemon $p$ and 0 otherwise.
\State Return max(singleHeight, maxHeight)
\EndProcedure
\end{algorithmic}
\vspace{0.2in}
\noindent
\textbf{Proof of correctness}\\
See \href{http://www-inst.eecs.berkeley.edu/~cs170/fa14/hws/instruct.pdf}{this detailed explanation} for more details on proofs and the other parts of your answer.\\
\noindent
\textbf{Running time analysis}\\
State your algorithm's runtime and your justification for why it is correct.
\end{document}