\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx, hyperref,varwidth,multicol}
\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 4}
\duedate{Due: Saturday October 28, 2017 at 11pm}
\begin{document}
\begin{center}
\begin{minipage}[t]{6in}
\rule{\linewidth}{2pt}
{\sc Topics} Quantifiers and paradoxes, proof strategies
\newline
{\sc Reading} Rosen Sections 1.1, 1.2, 1.3 (up to page 31), 1.4-1.8, 2.1-2.2.
\newline
{\sc Key Concepts} Predicates, domain of discourse / universe,
existential quantifier, universal quantifier, restricting the domain,
negated quantifiers, nested quantifiers, proof strategies,
counterexample, (constructive) example, direct proof, contrapositive
proof, proof by contradiction.\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\begin{problem}[1.] ({\bf 8 points})
Asymptotic analysis is foundational in many disciplines in Computer Science. At the heart
of asymptotic analysis is big-O notation. Definition 1 on page 205 of big O notation
can be written formally using quantifiers in the following way.
\begin{quote}
Let $f$ and $g$
be functions from the set of integers to the set of real numbers. We say that
$f(x)$ is $O(g(x))$ if
\[
\exists C \exists k \forall x~\left ( x > k ~\to~ |f(x)| \leq C |g(x)| \right)
\]
(where the variables $x$ and $k$ are assumed to be over the set of integers and
the variable $C$ is over the real numbers).
\end{quote}
\begin{itemize}
\item[(a)] Using this definition and our proof strategies for quantified
statements, prove that $2x$ is $O(x^2)$. That is, show that the proposition above
evaluates to true when $f(x) = 2x$ and $g(x) = x^2$.
\item[(b)] Using this definition and our proof strategies for quantified
statements, prove that $x^2$ is {\bf not} $O(2x)$. That is, show that the proposition above
evaluates to false when $f(x) = x^2$ and $g(x) = 2x$.
\end{itemize}
\end{problem}
\begin{problem}[2.] ({\bf 9 points})
For each of the following, determine whether it is true or false and then
prove it (if it true) or disprove it (if it is false). Note that in grading
this question, we will check whether you correctly determined the truth value
for \textbf{each} statement, but we may not grade all three proofs.
\begin{itemize}
\item[(a)] $n^2 - n + 41$ is prime for every non-negative integer $n$.
{\it As a reminder, the definition for prime numbers is on page 257.}
\item[(b)] The ratio (result of division) of any two positive rational numbers is rational.
{\it As a reminder, the definition for rational numbers is on page 85.}
\item[(c)] The sum of any two irrational numbers is irrational.
{\it As a reminder, an irrational number is a real number that is not rational.}
\end{itemize}
{\it Note: in your proofs, you may use known properties of the set of integers (e.g.\
that they are closed under addition, and facts about primes or rational / irrational numbers that
\end{problem}
\begin{problem}[3.] ({\bf 12 points})
Remember the {\bf load balancing problem} from HW1: In computations over multiple processors, the load of a processor is the sum of the times of
all loads assigned to that processor. To balance the computation, the goal is to minimize
the maximum load across the processors. The input to the {\bf load balancing problem} is a list of jobs,
each labelled by the time it would take to complete
that job. The output of the problem is an assignment of a processor to each job.
In this HW, you'll explore the theoretical limits for balancing the load, depending on the
input jobs given. Throughout, assume there are $k$ processors $P_1, \ldots, P_k$
and $n$ jobs $j_1, \ldots, j_n$ where $n$ and $k$ are positive integers.\\
\begin{itemize}
\item[(a)] Find a formula for the biggest theoretical value for
the maximum load of a processor, as a function of the input list of jobs. Justify your formula.
\item[(b)] Is there an algorithm which will always produce an assignment of jobs to processors
that exactly yields this {\bf biggest theoretical maximum load}? If so, give such an algorithm and explain why it has
this property. If not, explain why not.
{\it Note: such an algorithm would *not* do a good job of load balancing.}
\item[(c)] Prove that the minimum maximum load across all processors must be greater than or equal to
\[
\frac{1}{k} \sum_{i=1}^n j_i
\]
{\it Note: recall that this notation indicates $\frac{1}{k} ( j_1 + \cdots + j_n)$}.
\item[(d)] Is there an algorithm which will always produce an assignment of jobs to processors
that exactly yields this {\bf theoretical lower bound} for the smallest maximum load
(i.e. the formula from part (c))? If so, give such an algorithm and explain why it has
this property. If not, explain why not.
\end{itemize}
\end{problem}
\begin{problem}[4.] ({\bf 6 points}) A (simple undirected) {\bf graph} is given by a collection of nodes,
some pairs of which may be connected by edges. For which of the following graphs
is it possible to color each node red or blue in such a way that no two adjacent nodes
(nodes connected by an edge) are assigned the same color. Prove your answers.
\begin{multicols}{2}
\begin{itemize}
\item[(a)] \includegraphics[width=1in]{graph1.png}
\item[(b)] \includegraphics[width=1in]{graph2.png}
\item[(c)] \includegraphics[width=1.5in]{graph3.png}
\item[(d)] \includegraphics[width=1.5in]{graph4.png}
\end{itemize}
\end{multicols}
\end{problem}
\end{document}