\PassOptionsToPackage{unicode=true}{hyperref} % options for packages loaded elsewhere
\PassOptionsToPackage{hyphens}{url}
%
\documentclass[]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{textcomp} % provides euro and other symbols
\else % if luatex or xelatex
\usepackage{unicode-math}
\defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage[]{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\usepackage{hyperref}
\hypersetup{
pdfborder={0 0 0},
breaklinks=true}
\urlstyle{same} % don't use monospace font for urls
\setlength{\emergencystretch}{3em} % prevent overfull lines
\providecommand{\tightlist}{%
\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{0}
% Redefines (sub)paragraphs to behave more like sections
\ifx\paragraph\undefined\else
\let\oldparagraph\paragraph
\renewcommand{\paragraph}[1]{\oldparagraph{#1}\mbox{}}
\fi
\ifx\subparagraph\undefined\else
\let\oldsubparagraph\subparagraph
\renewcommand{\subparagraph}[1]{\oldsubparagraph{#1}\mbox{}}
\fi
% set default figure placement to htbp
\makeatletter
\def\fps@figure{htbp}
\makeatother
\date{}
\begin{document}
\hypertarget{cs-121-homework-zero-fall-2018}{%
\section{CS 121 Homework Zero: Fall
2018}\label{cs-121-homework-zero-fall-2018}}
This problem set is to ensure you are up to date with the mathematical
background needed to be successful in CS 121. Unlike future problem
sets, \textbf{you can collaborate freely with other students on this
problem set as long as you list your collaborators below}.
This problem set is due \textbf{Thursday September 6, 2018 11:59pm} on
but I encourage you to work on it during the summer. There are no late
days for this problem set, but it is OK if you don't submit it - it is
\textbf{optional} in the sense that it only adds to the numerator, and
not the denominator, of the calculation of the final pset average.
You can submit this problem set in \emph{pairs}.
\hypertarget{some-policies}{%
\subsubsection{Some policies}\label{some-policies}}
(See the \href{http://cs121.boazbarak.org/syllabus/}{course syllabus}
for the full policies.)
\begin{itemize}
\item
Sharing questions or solutions with anyone outside this course,
including posting on outside websites, is a violation of the honor
code policy.
\item
Since I encourage you to work on this during the summer, in this pset
you are allowed to collaborate with any other students, as long as you
list their names. Future psets will have stricter collaboration
policies. However, you and your partner must write up solutions
yourselves.
\item
The submitted PDF should be typed and in the same format and
pagination as ours. Please include the questions text and below the
text of Problem X use \textbf{Solution X:} for your solution. (This is
easy to do if you use our markdown template.) Please mark in
gradescope the pages where your solution to each question appears.
Points will be deducted if you submit in a different format.
\end{itemize}
\textbf{By writing my name here I affirm that I am aware of all policies
and abided by them while working on this problem set:} (list both your
names here)
Please write the names of yourself and your collaborators below (this
page does not contain any solutions, and so is not viewed by the people
grading your problems on gradescope.)
\textbf{Submitters (pairs):} (List your names and HUIDs here)
\textbf{Collaborators:} (List here anyone you discussed problems or
ideas for solutions with)
\newpage
\hypertarget{questions}{%
\subsection{Questions}\label{questions}}
Please solve the following problems. Some of these might be harder than
the others, so don't despair if they require more time to think or you
can't do them all. Just do your best. Also, you should only attempt the
bonus questions if you have the time to do so. If you don't have a proof
for a certain statement, be upfront about it. You can always explain
clearly what you are able to prove and the point at which you were
stuck. Also, for a non bonus question, you can always simply write
\textbf{``I don't know''} and you will get 15 percent of the credit for
this problem.
The Piazza board for this course is already active! If you are stuck on
this problem set, you can use Piazza to send a private message to all
instructors under the \texttt{e-office-hours} folder.
\textbf{Problem 0 (5 points):} Read fully the \textbf{Mathematical
Background Chapter} (
\href{https://introtcs.org/public/lec_00_1_math_background.pdf}{pdf
format}
\href{https://introtcs.org/public/lec_00_1_math_background.html}{html
format} ) from the textbook on the website \url{https://introtcs.org}.
\textbf{Solution 0:} (If submitting alone write ``I certify that I fully
read the chapter'', if submitting in a pair write ``We certify that each
one of us fully read the chapter''. I will assume you know all the
contents of that chapter in the rest of the course.)
\hypertarget{logical-operations-sets-and-functions}{%
\subsubsection{Logical operations, sets, and
functions}\label{logical-operations-sets-and-functions}}
These questions assume familiarity with strings, functions, relations,
sets, and logical operators. We use an indexing from zero convention,
and so given a length \(n\) binary string \(x\in \{0,1\}^n\), we denote
coordinates of \(x\) by \(x_0,\ldots,x_{n-1}\). We use \([n]\) to denote
the set \(\{0,1,\ldots,n-1\}\).
\textbf{Question 1 (3 points):} Write a logical expression
\(\varphi(x)\) involving the variables \(x_0,x_1,x_2\) and the operators
\(\wedge\) (AND), \(\vee\) (OR), and \(\neg\) (NOT), such that
\(\varphi(x)\) is true if and only if the majority of the inputs are
\emph{True}.
\textbf{Solution 1:}
\textbf{Question 2:} Use the logical quantifiers \(\forall\) (for all),
\(\exists\) (exists), as well as \(\wedge,\vee,\neg\) and the arithmetic
operations \(+,\times,=,>,<\) to write the following:
\textbf{Question 2.1 (3 points):} An expression \(\psi(n,k)\) such that
for every natural numbers \(n,k\), \(\psi(n,k)\) is true if and only if
\(k\) divides \(n\).
\textbf{Solution 2.1:}
\textbf{Question 2.2 (3 points bonus):} An expression \(\varphi(n)\)
such that for every natural number \(n\), \(\varphi(n)\) is true if and
only if \(n\) is a power of three.
\textbf{Solution 2.2:}
\textbf{Question 3:} In this question, you need to describe in words
sets that are defined using a formula with quantifiers. For example, the
set \(S = \{ x\in \mathbb{N} \;:\; \exists_{y\in\mathbb{N}} x=2y \}\) is
the set of even numbers.
\textbf{Question 3.1 (3 points):} Describe in words the following set
\(S\):
\[
S = \{ x\in \{0,1\}^{100} : \forall_{i\in \{0,\ldots, 99\}} x_i = x_{99-i} \}
\]
\textbf{Solution 3.1:}
\textbf{Question 3.2 (3 points):} Describe in words the following set
\(T\):
\[
T = \{ x\in \{0,1\}^* : |x|>1 \text{ and } \forall_{i \in \{2,\ldots,|x|-1 \} } \forall_{j \in \{2,\ldots,|x|-1\}} i\cdot j \neq |x| \}
\]
\textbf{Solution 3.2:}
\newpage
\textbf{Question 4:} This question deals with sets, their cardinalities,
and one to one and onto functions. You can cite results connecting these
notions from the course's textbook, MIT's ``Mathematics for Computer
Science'' or any other discrete mathematics textbook.
\textbf{Question 4.1 (4 points):} Define \(S = \{0,1\}^6\) and \(T\) as
the set \(\{ n \in [100] \;|\; \text{$n$ is prime } \}\). \emph{Prove or
disprove:} There is a one to one function from \(S\) to \(T\).
\textbf{Solution 4.1:}
\textbf{Question 4.2 (4 points):} Let \(n=100\),
\(S = [n] \times [n] \times [n]\) and \(T=\{0,1\}^n\). \emph{Prove or
disprove:} There is an onto function from \(T\) to \(S\).
\textbf{Solution 4.2:}
\textbf{Question 4.3 (4 points):} Let \(n=100\), let
\(S = \{0,1\}^{n^3}\) and \(T\) be the set of all functions mapping
\(\{0,1\}^n\) to \(\{0,1\}\). \emph{Prove or disprove:} There is a one
to one function from \(S\) to \(T\).
\textbf{Solution 4.3:}
\textbf{Question 5.1 (5 points):} Prove that for every finite sets
\(A,B,C\), \(|A \cup B \cup C| \leq |A|+|B|+|C|\).
\textbf{Solution 5.1:}
\textbf{Question 5.2 (5 points bonus):} Prove that for every finite sets
\(A,B,C\),
\(|A \cup B \cup C| \geq |A|+|B|+|C| - |A \cap B| - |B \cap C| - |A \cap C|\).
\textbf{Solution 5.2:}
\newpage
\hypertarget{graphs}{%
\subsubsection{Graphs}\label{graphs}}
These questions assume familiarity with basic graph theory.
\textbf{Question 6.1 (6 points):} Prove that for every undirected graph
\(G\) on \(n\) vertices, if \(G\) has at least \(n\) edges then \(G\)
contains a cycle.\footnote{\emph{Hint:} You can prove this by induction
on the number of edges. One way to prove it is to think of the
experiment of starting with the empty graph and adding the edges of
\(G\) one by one. You can then prove that: \textbf{(1)} if you ever
add an edge \(\{u,v\}\) such that \(u\) and \(v\) were already
connected then you create a cycle involving this edge, and
\textbf{(2)} if you add an edge \(\{u,v\}\) such that \(u\) and \(v\)
were not already connected then the number of connected components of
\(G\) drops by one.}
\textbf{Solution 6.1:}
\textbf{Question 6.2 (6 points bonus):} Prove that for every undirected
graph \(G\) of \(1000\) vertices, if every vertex has degree at most
\(4\), then there exists a subset \(S\) of at least \(200\) vertices
such that no two vertices in \(S\) are neighbors of one another.
\textbf{Solution 6.2:}
\hypertarget{big-oh-notation-questions}{%
\subsubsection{Big-Oh Notation
Questions}\label{big-oh-notation-questions}}
\textbf{Question 7:} For each pair of functions \(f,g\) below, state
whether or not \(f=O(g)\) and whether or not \(g=O(f)\).
\textbf{Question 7.1 (3 points):} \(f(n)=n(\log n)^3\) and \(g(n)=n^2\).
\textbf{Solution 7.1:}
\textbf{Question 7.2 (3 points):} \(f(n)= n^{\log n}\) and
\(g(n) = n^2\).
\textbf{Solution 7.2:}
\textbf{Question 7.3 (3 points bonus):}
\(f(n) = \binom{n}{\lceil 0.2 n \rceil}\) (where \(\binom{n}{k}\) is the
number of \(k\)-sized subsets of a set of size \(n\)) and
\(g(n) = 2^{0.1 n}\).\footnote{\emph{Hint:} one way to do this is to use
\href{https://goo.gl/cqEmS2}{Stirling's approximation}.}
\textbf{Solution 7.3:}
\end{document}