\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx, hyperref,varwidth}
\pagestyle{empty}
\newcommand{\st}{~\mid~}
\newcommand{\bAlg}[1]{\begin{center}\begin{varwidth}{\textwidth}
#1
\begin{enumerate}\setlength{\itemsep}{-3pt}}
\newcommand{\eAlg}{\end{enumerate}\end{varwidth}\end{center}}
%\name{}
\assignment{CSE 20 Homework 1}
\duedate{Due: Sunday Jan 15, 2017 at noon}
\begin{document}
\begin{center}
\begin{minipage}[t]{6in}
\rule{\linewidth}{2pt}
{\sc Topics} Algorithms and Integer representations
\newline
{\sc Reading} Rosen Section 3.1: pages 191-194 (up to but not including
Searching Algorithms) and pages 198-201 (except proofs; we'll come back to the proofs in
future weeks), Appendix 3 pages A11-A16;
Section 4.1: pages 237-240 (up to but not including Modular Arithmetic);
Section 4.2: pages 245-253 (up to but not including Modular Exponentiation).
\newline
{\sc Key Concepts} Algorithm, input of algorithm, output of algorithm,
tracing pseudocode given input, higher-level function of an algorithm,
definiteness of algorithms, finiteness (termination) of algorithms,
correctness of algorithms, optimization problem, greedy
approach. Base expansion, decimal expansion, binary expansion,
hexadecimal expansion, octal expansion, bit shift, DIV, MOD.
\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\begin{problem}[1.] ({\bf 10 points}) Consider the following algorithm:
\begin{align*}
&\text{\bf procedure} ~alg1(a,b : ~\text{ positive integers} )\\
&~~~x :=a \\
&~~~y:=b\\
&~~~\text{\bf while}~y \neq 0 \\
&~~~~~~r:= x ~\text{\bf mod}~y \\
&~~~~~~x:= y \\
&~~~~~~y:= r \\
&~~~\text{\bf return}~ x
\end{align*}
\begin{itemize}
\item[(a)] What does $alg1$ return with input $a=50, b=75$?
{\it Note: for full credit, Include enough work to trace the execution of the algorithm on these inputs.
Clearly label the {\bf output} of the algorithm in your answer.)}
\item[(b)] Is this algorithm finite? That is, is its computation guaranteed to terminate
no matter which positive integers are chosen for $a$ and $b$?
{\it Note: for full credit, give your answer (yes or no) and justify it. If your answer is yes,
the justification should explain why the algorithm can't possibly go into an infinite loop no
matter what inputs are chosen (think carefully about the type of the inputs and the loop
condition). If your answer is no, you need to find an example where
the algorithm never returns output because it goes into an infinite loop.)}\\
\end{itemize}
\end{problem}
\begin{problem}[2.] ({\bf 10 points}) Show that if there were a coin worth 9 cents, the greedy algorithm
using quarters, dimes, 9-cent coins, nickels, and pennies would {\bf not always} produce change
using the fewest coins possible. \\
{\it Note: for full credit, you need to find an example where the greedy algorithm does
not produce change using the fewest coins possible, and then describe why this example
works: trace the greedy algorithm
to explain how many coins it would produce in change? what's a better
way to make change using fewer coins?}\\
{\it Second note: for worked examples related to this question,
refer to Week 1 discussion section worksheet.}\\
\end{problem}
\begin{problem}[3.] ({\bf 9 points}) Convert the following numbers as indicated.
Include a sentence of explanation about how you're doing the conversion.
{\it For full credit, the explanation must be a grammatically correct, complete sentence.
For example, in support of a calculation for converting $(101)_2$ to decimal, you
might write: ``$(101)_2 = 1 \cdot 2^2 + 0 \cdot 2 + 1 = (5)_{10}$.
I calculated the value contributed by each column in the binary
representation, using the definition of base expansion, and then added up these
values together."}
\begin{itemize}
\item[a.] $(145)_{10}$ (decimal) to base $2$ (binary).
\item[b.] $(AA)_{16}$ (hexadecimal) to base $8$ (octal).
\item[c.] $(101 1000 0001)_2$ (binary) to base $16$ (hexadecimal).
\end{itemize}
\end{problem}
\begin{problem}[4.] ({\bf 16 points}) In class, we
discussed the Russian Peasant Multiplication (RPM) algorithm. The pseudo-code
implementation of this algorithm is:
\bAlg{{\bf procedure} $RPM(m:~\text{real number}; n:~\text{positive integer})$}
\item $total := 0$
\item $a := m$
\item $b := n$
\item {\bf while} $b > 1$
\item ~~~{\bf if} ($b~{\bf mod}~2 = 1$) {\bf then} $total := total +a$
\item ~~~$a := 2\cdot a$
\item ~~~$b := b~{\bf div}~2$
\item {\bf return} total + a
\eAlg
\begin{itemize}
\item[(a)] Trace (i.e. walk through) an example of the operation of this algorithm when $m=208$
and $n=41$.
{\it Note: for full credit, Include enough work to trace the execution of the algorithm on these inputs.
Clearly label the {\bf output} of the algorithm in your answer.)}
\item[(b)] Convert $m = 208$ and $n=41$ to binary notation.
{\it Note: include the calculations you use in support of your answer. You need not write an explanation
of the conversion for this question.}
\item[(c)] Multiply $m = 208$ and $n = 41$ using the usual school algorithm for long multiplication (but in base $2$
instead of decimal).
{\it Note: include the calculations you use in support of your answer.}
\item[(d)] Convert your answer from part (c) back to decimal, and compare to part (a).
{\it Note: include the calculations you use in support of your answer. You need not write an explanation
of the conversion for this question.}
\item[(e)] Explain how the steps in parts (a) and parts (c) correspond to one another.
{\it For full credit, the explanation must use grammatically correct, complete sentences but
may be short. Make specific reference to RPM (either its English-language description
from class or the pseudocode above) and to the usual-school-algorithm for long multiplication.
}
\end{itemize}
\end{problem}
\begin{problem}[5.] ({\bf 5 points}) This question will help you set up all the tools you need for this class.
{\bf Part 1: Set up all the tools required for this class.}
\begin{itemize}
\item Enroll in the Piazza site for this class:
\url{http://piazza.com/ucsd/winter2017/cse20}.
\item Register your iClicker at
\url{https://www1.iclicker.com/register-clicker/}.
\item Confirm you have access to this class via Gradescope
\url{https://gradescope.com/}
using your \texttt{ucsd.edu} email address. If you do not, post a private Piazza post with your
name, PID, Section (A01, A02, A03, B01, or B02), and UCSD email.
\end{itemize}
{\bf Part 2: Review instructions for all homework assignments for CSE 20}
\begin{itemize}
\item Homework should be done in groups of {\bf one to three} people.
You are free to change group members at any time throughout the quarter.
Problems should be solved together, not divided up between partners.
\item Homework solutions should be neatly written and scanned to PDF or typed and printed to PDF.
Please ensure that your submission is legible (neatly written and not too faint)
or your homework may not be graded. A guide to scanning is at
\url{http://gradescope-static-assets.s3-us-west-2.amazonaws.com/help/submitting_hw_guide.pdf}
\item A {\bf single representative} of your group should
submit your work through Gradescope. The group submission must include
ALL group members' names and PIDs in the top left of each page.
Submission instructions are available
at \url{https://gradescope.com/get_started#student-submission}.
Submissions must be received by the posted time
on the due date, and there are no exceptions to this rule.
\item You may consult your textbook, class notes, lecture slides, instructors, TAs, and tutors
for help with homework. You should not look for answers to homework problems in other texts or sources, including the internet. Only post about graded homework questions on Piazza if you suspect a typo in the assignment, or if you don't understand what the question is asking you to do. Other questions are best addressed in office hours.
\item Your assignments in this class will be evaluated not only on the correctness of your answers, but on your ability to present your ideas clearly and logically. You should always explain how you arrived at your conclusions, using mathematically sound reasoning. Whether you use formal proof techniques or write a more informal argument for why something is true, your answers should always be well-supported. Your goal should be to convince the reader that your results and methods are sound.
\item For questions that require pseudocode, you can follow the same format as the textbook,
or you can write pseudocode in your own style, as long as you specify what your notation means.
For example, are you using ``='' to mean assignment or to check equality? You are welcome to use any algorithm from class as a subroutine in your pseudocode.
\end{itemize}
{\bf To submit}: For full credit for this problem, submit screen-captures of each group member's account logged into Piazza and correctly answer the following three questions:
\begin{itemize}
\item[(a)] If you're stuck on a problem, are you allowed to Google the key phrases in the problem
or look on Wikipedia for background on the problem?
\item[(b)] If the problem statement doesn't explicitly say whether you need to justify your answer or
not, is it okay to give just the final answer (e.g.\ ``42" or ``True") without any explanation of how
you got to the answer?
\item[(c)] If you've registered your iClicker on TritonEd in previous quarters, do you need to register
it again?
\end{itemize}
\end{problem}
\end{document}