% -------------------------------------------------------- hw1.tex
%
% --------------------------------------------------------


% \newcommand{\areaX}[1]{\mathrm{area}\pth{#1}}%

\documentclass[12pt]{article}%
\usepackage{rand}%
\usepackage{rand_extra}

\HomeworkStart%
{4} % Homework number
{12} % Week of semester submitted
{1.0} % Version

\SaveIndent%
\HWInstructions{Submission guidelines same as previous homework.}

\medskip%
\hrule %
\medskip


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\SaveIndent


\begin{questions}[start=10]
    \item \HWProblemHead{100}{Streaming inverse frequencies.}{}

    Let $S$ be a stream of $m$ numbers taken out of the set
    $\{1,\ldots, n\}$. For a number $i=1,\ldots, n$, let $f_i$ be the
    number of times that $i$ appears in the stream.  You can assume
    that this stream contains at least $m/10$ distinct values.

    You are also given parameter $\eps \in (0,1)$ and
    $\delta \in (0,1)$.  Design an algorithm that uses small space (in
    both $n$ and $m$) that outputs an estimate $H$ to the quantity
    $G = \sum_{i: f_i \neq 0} \frac{1}{f_i}$. The algorithm is
    required to have the property that
    \begin{equation*}
        \Prob{ (1-\eps) G \leq H \leq (1+\eps)G} \geq 1-\delta.
    \end{equation*}
    Provide full details!


    (Hint: Follow the algorithms seen in class. Figure out where you
    have to use the provided assumption.)


    \item \HWProblemHead{100}{Estimate it.}{}

    Let $S = s_1, s_2, \ldots, s_m$ be a stream ($m$ is not known to
    you in advance). Given an item $s_i$ in the stream, you can check
    if it is valid by calling an oracle $D$. Let $\tau$ be the number
    of valid elements in the stream.  The oracle calls are
    expensive. Given parameters $\eps, \delta$, describe an algorithm
    that outputs an estimate $u$ for the number of items in the stream
    that are valid, such that
    $\Prob{ \tau -\eps m \leq u \leq \tau + \eps m } \geq 1 - \delta$.

    Your algorithm needs to use little space, and few oracle calls. In
    particular, how many oracle calls does your algorithm performs,
    say in expectation. How much space does your algorithm uses?


    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    \item \HWProblemHead{100}{Streaming for $k$\th smallest number.}{}

    \newcommand{\rankY}[2]{\mathrm{rank}\pth{#1,#2}}
    
    You are given as input a parameter $k$.
    \begin{questions}
        \item \points{10} Describe a streaming algorithm that output
        the $k$\th smallest number in a stream $S$ of $n$ (distinct)
        numbers $s_1, \ldots, s_n$. How much space does your algorithm
        use.

        \item \points{70} Given a parameter $\eps \in (0,1)$, describe
        a streaming algorithm that outputs a number $t$, such that
        $(1-\eps)k \leq \rankY{S}{t} \leq (1+\eps)k$, where
        $\rankY{S}{t}$ is the rank of the number of $t$ in $S$ (i.e.,
        it is the number of elements in $S$ that are $\leq t$).

        For credit, your solution should use space independent of $k$,
        and succeed with probability $\geq 1-1/n^{10}$. Prove that
        your algorithm succeeds with the stated probability.
 
        \item \points{20} (Probably hard and tedious.) Solve the
        previous part, under the settings where you do not know $n$ in
        advance (i.e., the length of the stream). Instead, you are
        given an additional parameter $\delta \in (0,1)$, and your
        streaming algorithm needs to succeed with probability
        $\geq 1 - \delta$. How much space does your streaming
        algorithm use?

    \end{questions}

\end{questions}

\end{document}


% --------------------------------------------------------
%
% homework 4 - end of file
% --------------------------------------------------------
