\PassOptionsToPackage{unicode=true}{hyperref} % options for packages loaded elsewhere
\PassOptionsToPackage{hyphens}{url}
%
\documentclass[
]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\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{Scale=MatchLowercase}
\defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
\IfFileExists{microtype.sty}{% use microtype if available
\usepackage[]{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\makeatletter
\@ifundefined{KOMAClassName}{% if non-KOMA class
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}}
}{% if KOMA class
\KOMAoptions{parskip=half}}
\makeatother
\usepackage{xcolor}
\IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
\IfFileExists{bookmark.sty}{\usepackage{bookmark}}{\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}{-2}
% 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-2019}{%
\section{CS 121 Homework Zero: Fall
2019}\label{cs-121-homework-zero-fall-2019}}
The aim of problem set is to help you in brushing up on the mathematical
background needed to be successful in CS 121. This problem set will be
due in the first week of class, but I encourage you to start working on
it over the summer.
\textbf{Some policies:} (See the
\href{http://cs121.boazbarak.org/syllabus/}{course syllabus} for the
full policies.)
\begin{itemize}
\item
You can collaborate with other students that are currently enrolled in
this course (or, in the case of homework zero, planning to enroll in
this course) in brainstorming and thinking through approaches to
solutions but you should write the solutions on your own and cannot
share them with other students.
\item
Always make sure that you ``own'' your solutions to this other problem
sets. That is, you should always first grapple with the problems on
your own, and even if you participate in brainstorming sessions, make
sure that you completely understand the ideas and details underlying
the solution. This is in your interest as it ensures you have a solid
understanding of the course material, and will help in the midterms
and final. There will be many ``bonus points'' in the problem sets and
ways to make up for lost points. Therefore getting 80\% of the problem
set questions right on your own will be much better to both your
understanding and grade than getting 100\% of the questions through
gathering hints from others without true understanding.
\item
Sharing questions or solutions with anyone outside this course,
including posting on outside websites, is a violation of the honor
code policy. Collaborating with anyone except students currently
taking this course or using material from past years from this or
other courses is a violation of the honor code policy.
\item
The submitted PDF should be typed and in the same format and
pagination as ours. Please include the text of the problems and write
\textbf{Solution X:} before your solution. (This is easy to do if you
use our markdown template.) Please mark in gradescope the pages where
the 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:}
\textbf{Your name:} (Write name and HUID here)
\textbf{Collaborators:} (List here names of 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 will be active even before the course
starts. 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.
This problem set has a total of \textbf{50 points} and \textbf{11 bonus
points}. A grade of 50 or more on this problem set is considered a
perfect grade. If you get stuck in any questions, you might find the
resources in the \href{https://cs121.boazbarak.org/background/}{CS 121
background page} helpful.
\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}.
This is probably the most important exercise in this problem set!!
\textbf{Solution 0:} (Write ``I certify that I fully read the
mathematical background chapter''.)
\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{False}.
\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, 98\}} x_i = x_{i+1} \}
\]
(Recall that, as written in the mathematical background chapter, we use
zero-based indexing in this course, and so a string
\(x\in \{0,1\}^{100}\) is indexed as \(x_0x_1\cdots x_{99}\).)
\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:}
\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:}
\hypertarget{graphs}{%
\subsubsection{Graphs}\label{graphs}}
Thee following two questions assume familiarity with basic graph theory.
If you need to look up or review any terms, the
\href{https://cs121.boazbarak.org/background/}{CS 121 background page}
contains several freely available online resources on graph theory. This
material also appears in Chapters 13,14,16 and 17 of the CS 20 textbook
``Essential Discrete Mathematics for Computer Science'' by Harry Lewis
and Rachel Zax.
\textbf{Question 6.1 (5 points):} Prove that if \(G\) is a directed
acyclic graph (DAG) on \(n\) vertices, if \(u\) and \(v\) are two
vertices of \(G\) such that there is a directed path of length \(n-1\)
from \(u\) to \(v\) then \(u\) has no in-neighbors.\footnote{\emph{Hint:}
You can use the topological sorting theorem shown in the mathematical
background chapter.}
\textbf{Solution 6.1:}
\textbf{Question 6.2 (5 points):} 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-o-notation}{%
\subsubsection{Big-O Notation}\label{big-o-notation}}
\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}