\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 2023 \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}
\section*{Policies}
See \href{hhttps://cs121.boazbarak.org/syllabus/}{course syllabus} for the full policies.
\begin{itemize}
\item {\bf Collaboration:} You can collaborate with other students who 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, without sharing notes.
\item {\bf Owning your solution:} Always make sure that you ``own'' your solutions to 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. Especially given the generous bonus points policies for homework, \textbf{getting 80\% of the problem set questions right on your own will be much better to both your understanding and your course grade than getting 100\% of the questions through gathering hints from others without true understanding.}
\item {\bf Serious violations:} The following are examples of serious violations of the honor code: (1) Sharing questions or solutions with anyone outside this course, including posting on outside websites. (2) Collaborating with anyone except students currently taking this course. (3) Obtaining solutions using material from past years, other websites, or large language models.
\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 six} late days through the semester, but you may not take more than {\bf two} late days on any single problem set.
\item {\bf Attempting problems and ``I don't know'' policy.} Some problems might be harder than 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. If you are stuck on this problem set, you can use Ed to send a private message to all staff.
\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.
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.
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 the team.
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{Introduction} (Chapter 0) and \textbf{Mathematical Background Chapter} (Chapter 1) from the textbook. This is probably the most important exercise in this problem set!!
You should generally use \href{https://app.perusall.com/courses/compsci-121-introduction-to-theoretical-computer-science-40326360}{Perusall} to do the reading, which can be accessed through canvas. For homework zero, if you do not yet have access to Perusall, you can read the chapters from the \href{https://introtcs.org}{textbook website}.
Then write ``\textit{I certify that I fully read the introduction and mathematical background chapters}''.
\begin{solution}
\todo{Answer Question {\thequestion} here.}
\end{solution}
\end{question}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Question 2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{question}{Parity}{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 number of $x_i$'s that are True is \emph{odd}.
\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}}
For both questions below, give a direct proof without appealing to statements such as the union bound or the inclusion-exclusion principle.
\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}
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}