\documentclass[11pt]{article}
\usepackage{latexsym}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{epsfig}
\usepackage[right=0.8in, top=1in, bottom=1.2in, left=0.8in]{geometry}
\usepackage{setspace}
\spacing{1.06}

\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{\vspace{0.25cm}
      \hbox to 5.78in { {COMS 4995:\hspace{0.12cm}Advanced Algorithms} \hfill #2 }
      \vspace{0.48cm}
      \hbox to 5.78in { {\Large \hfill #5  \hfill} }
      \vspace{0.42cm}
      \hbox to 5.78in { {#3 \hfill #4} }\vspace{0.25cm}
    }
  }
  \end{center}
  \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{#3}{Scribes:\hspace{0.08cm}#4}{Lecture #1}}


\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}

\begin{document}

\lecture{1 -- Introduction, Schedule, Approximate Counting}{Jan 22, 2020}{Instructor:\hspace{0.08cm}\emph{Alex Andoni}}{\emph{Yiming Wang, Zhaoyang Wang}}

\section{Introduction and Schedule}
\subsection{Topics}
In this class, we will frequently talk about randomized algorithms (e.g. $P_A(\textrm{algorithm correct} ) \geq 90 \% $ , $P_A(\text{has runtime O(n)} ) \geq 90\% $) as well as approximate algorithms (i.e. if $\alpha$ is the correct answer, algorithm A has approximation answer if it outputs $\hat{\alpha}$ s.t. $\alpha \leq \hat{\alpha} \leq a\alpha$, where $a$ is constant). A list of specific topics is shown below.


\begin{enumerate}
   \item hashing
   \begin{itemize}
     \item $h: u \rightarrow [n] $ ($[n] = \{ 1,2,3,...,n \}$)
     \item perfect hashing $O(1)$ worst case per query
     \item consistent hashing
   \end{itemize}
   \item graph algorithms
   \begin{itemize}
     \item combinatorial in nature
     \item max-flow
   \end{itemize}
   \item spectral graph algorithms, linear algebra techniques
   \begin{itemize}
     \item $A ( \textrm{n x n matrix} )$ = adjacency matrix of $G$, $A_{ij} = 1$ iff $(i,j)$ is an edge
     \item look at spectral decomposition of A
     \item random walk
     \item spectral partitioning / clustering
   \end{itemize}
   \item optimization
   \begin{itemize}
     \item linear programming
     \item duality
     \item polynomial time algorithm for linear programming
     \item iterative method (gradient descent, second order method)
     \item interior point method
     \item multiplicative weights update, online algorithm
   \end{itemize}
   \item large scale models
   \begin{itemize}
     \item cache models (CPU(register)  $\stackrel{\mathrm{fast}}{\longleftrightarrow}$ cache $\stackrel{\mathrm{slow}}{\longleftrightarrow}$ memory)
     \item parallel algorithms (map-reduce)
   \end{itemize}
   \item extra
   \begin{itemize}
     \item fast fourier transform (FFT)
     \item elliptic-curve cryptography (ECC)
     \item exhaustive search 
   \end{itemize}
\end{enumerate}


\subsection{Prerequisite}

\begin{enumerate}
   \item math
   \begin{itemize}
     \item probability theory
     \item linear algebra
   \end{itemize}
   \item CS/algorithm
   \begin{itemize}
     \item $O( )$, $\Omega( )$
     \item runtime analysis
     \item sorting, binary search, basic graph algorithms
   \end{itemize}
 
\end{enumerate}


\subsection{Deliverables}

\begin{enumerate}
   \item scribe one lecture
   \begin{itemize}
     \item $10 \%$
     \item due next day midnight
   \end{itemize}
   \item homework  
   \begin{itemize}
     \item $55\%$
     \item 5 in total (1 in every 2 weeks)
     \item late policy: 5 late days in total, $10 \%$ penalty per day up to 7 days
   \end{itemize}
   \item project  
   \begin{itemize}
     \item $35\%$
     \item options
        \begin{itemize}
            \item reading based / survey
            \item implementation based
            \item research oriented
        \end{itemize}
     \item Progress Report 1 ($5\%$) (a few pages)
     \item Progress Report 2 ($5\%$) (a few pages)
     \item Final Project ($25\%$) (10 pages)
   \end{itemize}
\end{enumerate}


\section{Counting and Morris’ Algorithm}

Let $n$ be the number of objects or ticks we would like to count. What is the space complexity required to count to n? It turns out that $O(log(n))$ bits is required to exactly count to $n$.

\begin{theorem}
To exactly count to $n$, we cannot do better than $\Omega$(log(n)).
\end{theorem}

\noindent However, if the task is approximate counting rather than exact counting, then the problem can be solved much more efficiently via \textbf{Morris' algorithm}. The key idea is to use randomized algorithm in order to achieve $O(log(log(n))$ space complexity. The details of the algorithm is shown below:

\begin{enumerate}
  \item Initialize the counter $X$ to 0
  \item For each tick, update $X \leftarrow X + 1$ with probability $2^{-X}$, and leave $X$ unchanged with probability $1-2^{-X}$
  \item output the estimate $\hat{n} = 2^{X} - 1$
\end{enumerate}

\section{Probability}

\begin{definition} [Expectation]
For a discrete random variable X, the expectation of X is
\begin{equation}
    \notag E[X] = \sum_a aP[X=a]
\end{equation}
For a continuous random variable X, the expectation of X is
\begin{equation}
    \notag E[X] = \int af(a)da
\end{equation}
where f is the probability density function (PDF) of X.
\end{definition}

\begin{lemma} [Linearity of Expectation]
Let X and Y be two random variables, then 
\begin{equation}
    \notag E[X + Y ] = E[X] + E[Y]
\end{equation}
\end{lemma}

\begin{lemma} [Markov’s inequality]
Let X be a non-negative random variable. For all $\lambda > 0$,
\begin{equation}
    \notag P[X > \lambda] \leq \frac{E[X]}{\lambda}
\end{equation}
\end{lemma}

\begin{definition} [Variance]
Let X be a random variable. The variance of X is
\begin{equation}
    \notag Var[X] = E[(X-E[X])^2] = E[X^2] - E[X]^2
\end{equation}
\end{definition}

\begin{lemma} [Chebyshev's Inequality]
Let X be a random variable. For all $\lambda > 0$,
\begin{equation}
    \notag P[ |X-E[x]| > \lambda] \leq \frac{Var[X]}{\lambda^2}
\end{equation}
\end{lemma}

\section{Analysis of Morris' Algorithm}
Define $X_n$ as the value of counter $X$ after $n$ ticks, and define $X_0 = 0$. We want the show that the expectation of the output $\hat{n}$ is in fact the actual count.
\begin{claim}
$E[2^{X_n} -1] = n$
\end{claim}

\begin{proof}
We will prove by induction. First, we check the the base cases: for $n=0$, $E[2^{X_0} - 1] = 0$; for $n=1$, $E[2^{X_1} - 1] = 1$. Now assume for inductive hypothesis that $E[2^{X_{n-1}} - 1] = n - 1$; we want to show $E[2^{X_n} -1] = n$. We have:
\begin{align*}
    \notag E[2^{X_n} -1] &= E_{X_n,X_{n-1},...,X_1}[2^{X_n} -1] \\
    \notag &= E_{X_{n-1},...,X_1}[E_{X_n}[2^{X_n} -1]] \\
    \notag &= E_{X_{n-1},...,X_1}[2^{-X_{n-1}}(2^{X_{n-1}+1}-1) + (1- 2^{-X_{n-1}}) (2^{X_{n-1}}-1)] \\
    \notag &= E_{X_{n-1},...,X_1}[2 - 2^{-X_{n-1}} + 2^{X_{n-1}}-1 - 1 + 2^{-X_{n-1}}] \\
    \notag &= E_{X_{n-1},...,X_1}[2^{-X_{n-1}}] \\
    \notag &= E[2^{-X_{n-1}} + 1 - 1] = n - 1 + 1 = n
\end{align*}
    

\end{proof}




\end{document}
