\documentclass[11pt,addpoints,answers]{exam}

% Packages
\usepackage{fullpage}
\usepackage{latexsym,amssymb,amsfonts,amsmath,mathrsfs,float, amsthm}
\usepackage[font=small,labelfont=bf, width=.618\textwidth]{caption} % custom captions
\usepackage{xcolor}
\usepackage{tikz, graphics, enumerate}
\usepackage{hyperref}


% Paragraph indentation and spacing
\newcommand{\parset}{
	\setlength{\parskip}{3mm}
  	\setlength{\parindent}{0mm}}
	
% Probability
  \DeclareMathOperator{\var}{Var}
  \renewcommand{\Pr}{\mbox{\rm Pr}}	
  \newcommand{\Exp}{{\mathbb{E}}}
  \newcommand{\E}{\mathbb{E}}

% Sets 
  \newcommand{\R}{\mathbb{R}} % reals
  \newcommand{\C}{\mathbb{C}} % complex numbers
  \newcommand{\N}{\mathbb{N}} % natural numbers
  \newcommand{\Z}{\mathbb{Z}} % integers
  \newcommand{\F}{\mathbb{F}} % field
  \newcommand{\K}{\mathbb K} % field
  \newcommand{\T}{\mathbb T} % circle
\newcommand{\B}{\mathcal{B}} % ball
  \newcommand{\pmset}[1]{\{-1,1\}^{#1}} % hypercube in +-1 basis
  \newcommand{\bset}[1]{\{0,1\}^{#1}} % hypercube
  \newcommand{\sphere}[1]{S^{#1-1}} % real unit sphere of dimension #1
  \newcommand{\ball}[1]{B_{#1}} % real unit ball of dimension $1
  \newcommand{\Orth}[1]{O(\R^{#1})} % orthogonal group
  \DeclareMathOperator{\im}{im} % image
  \DeclareMathOperator{\vspan}{Span} % kernel
  \newcommand{\1}{\mathbf{1}}
  \DeclareMathOperator{\Cball}{\mathcal C}
  \DeclareMathOperator{\cay}{Cay} 
  \DeclareMathOperator{\sol}{Sol} 
\DeclareRobustCommand{\stirling}{\genfrac\{\}{0pt}{}}

% Miscellaneous
  \newcommand{\st}{:\,} % "such that" to define sets
  \newcommand{\ie}{{i.e.}}  
  \newcommand{\eg}{{e.g.}} 
  \newcommand{\eps}{\varepsilon}
  \newcommand{\ip}[1]{\langle #1 \rangle}
  \newcommand{\cF}{{\mathcal F}}   
  \DeclareMathOperator{\U}{\mathcal{U}}
  \DeclareMathOperator{\sign}{sign}
  \newcommand{\poly}{\mbox{\rm poly}}
  \newcommand{\ceil}[1]{\lceil{#1}\rceil}
  \newcommand{\floor}[1]{\lfloor{#1}\rfloor}
  \DeclareMathOperator{\Tr}{\mathsf{Tr}}
  \DeclareMathOperator{\diag}{diag}
  \DeclareMathOperator{\patt}{patt}
  \DeclareMathOperator{\argmin}{arg\,min}
  \DeclareMathOperator{\spec}{Spec}
  \DeclareMathOperator{\enc}{\sf Enc}
  \DeclareMathOperator{\dec}{\sf Dec}
  \DeclareMathOperator{\diam}{diam} 
  \DeclareMathOperator{\spn}{span} 
  \DeclareMathOperator{\geom}{gm}
\DeclareMathOperator{\sinc}{sinc}
\DeclareMathOperator{\disc}{disc}
\DeclareMathOperator*{\argmax}{arg\,max}
  \newcommand{\infnorm}{{\ell_\infty, \ldots, \ell_\infty}}
  \newcommand{\pnorm}{{\ell_p,\dots,\ell_p}}
  \newcommand{\tnorm}{{\ell_t,\dots,\ell_t}}
  
  
% Enviroments
  \newcommand{\beq}{\begin{equation}}
  \newcommand{\eeq}{\end{equation}}
  \newcommand{\beqn}{\begin{equation*}}
  \newcommand{\eeqn}{\end{equation*}}
  \newcommand{\beqr}{\begin{eqnarray}}
  \newcommand{\eeqr}{\end{eqnarray}}
  \newcommand{\beqrn}{\begin{eqnarray*}}
  \newcommand{\eeqrn}{\end{eqnarray*}}
  \newcommand{\bmline}{\begin{multline}}
  \newcommand{\emline}{\end{multline}}
  \newcommand{\bmlinen}{\begin{multline*}}
  \newcommand{\emlinen}{\end{multline*}}
  
  \makeatletter

% END OF SUPPLIED VARIABLES

  \chead{\large \textbf{Week 1 Questions}}

  \lhead{\small
    \textbf{{Boolean Functions}\\{Northwestern \\Winter 2021}}}

  \rhead{\small \textbf{Instructor:
     {Shravas Rao}}\\\textbf{Student}: FIRSTNAME LASTNAME}

  \setlength{\headheight}{20pt}
  \setlength{\headsep}{16pt}                       
  \headrule
% execute homework commands

\begin{document}

\pagestyle{head}                % put header on every page

\medskip

\begin{questions}
\question (O 1.8) The \emph{(Boolean) dual} of $f: \{-1, 1\}^n \rightarrow \R$ is the function $f^{\dagger}$ defined by $f^{\dagger}(x) = -f(-x)$.  
The function $f$ is said to be \emph{odd} if it equals its dual; equivalently, if $f(-x) = -f(x)$ for all $x$.
The function $f$ is said to be even if $f(-x) = f(x)$ for all $x$.
Given any function $f: \{-1, 1\}^n \rightarrow \R$, its \emph{odd part} is the function $f^{\text{odd}}: \{-1, 1\}^n \rightarrow \R$ defined by $f^{\text{odd}} = (f(x)-f(-x))/2$ and its \emph{even part} is the function $f^{\text{even}}: \{-1, 1\}^n \rightarrow \R$ defined by $f^{\text{even}} = (f(x)+f(-x))/2$.

\begin{parts}
\part Express $\widehat{f}^{\dagger}(S)$ in terms of $\widehat{f}(S)$.
	
\begin{solution}

  \end{solution}

\part Verify that $f = f^{\text{odd}}+f^{\text{even}}$ and that $f$ is odd (respectively, even) if and only if $f = f^{\text{odd}}$ (respectively, $f = f^{\text{even}}$).
\begin{solution}

  \end{solution}

\part Show that
\begin{align*}
f^{\text{odd}} = \sum_{S \subseteq [n], |S| \text{ odd}} \widehat{f}(S) \chi_S, && f^{\text{even}} = \sum_{S \subseteq [n], |S| \text{ even}} \widehat{f}(S) \chi_S
\end{align*}
\begin{solution}

  \end{solution}
\end{parts}

\question (Based on O 1.15) Let $f: \{-1, 1\}^n \rightarrow \R$.  For some $k \leq n$, let $z \in \{-1, 1\}^k$.
Let $g: \{-1, 1\}^{n-k} \rightarrow \R$ be the function defined by $g(x) = f(x \circ z)$ where $\circ$ denotes concatenation.
In other words, $g$ is function obtained from $f$ after restricting the last $k$ coordinates of the input to $z$.
Compute the Fourier coefficients of $g$ in terms of the Fourier coefficients of $f$.
Conclude that $\E[g] = \sum_{T \subseteq \{n-k+1, n-k+1, \ldots, n-1, n\}} \left(\widehat{f}(T) \prod_{i \in T} z_i \right).$
\begin{solution}

  \end{solution}

\question (O 1.20) Let $f: \{-1, 1\}^n \rightarrow \R$ be such that $\widehat{f}(S)$ is nonzero if and only if $|S| = 1$.
Show that $\var[f^2] = \sum_{i \neq j} \widehat{f}(i)^2\widehat{f}(j)^2$.

\begin{solution}

\end{solution}

\question (O 1.21) Prove that there are no functions $f: \{-1, 1\}^n \rightarrow \{-1, 1\}$ with exactly $2$ nonzero Fourier coefficients.
What about exactly $3$ nonzero Fourier coefficients?

\begin{solution}

\end{solution}

\end{questions}
\end{document}