# 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, __you can collaborate freely with other students on this problem set as long as you list your collaborators below__.
This problem set is due **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 **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 _pairs_.
### Some policies
(See the [course syllabus](http://cs121.boazbarak.org/syllabus/) for the full policies.)
* Sharing questions or solutions with anyone outside this course, including posting on outside websites, is a violation of the honor code policy.
* 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.
* 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 __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.
**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.)
__Submitters (pairs):__ (List your names and HUIDs here)
__Collaborators:__ (List here anyone you discussed problems or ideas for solutions with)
\newpage
## 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 __"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 `e-office-hours` folder.
__Problem 0 (5 points):__ Read fully the __Mathematical Background Chapter__ ( [pdf format](https://introtcs.org/public/lec_00_1_math_background.pdf)
[html format](https://introtcs.org/public/lec_00_1_math_background.html) ) from the textbook on the website [https://introtcs.org](https://introtcs.org).
__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.)
### 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\}$.
__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 _True_.
__Solution 1:__
__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:
__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$.
__Solution 2.1:__
__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.
__Solution 2.2:__
__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.
__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} \}
$$
__Solution 3.1:__
__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| \}
$$
__Solution 3.2:__
\newpage
__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.
__Question 4.1 (4 points):__ Define $S = \{0,1\}^6$ and $T$ as the set $\{ n \in [100] \;|\; \text{$n$ is prime } \}$.
_Prove or disprove:_ There is a one to one function from $S$ to $T$.
__Solution 4.1:__
__Question 4.2 (4 points):__
Let $n=100$, $S = [n] \times [n] \times [n]$ and $T=\{0,1\}^n$.
_Prove or disprove:_ There is an onto function from $T$ to $S$.
__Solution 4.2:__
__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\}$.
_Prove or disprove:_ There is a one to one function from $S$ to $T$.
__Solution 4.3:__
__Question 5.1 (5 points):__ Prove that for every finite sets $A,B,C$, $|A \cup B \cup C| \leq |A|+|B|+|C|$.
__Solution 5.1:__
__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|$.
__Solution 5.2:__
\newpage
### Graphs
These questions assume familiarity with basic graph theory.
__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.^[_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: __(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 __(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.]
__Solution 6.1:__
__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.
__Solution 6.2:__
### Big-Oh Notation Questions
__Question 7:__ For each pair of functions $f,g$ below, state whether or not $f=O(g)$ and whether or not $g=O(f)$.
__Question 7.1 (3 points):__ $f(n)=n(\log n)^3$ and $g(n)=n^2$.
__Solution 7.1:__
__Question 7.2 (3 points):__ $f(n)= n^{\log n}$ and $g(n) = n^2$.
__Solution 7.2:__
__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}$.^[_Hint:_ one way to do this is to use [Stirling's approximation](https://goo.gl/cqEmS2).]
__Solution 7.3:__