\documentclass[11pt]{article}
\usepackage{latexsym,amsmath,amsthm,amssymb,fullpage}
\begin{document}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\renewcommand{\O}{\textrm{O}}
\newtheorem{theorem}{Theorem}
\section*{CS 70 homework 4 submission}
Your full name: PUT YOUR NAME HERE
\\
Your login name: PUT YOUR LOGIN NAME HERE
\\
Homework 4
\\
Your section number: PUT YOUR SECTION NUMBER HERE
\\
Your list of partners: LIST THE PEOPLE YOU WORKED WITH HERE (OR ``none'')
\begin{enumerate}
\item
\begin{enumerate}
\item
Prove that $n^2 + 2008 \in \O(n^3)$.
YOUR ANSWER GOES HERE.
\item
Prove that $77 n^3 \lg n \in \O(n^4)$.
YOUR ANSWER GOES HERE.
\item
True or false: There exists $e \in \N$ such that
$2^n \in \O(n^e)$.
Briefly justify your answer.
YOUR ANSWER GOES HERE.
\item
Prove that if $f(n)\in \O(g(n))$ and $g(n)\in \O(h(n))$,
then $f(n)\in \O(h(n))$.
YOUR ANSWER GOES HERE.
\item
Critique the following argument.
Is the reasoning valid? If not, why not?
If there is an error, identify the erroneous step and explain what's wrong with it.
\begin{quote}
We have $n^2 = \O(n^4)$.\\
Also, we have $n^2 = \O(n^3)$.\\
By transitivity, it follows that $\O(n^4)=\O(n^3)$.\\
This means that $n^4 = \O(n^3)$.
\end{quote}
YOUR ANSWER GOES HERE.
\end{enumerate}
\item
%In this problem, we will study a matching problem that is
%somewhat different from the stable marriage problem.
%As before, we have $n$ men and $n$ women, but
%there are no preference lists.
%Instead,
%we have a list of potential couples $(m,w)$ who are considered ``compatible''
%(where $m$ is a man and $w$ a woman).
%The task is to find a pairing of all the men and women,
%subject to the restriction that
%a man and woman can only be paired together if they are compatible.
%
%In other words, we are given a compatibility set $C$,
%where $(m,w)\in C$ means that $(m,w)$ are a compatible couple.
%We say that a pairing is a \emph{compatible pairing} if it is made
%solely out of compatible couples from $C$.
%Given $C$, the goal is to find a compatible pairing.
%(Any such pairing will do.
%Since we don't have preference lists, we don't have to worry
%about stability.)
%
%If $S$ is a set of some number of men,
%let $f(S)$ denote the set of women who are compatible with some
%man in $S$, i.e., $f(S) = \{w : \exists m \in S . (m,w) \in C\}$.
%We'll say that the compatibility set $C$ is \emph{plentiful} if
%for every set $S$ of at most $n$ men, $|f(S)| \ge |S|$.
%(Recall that $|S|$ denotes the \emph{size} of the set $S$,
%i.e., the number of elements it has.)
%We'll say that the compatibility set $C$ is \emph{super-plentiful}
%if for every non-empty set $S$ of at most $n-1$ men, $|f(S)| > |S|$.
%In this problem, you will prove that a compatible pairing exists
%if and only if $C$ is plentiful. (There exist efficient algorithms
%to find such a pairing, if it exists, but they are too complex to
%cover here.)
\begin{enumerate}
\item
%Not every $C$ has a compatible pairing.
Prove that if $C$ has a compatible pairing, then $C$ is plentiful.
YOUR ANSWER GOES HERE.
\item
%Suppose that $C$ is plentiful.
%Let $(a,b)$ be a compatible couple from $C$, i.e., $(a,b) \in C$.
%Suppose that $a$ and $b$ fall madly in love, elope,
%and fly off to Hawaii for their honeymoon.
%We are left with $n-1$ men, $n-1$ women, and the compatibility
%set $C' = \{(m,w) \in C : m\ne a \land w\ne b\}$.
Are we guaranteed that $C'$ is necessarily plentiful?
Briefly justify your answer.
YOUR ANSWER GOES HERE.
\item
%Same as in part 2, except now we are told that
%$C$ is super-plentiful.
Prove that, in this case, $C'$ is guaranteed to be plentiful.
YOUR ANSWER GOES HERE.
\item
Prove that if $C$ is plentiful but not super-plentiful,
then there exists a non-empty set $M$ of men
such that $|f(M)|=|M|$ and $|M|