\documentclass[]{article}
% Required packages.
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{color}
\usepackage{tikz}
\usepackage[utf8]{inputenc}
% Some setup.
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
\setlength{\emergencystretch}{3em} % prevent overfull lines
\setcounter{secnumdepth}{0}
% Input data macros for \maketitle.
\title{CS 4810: Homework 1}
\author{due 09/05 11:59pm}
\date{(your name + netid)} % TODO: Fill in your own name and netID here.
% The actual document technically begins here.
\begin{document}
\maketitle
Collaborators: (names and netids) % TODO: List the names and netIDs of everyone who collaborated with you on this homework here.
Each problem is worth 20 points.
\section{Problem 0}
Submit the student information form (see link on piazza).
\section{Problem 1}
Show that every $n$-bit boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ can be represented by a circuit of depth at most $O(n)$.
% TODO: Enter your solution for Problem 1 here.
% \paragraph{Solution.}
\section{Problem 2}
Let $\mathrm{NOR}:\{0,1\}^2\to \{0,1\}$ be the not-or operation, so that
$\mathrm{NOR}(x,y)=0$ if $x=1$ or $y=1$, and $\mathrm{NOR}(x,y)=1$ if $x=y=0$.
Show that every circuit can then also be implemented using only NOR gates (instead of NOT, AND, OR). Show also that this does not affect the asymptotic size or depth of the circuit.
(Concretely, show that for every circuit $C$,
there exists a circuit $C'$ using only NOR gates, such that $C$ and
$C'$ compute the same function and have the
same size and depth up to constant factors, i.e.,
$\mathrm{size}(C')=O(1)\cdot\mathrm{size}(C)$ and $\mathrm{depth}(C')=O(1)\cdot\mathrm{depth}(C)$.)
You may assume that in addition to the function inputs, you have
access to constants, i.e., wires that are always $0$ or always $1$.
% TODO: Enter your solution for Problem 2 here.
% \paragraph{Solution.}
\section{Problem 3}
The function {\sc Parity}$: \{0,1\}^n\rightarrow \{0,1\}$ returns $1$ if and only if an odd number of its inputs are $1$.
Show that {\sc Parity} can be represented by a circuit of size $O(n)$ and depth $O(\log n)$.
% TODO: Enter your solution for Problem 3 here.
% \paragraph{Solution.}
\section{Problem 4}
A \emph{labelled tree} with $n$ labels is a tree -- that is, a connected graph without cycles -- whose $n$ vertices are the integers from $1$ up to $n$.
% This is an example of how you can typeset graphics directly in LaTeX. Many more advanced ones can be found at http://www.texample.net/tikz/.
\begin{figure}[htbp]
\centering
\begin{tikzpicture}
\node (a1) at (0,0) {1};
\node (a2) at (0,1) {2};
\draw (a1)--(a2);
\node (b1) at (2.5,0) {1};
\node (b2) at (2,1) {2};
\node (b3) at (3,1) {3};
\draw (b1)--(b2);
\draw (b1)--(b3);
\node (beqc) at (3.5,0.5) {$=$};
\node (c1) at (4.5,0) {1};
\node (c2) at (5,1) {2};
\node (c3) at (4,1) {3};
\draw (c1)--(c2);
\draw (c1)--(c3);
\node (cneqd) at (5.5,0.5) {$\neq$};
\node (c1) at (6.5,0) {1};
\node (c2) at (7,1) {2};
\node (c3) at (6,1) {3};
\draw (c1)--(c2);
\draw (c2)--(c3);
\node (d5) at (10,-0.5) {5};
\node (d2) at (9.5,0.5) {2};
\node (d3) at (10.5,0.5) {3};
\node (d4) at (9.85,1.5) {4}; % 0.65 surely is a reasonable approximation for 2/3 :)
\node (d1) at (10.5,1.5) {1};
\node (d6) at (11.15,1.5) {6};
\draw (d5)--(d2);
\draw (d5)--(d3)--(d4);
\draw (d3)--(d1);
\draw (d3)--(d6);
\end{tikzpicture}
\caption{Some drawings of labelled trees, not all distinct.}
\end{figure}
Show that for a given $n$, there are no more than $n^n$ distinct labelled trees.
% TODO: Enter your solution for Problem 4 here.
% \paragraph{Solution.}
\section{Problem 5}
The function {\sc Majority}$: \{0,1\}^n\rightarrow \{0,1\}$ returns $1$ if \emph{at least} $n/2$ of its inputs are $1$, and $0$ if \emph{fewer than} $n/2$ of them are.
Show that {\sc Majority} can be implemented with a circuit of size $O(n^2)$. % or $O(n \log n)$.
% TODO: Enter your solution for Problem 5 here.
% \paragraph{Solution.}
\end{document}