\documentclass[11pt]{article}
%%% Packages
\usepackage{amsfonts}
\usepackage[dvipsnames]{xcolor} % used for notes and solutions
\usepackage{hyperref} % used for links
\hypersetup{
colorlinks=true,
linkcolor=blue,
filecolor=magenta,
urlcolor=cyan,
pdftitle={Overleaf Example},
pdfpagemode=FullScreen,
}
\pagestyle{myheadings}
\markright{CS 121 Fall 2022 \hfill PSET 0}
\pagenumbering{gobble}
\usepackage{geometry}
\geometry{
left=1in,
right=1in,
top=1in,
bottom=1in
}
%%% Formatting
\setlength{\parskip}{\medskipamount}
\setlength{\parindent}{0in}
%%% Useful Commands
\newcommand\bit{\{0, 1\}}
\newcommand\false{\textbf{FALSE}}
\newcommand\true{\textbf{TRUE}}
\newcommand\size[1]{\left|#1\right|} % cardinality
\newcommand\union{\cup}
\newcommand\intersect{\cap}
\newcommand{\F}{\mathbb{F}}
\newcommand{\np}{\mathop{\rm NP}}
\newcommand{\binom}[2]{{#1 \choose #2}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\vol}{\mathop{\rm Vol}}
\newcommand{\conp}{\mathop{\rm co-NP}}
\newcommand{\atisp}{\mathop{\rm ATISP}}
\renewcommand{\vec}[1]{{\mathbf #1}}
\newcommand{\cupdot}{\mathbin{\mathaccent\cdot\cup}}
\newcommand{\mmod}[1]{\ (\mathrm{mod}\ #1)}
%%% Notes
\newenvironment{hint}{\itshape\color{gray}\textbf{Hint:}}{}
\newcommand\todo[1]{\textbf{\color{red}[[TODO: \textit{#1}]]}}
\newcommand\idk{\textbf{\color{orange}I don't know }}
\newcommand\bonus[1]{BONUS #1}
%%% Questions
%% TODO: Fix \hfill error
\newcommand\thequestion{\thesection}
\newenvironment{question}[2]
{\newpage\section{#1\texorpdfstring{\hfill}{horizontal spacing}{\rm\normalsize #2}}}{}
\newcommand\thesubquestion{\thesubsection}
\newenvironment{subquestion}[2]
{\subsection{#1\texorpdfstring{\hfill}{horizontal spacing}{\rm\normalsize #2}}}{}
\newenvironment{solution}
{\textbf{Solution: }\color{blue}}
{\color{black}}
%%% Assignment
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Cover Page
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TODO: Ensure all these policies are up to date.
\section*{Policies}
% TODO: Update the policies link
See the \href{http://madhu.seas.harvard.edu/courses/Fall2021/syllabus.html}{course syllabus} for the full policies.
\begin{itemize}
\item {\bf Collaboration:} 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: you must wait one hour after any collaboration or use of notes from collaboration before any writing in your own solutions to submit.
\item {\bf Owning your solution:} 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. Getting 80\% of the problem set questions right on your own will be much better to both your understanding than getting 100\% of the questions through gathering hints from others without true understanding.
\item {\bf Serious violations:} 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 {\bf Submission Format:} 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. Please mark in gradescope the pages where the solution to each question appears. Points will be deducted if you submit in a different format.
\item {\bf Late Day Policy:} To give students some flexibility to manage your schedule, you are allowed a net total of {\bf eight} late days through the semester, but you may not take more than {\bf two} late days on any single problem set.
\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:}
\begin{tabular}{rp{0.6\linewidth}}
Name:& \bf{
\todo{Put your name here}
} \\
HUID:& \bf{
\todo{Put your HUID here}
} \\
Collaborators:& \bf{
\todo{Put your collaborators here, if any.}
}
\end{tabular}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Instructions
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\section*{Instructions}
% TODO: Go through these and make sure it is up to date
The aim of problem set is to help you to test and, if needed, to brush up on the mathematical background needed to be successful in CS 121. This problem set will be \underline{\textbf{due in the first week of class}}, but you are encouraged to start working on it over the summer.
% TODO: Fix weird spacing on \idk
% Done! - Priya
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 \idk and you will get 15 percent of the credit for this problem.
% TODO: check what this e-office-hours folder is
The discussion board for this course will be active even before the course starts. If you are stuck on this problem set, you can use this discussion board to send a private message to all instructors under the \texttt{e-office-hours} folder.
% TODO: Make sure point total is accurate
% Done! - Priya
This problem set has a total of \textbf{100 points} and \textbf{22 bonus points}. A grade of 100 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.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Question 1
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TODO: update book link
\begin{question}{Textbook}{10}
Read fully the \textbf{Mathematical Background Chapter} (Chapter 1) from the \href{http://madhu.seas.harvard.edu/courses/Fall2021/book.pdf}{textbook}. This is probably the most important exercise in this problem set!!
Then write ``\textit{I certify that I fully read the mathematical background chapter}''.
\begin{solution}
\todo{Answer Question {\thequestion} here.}
\end{solution}
\end{question}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Question 2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{question}{Majority False}{6}
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 \false.
\begin{solution}
\todo{Answer Question {\thequestion} here.}
\end{solution}
\end{question}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Question 3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{question}{Writing Math}{6 + \bonus{6}}
Use the logical quantifiers \(\forall\) (for all), \(\exists\) (exists), as well as \(\wedge,\vee,\neg\) and the arithmetic operations \(+,\times,=,>,<\) to write the following:
\begin{subquestion}{}{6}
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\).
\begin{solution}
\todo{Answer Question {\thequestion} here.}
\end{solution}
\end{subquestion}
\begin{subquestion}{}{\bonus{6}}
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. (Note that the problem is much harder if you replace ``three'' by ``ten''; if you think you have a solution that would work for that problem, check that you haven't used a banned operation like exponentiation or used a variable out of scope (e.g. after \((\forall i \exists f(i)) \wedge \forall j \exists g(j)\), you can't use \(f(i)\) or \(g(j+1)\)).)
\begin{solution}
\todo{Answer Question {\thequestion} here.}
\end{solution}
\end{subquestion}
\end{question}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Question 4
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{question}{Reading Math}{12}
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.
\begin{subquestion}{}{6}
Describe in words the following set \(S\):
\[
S = \{ x\in \bit^{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 \bit^{100}\) is indexed as \(x_0x_1\cdots x_{99}\).)
\begin{solution}
\todo{Answer Question {\thesubquestion} here.}
\end{solution}
\end{subquestion}
\begin{subquestion}{}{6}
Describe in words the following set \(T\):
\[
T = \{ x\in \bit^* : |x|>1 \mbox{ and } \forall_{i \in \{2,\ldots,|x|-1 \} } \forall_{j \in \{2,\ldots,|x|-1\}} i\cdot j \neq |x| \}
\]
\begin{solution}
\todo{Answer Question {\thesubquestion} here.}
\end{solution}
\end{subquestion}
\end{question}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Question 5
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{question}{Sets}{24}
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.
\begin{subquestion}{}{8}
Define \(S = \bit^6\) and \(T\) as the set \(\{ n \in [100] \;|\; \mbox{\(n\) is prime } \}\). \emph{Prove or disprove:} There is a one to one function from \(S\) to \(T\).
\begin{solution}
\todo{Answer Question {\thesubquestion} here.}
\end{solution}
\end{subquestion}
\begin{subquestion}{}{8}
Let \(n=100\), \(S = [n] \times [n] \times [n]\) and \(T=\bit^n\). \emph{Prove or disprove:} There is an onto function from \(T\) to \(S\).
\begin{solution}
\todo{Answer Question {\thesubquestion} here.}
\end{solution}
\end{subquestion}
\begin{subquestion}{}{8}
Let \(n=100\), let \(S = \bit^{n^3}\) and \(T\) be the set of all functions mapping \(\bit^n\) to \(\bit\). \emph{Prove or disprove:} There is a one to one function from \(S\) to \(T\).
\begin{solution}
\todo{Answer Question {\thesubquestion} here.}
\end{solution}
\end{subquestion}
\end{question}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Question 6
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{question}{More Sets}{10 + \bonus{10}}
\begin{subquestion}{}{10}
Prove that for every finite sets \(A, B, C\),
\[
\size{A \union B \union C}
\leq
\size{A} + \size{B} + \size{C}
\]
\begin{solution}
\todo{Answer Question {\thesubquestion} here.}
\end{solution}
\end{subquestion}
\begin{subquestion}{}{\bonus{10}}
Prove that for every finite sets \(A, B, C\),
\[
\size{A \union B \union C}
\geq
\size{A} + \size{B} + \size{C} - \size{A \intersect B} - \size{B \intersect C} - \size{A \intersect C}
\]
\begin{solution}
\todo{Answer Question {\thesubquestion} here.}
\end{solution}
\end{subquestion}
\end{question}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Question 7
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{question}{Graphs}{20}
\begin{subquestion}{}{10}
% DAG are also the initials of Diego Andres Gutierrez :-)
% lol that's pretty cool - Priya
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.
\begin{hint}
You can use the topological sorting theorem shown in the mathematical background chapter.
\end{hint}
\begin{solution}
\todo{Answer Question {\thesubquestion} here.}
\end{solution}
\end{subquestion}
\begin{subquestion}{}{10}
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.
\begin{solution}
\todo{Answer Question {\thesubquestion} here.}
\end{solution}
\end{subquestion}
\end{question}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Question 8
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{question}{Big O-Notation}{12 + \bonus{6}}
For each pair of functions \(f,g\) below, state
\underline{\textbf{BOTH}} whether or not \(f=O(g)\) and whether or not \(g=O(f)\).
\begin{subquestion}{}{6}
\(f(n)=n(\log n)^3\) and \(g(n)=n^2\).
\begin{solution}
\todo{Answer Question {\thesubquestion} here.}
\end{solution}
\end{subquestion}
\begin{subquestion}{}{6}
\(f(n)= n^{\log n}\) and \(g(n) = n^2\).
\begin{solution}
\todo{Answer Question {\thesubquestion} here.}
\end{solution}
\end{subquestion}
\begin{subquestion}{}{\bonus{6}}
\(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}\).
\begin{hint}
One way to do this is to use \href{https://en.wikipedia.org/wiki/Stirling\%27s\_approximation}{Stirling's approximation}.
\end{hint}
\begin{solution}
\todo{Answer Question {\thesubquestion} here.}
\end{solution}
\end{subquestion}
\end{question}
\end{document}