%Do not change 
\documentclass[12pt, oneside]{article}
\usepackage{amssymb,amsmath}
\usepackage[margin=1in]{geometry}
\usepackage{textpos}
\usepackage{mathtools}
\usepackage{xspace}
\newcommand\myeq{\stackrel{\mathclap{\normalfont\mbox{?}}}{=}}
\newcommand\eq{\stackrel{\mathclap{\normalfont\mbox{def}}}{=}}
% You may add the packages you need here
\newcommand\rd{\textsuperscript{rd}\xspace}
\newcommand\nth{\textsuperscript{th}\xspace}


\begin{document}
% Do not modify 


%Do not modify
\begin{textblock*}{16cm}(-1.7cm,-2.3cm)
\noindent {\large CS 580-Spring 2019} \\
\noindent {\large Instructor: Jeremiah Blocki} \\
\noindent {\large TAs:  Hamidreza Khorasgani, Akash Kumar} \\
\noindent {\large I collaborated with (...). I affirm that I wrote the solutions in my own words and that I understand the solutions I am submitting.}
\end{textblock*}

%Do not modify other than putting your name where stated
\begin{textblock*}{8cm}(12.5cm,-1cm)
%\noindent {Name: } 
\end{textblock*}
%Do not modify other than typing your acknowledgement where stated
\begin{textblock*}{13.5cm}(-1.7cm,-1.8cm)
\noindent \textit{\footnotesize  } 
\end{textblock*}

\vspace{1cm}

%Do not modify other than typing the homework number after #
\begin{center}
\textbf{\Large Homework 1} \\ 
\textbf{Due Date: January 24, 2019 at 11:59PM on Gradescope.}%\\
%\textbf{Instructor: Jeremiah Blocki}\\
%\textbf{TAs: Chang Li, Akash Kumar}
\end{center}


%Rest should contain your solution for the homework. Feel free to improvise in ways that you believe make grading easier.
\subsection*{Question 1} 
\begin{enumerate}
\item Show the following using induction. Consider the following graph $H_n=(V_n,E_n)$. Its vertex set is $V_n=\{0,1\}^n$ -- that is every bitstring of length $n$ is a vertex. A pair of vertices $u, v \in \{0,1\}^n$ is connected by an edge (i.e., $\{u,v\} \in E_n$) if $u$ and $v$ differ in exactly one bit. For example, if $n=3$ then $u=(0,0,0)$ and $v=(1,0,0)$ would be connected by an edge, but $v$ and $w=(1,1,1)$ were not connected by an edge. Use the principle of mathematical induction to show that the number of edges in the graph is $\left| E_n  \right| = n2^{n-1}$.

\item $n$ friends get together at a bar. It takes exactly $3$ friends to participate in a cheer. Various (not necessarily all) triples of friends engage in cheers. For an individual $x$ we use $\mathtt{CheerCount}(x)$ to denote the number of times individual $x$ participates in a cheer.  For $i \in \{0,1,2\}$, let $S_i = \{ x~:~i=\mathtt{CheerCount}(x)  \mod{3} \}$ denote the set of people $x$ that have cheered $i$ times or $i+3$ times or $i+6$ times etc...  For example, if individual $x$ participated in $8$ cheers then $x \in S_2$ and if individual $y$ participated in $12$ cheers then $y \in S_0$. Show that the number $2|S_2| + |S_1|$ is a multiple of $3$. 
\end{enumerate}



\subsection*{Question 2}
Consider an instance $I$ of the stable marriage problem with $n$ men and $n$ women. For a person (man or woman) $x$ with preference list $P_x$ define $P_x(1/2)$ to be the first $n/2$ persons (women/men) in the list $P_x$ (to simplify notation we will assume that $n$ is even). Suppose that we use Gale Shapley algorithm to find a stable matching. If a person (man or woman) $x$ is paired off with another person $y \in P_x(1/2)$, the Gale Shapley matching is said to be \emph{good for} $x$. Show that there is at least one person $x$ such that Gale-Shapley matching is \emph{good for} $x$. You may not make any assumptions about the preference lists. 
%Chapter 1. Problem 5. Kleinberg-Tardos (KT) \\
%Suppose that we want to match $n$ residents to $n$ hospitals so that each resident is assigned to a distinct hospital. Furthermore, suppose that each resident is graded A, B, C or D and each hospital is ranked R1, R2 or R3. Each resident would prefer an R1 hospital to an R2 hospital and would prefer a rank 2 hospital to a rank 3 hospital though different residents will have different preferences among the different hospitals of each rank. Similarly, each hospital will prefer to be matched with a resident of higher grade though each hospital will have different preferences among the residents in each grade. Let $\#A$ (resp. $\#B$,$\#C$,$\#D$) denote the number of grade A residents (resp. grade B, C, D) and let $\#R1$ (resp. $\#R2$,$\#R3$) denote the number of rank 1 hospitals (resp. rank 2, 3). Prove or refute each of the following claims.
%\begin{enumerate}
%\item Suppose that $\#A + \#B = \#R1$ then in {\em any} stable matching no rank 1 hospital is matched with a grade C or grade D resident.
%\item  Suppose that $\#A + \#B+\#C >  \#R2$ and then in any stable matching every resident with a grade of D is matched with a rank 3 hospital.
%\item Suppose that $\#A > \#R1$ and that every rank 1 hospital has a unique top candidate on their preference list. Then in the Gale-Shapley matching (with hospitals playing the role of ``men'') each rank 1 hospital will be matched with its favorite resident. 

%\end{enumerate}
\subsection*{Question 3}
In class we introduced big-O notation $f(n) \in O\left(g(n)\right)$, $f(n) \in \Omega\left(g(n)\right)$ and $f(n) \in \Theta\left(g(n)\right)$. In computer science it is also common to use ``little-o'' notation. In particular, we say that $f(n) \in o\left( g(n)\right)$ if for all positive constants $c>0$ there exists a number $N$ such that for all $n \geq N$ it holds that $f(n) < c \times g(n)$. Similarly, we say that $f(n) \in \omega\left(g(n) \right)$ if for all positive constants $c>0$ there exists a number $N$ such that for all $n \geq N$ it holds that $f(n) \geq c \times g(n)$. \\

Formally prove or disprove each of the following claims. You may assume that for all $n \geq 2^{2^{2019}}$ we have $f(n) \geq 1$ and $g(n) \geq 1$. 

\begin{enumerate}
%\item $f(n) \in O\big(g(n)\big)$ implies $g(n) \in O\big(f(n)\big)$ .
\item $h(n) \in \Theta\left( \max\{f(n)^2,g(n)^2\} \right)$ where $h(n) = f(n) \times g(n)$
\item $f(n) \in o\left( g(n)\right)$ if and only if $g(n) \in \omega\left(f(n)\right)$. 
\item If $h(n) \in \Theta\left( \log n \right)$ where $h(n) = \ln f(n)$ then $f(n) \in O(n)$.
\item Suppose that $f(n) \in \omega(1)$ then $f(n) \in o\left( f(n)^2\right)$. 
\item If $f(n) \notin O\left( g(n)\right)$ then $g(n) \in O\left( f(n)\right)$. 
\item $f(n)  \in o\left(g(n)\right)$ implies that $h(n) \in O\big(2^{g(n)}\big)$ where $h(n) = 2^{f(n)}$.
\item If $f(n) \in \Theta(h(n))$ and $g(n) \in o\left(h(n)\right)$ then $f(n) \in  \omega\left( g(n)\right)$. 
\end{enumerate}

\subsection*{Question 4}
Suppose that an $n$-node undirected graph $G=(V,E)$ contains two nodes $s$ and $t$ such that the distance between $s$ and $t$ is strictly greater than $n/2$. Show that there exists some node $v \neq s,t$ such that deleting $v$ from $G$ destroys {\em all} paths from $s$ to $t$. Give an algorithm running in time $O\left( n+m\right)$ to find such a node.


\end{document}