%
% This is a borrowed LaTeX template file for lecture notes for CS267,
% Applications of Parallel Computing, UCBerkeley EECS Department and
%  CMU's 10725 Fall 2012 Optimization course
% taught by Geoff Gordon and Ryan Tibshirani.  
%Now it is used for CSCI-B609 Foundations of Data Science 
%course at Indiana  University. When preparing 
% your homework for this class, please use this template.
%
% To familiarize yourself with this template, the body contains
% some examples of its use.  Look them over.  Then you can
% run LaTeX on this file.  After you have LaTeXed this file then
% you can look over the result either by printing it out with
% dvips or using xdvi. "pdflatex template.tex" should also work.
%

\documentclass[twoside]{article}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}

%
% ADD PACKAGES here:
%

\usepackage{amsmath,amsfonts,graphicx}

%
% The following commands set up the hwnum (homework number)
% counter and make various numbering schemes work relative
% to the homework number.
%
\newcounter{hwnum}
\renewcommand{\thepage}{\thehwnum-\arabic{page}}
\renewcommand{\thesection}{\thehwnum.\arabic{section}}
\renewcommand{\theequation}{\thehwnum.\arabic{equation}}
\renewcommand{\thefigure}{\thehwnum.\arabic{figure}}
\renewcommand{\thetable}{\thehwnum.\arabic{table}}

%
% The following macro is used to generate the header.
%
\newcommand{\hw}[4]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{hwnum}{#1}
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf CSCI B609 -- Foundations of Data Science
	\hfill Fall 2017} }
       \vspace{4mm}
       \hbox to 6.28in { {\Large \hfill Homework #1: #2  \hfill} }
       \vspace{2mm}
       \hbox to 6.28in { {\it Name: #3 \hfill #4} }
      \vspace{2mm}}
   }
   \end{center}


}
%
% Convention for citations is authors' initials followed by the year.
% For example, to cite a paper by Leighton and Maggs you would type
% \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
% (To avoid bibliography problems, for now we redefine the \cite command.)
% Also commands that create a suitable format for the reference list.
\renewcommand{\cite}[1]{[#1]}
\def\beginrefs{\begin{list}%
        {[\arabic{equation}]}{\usecounter{equation}
         \setlength{\leftmargin}{2.0truecm}\setlength{\labelsep}{0.4truecm}%
         \setlength{\labelwidth}{1.6truecm}}}
\def\endrefs{\end{list}}
\def\bibentry#1{\item[\hbox{[#1]}]}

%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{SPACE-IN-INCHES}{CAPTION}
\newcommand{\fig}[3]{
			\vspace{#2}
			\begin{center}
			Figure \thehwnum.#1:~#3
			\end{center}
	}
% Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[hwnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}
\newtheorem{problem}[theorem]{Problem}


% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM HERE:

\newcommand\E{\mathbb{E}}

\begin{document}

\hw{3}{November 06}{YOUR NAME HERE}{Due: Monday, November 20, 11:59pm EST}

\begin{problem}[Approximate median]
You are given a stream of $m$ elements $x_1, \dots, x_m$ where $x_i \in \{1, \dots n\}$ where $m$ is an odd integer. 
For each element $x_i$ in the stream $rank(x_i) = \{j | x_j \le x_i\}$.
Recall the median $M$ is defined as the element $x_i$ in the stream such that $rank(x_i) = m/2 + 1$.
Consider an algorithm that takes a uniformly random sample of size $t$ from the stream and computes $M'$, the median value on this random sample.

For $t = o(m)$ does the above algorithm give a 10\%-approximate value of the true median with probability $\ge 2/3$, i.e. is it true that:
$$M - \frac{n}{10} \le M' \le M + \frac{n}{10} \text{ }?$$
Explain your answer -- if the algoirthm works provide the analysis. If it doesn't give a counterexample.
\end{problem}

\begin{problem}[Lower bound on $F_k$]
Recall the definition of a frequency vector $f$ whose entries $f_i$ correspond to the number of occurrences of an element $i$ in the stream.
The $k$-th frequency moment $F_k$ is defined as $F_k = \sum_{i = 1}^n f^k_i$.
Show that for all integer $k \ge 1$ it holds that:
$$F_k \ge n \left(\frac{m}{n}\right)^k,$$
where $m$ is the length of the stream.

\textbf{Hint:} Consider the worst case when $f_1 = f_2 = \dots = f_n = \frac{m}{n}$. Use convexity of $x^k$ to finish the proof.

\end{problem}


\begin{problem}[Upper bound on the AMS estimator]
Recall the same definitions of $f_i$ and $F_k$ given in the previous problem.
Recall that in the AMS estimator we sample an index $j$ between $1$ and $m$ and define $r = |\{k \ge j: x_k = x_j\}|$.
The AMS estimator is given as $X = m (r^k - (r-1)^k)$.
Show that:
$$X \le m k f_\star^{k - 1}\text{, where }f_\star = max_{i = 1}^n f_i.$$
\end{problem}


\begin{problem}[Exercise 7.9, modified]
Let $p$ be a prime. A set of hash functions 
$H = \{h | \{0, 1, \dots, p-1\} \rightarrow \{0, 1, \dots, p-1\}  \}$ 
is $3$-universal if for all $u,v,w,x,y,z$ in $\{0, 1, \dots, p-1\}$ where $x,y,z$ are distinct:
\begin{align*}
&\Pr_h[h(x) = u] =  1/p, \\
&\Pr_h[h(x) = u, h(y) = v, h(z) = w] = \frac{1}{p^3}.
\end{align*}
\begin{enumerate}
\item Is the set $\{h_{ab}(x) = ax + b \text{ mod } p | 0 \le a, b < p\}$ of hash functions universal for a uniformly random choice of $a,b \sim \{0, 1, \dots, p-1\}$?
\item Give a $3$-universal set of hash functions.
\end{enumerate}
\end{problem}

\end{document}





