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

\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{\vspace{0.25cm}
      \hbox to 5.78in { {COMS 4995-8:\hspace{0.12cm}Advanced
          Algorithms (Spring'21)} \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}

\newtheorem{algo}[theorem]{Algorithm}
\newcommand{\E}{{\mathbb E}}
\DeclareMathOperator{\var}{Var}

\begin{document}

\lecture{Lecture 1: Introduction, Approximate Counting}{Jan 11,
  2021}{Instructor:\hspace{0.08cm}\emph{Alex Andoni }}{\emph{Max Daniels}}

\section{Introduction}

In this course, we will study the theory behind many modern, practical algorithms. We will focus on algorithms which are randomized, producing a correct result only with some fixed probability, and  which are approximate, producing a result which may be off the true result by at most a constant factor. For example, instead of finding some minimized quantity $a_\text{min}$, it may be easier to output a random approximation $b$ with
\begin{align*}
    \text{Pr} \left( \text{output $b$ has $a_{\text{min}} < b < (1 + \epsilon) a_{\text{min}}$} \right) \geq 90 \%.
\end{align*}
Our main tasks will be to design algorithms and analyze them. Analyzing an algorithm requires proving its correctness and studying its performance. Algorithms in this course may be approximately or non-deterministically correct and we may focus on performance analysis of the time usage, space usage, communication cost, etc. 

\section{Course Info}

Here is the course website: \url{http://www.cs.columbia.edu/~andoni/advancedS21/index.html}.
The course has no textbook but lectures will be scribed, with notes and additional resources for each lecture are available on the course page.

 \vspace{0.5cm} 
 
\noindent\textbf{Mathematical Background}. We are encouraged to review the self-evaluation test as preparation for the course. Familiarity with the following subjects will be important:
\begin{enumerate}
    \item Probability: expectation, variance, Markov bounds, Chebyshev bounds.
    \item Linear Algebra: span, subpaces, linear transformations.
    \item Computer Science: big-O notation, basic algorithms for sorting and searching, graphs. 
\end{enumerate}

\noindent \textbf{Grading}: here is the grade breakdown.
\begin{enumerate}
    \item (10\%) Scribing Lectures 
    \item (55\%) Homeworks. there are 5 homework assignments, roughly once every 2 weeks. Students can take 5 total late days. Afterwards, assignments receive a $10\%$-per-day point deduction.
    \item (35\%) Final Project. Students will work in groups of 2-3 and will submit two reports ($5\%$ each) and a final project ($25\%$ each). The final project can be reading based, implementation based, or research based.
\end{enumerate}

\section{Course Topics}
We will discuss the following topics.
\begin{enumerate}
    \item \textbf{Hashing}. We will design hash functions $h : U \to [n]$ which map items in some universe $U$, a generic set, to keys in the set $[n] = \{1, 2, \ldots, n\}$. We will use them to solve the Dictionary Problem:
    \begin{align*}
        & \text{Given $S \subseteq U$, how can we preprocess $S$ so that later,}\\
        & \text{given arbitrary $x \in U$, we can cheaply query whether $x \in S$}.
    \end{align*}
    We will use perfect hashing to solve the dictionary problem with $O(1)$ time queries. 
    \item \textbf{Sketching and Streaming}. How can we compress (``sketch'') extremely large objects into useful smaller versions? For example, we may compress large objects into digests that can be easily compared for similarities or which provide a synopsis of the original object. As a real-world example, consider the problem of approximately counting the number of unique IP addresses seen by a router under heavy traffic. By embedding data into high dimensional spaces, we will design algorithms that leverage properties of high dimensional geometry.
    \item \textbf{Nearest Neighbor Searches}. Given a high dimensional set of points, how can we efficiently compute the nearest neighbors of any particular point? This is another question related to high dimensional geometry. 
    \item \textbf{Graph Algorithms, Maximum Flows}. We have previously studied the Ford-Fulkerson algorithm which is not exactly polynomial time. We will study various polynomial time algorithms for max flow. We will also study \textit{scaling algorithms}, which can be used to solve max flow in polynomial time. 
    \item \textbf{Spectral Graph Theory}. Graphs are often represented by matrices, for example the adjacency or degree matrix. We will relate spectral properties of these matrices (ie. properties of their eigenvalues) to important properties of the graph, like connectedness or the presence of clusters of well-connected nodes. Our goal is to study \textit{spectral clustering algorithms}.  
    \item \textbf{Optimization}. How can we solve optimization problems of the form $\min_{x \in C } f(x)$ where $x$ is constrained within $C \subseteq \mathbb{R}^d$? We will focus on \textit{linear programs} (LPs), where $f(x)$ and $C$ are linear. For example, $f(x) = c^T x$ and $C = \{ x \in \mathbb{R}^d : A x \geq b \}$ for $b, c \in \mathbb{R}^d$ and $A \in \mathbb{R}^{d \times d}$.
    
    We will study \textit{interior point methods} for solving LPs in polynomial time as well as descent algorithms like \textit{Gradient Descent} or \textit{Newton Iteration}. As an application of LPs, we will study \textit{Multiplicative Weight Updates} for learning-from-experts/boosting problems.  
    \item \textbf{Models of Large Scale Computation}. There are many models of computation which incorporate design elements of modern computers like parallel processors, cache memory, and cluster computing. We will study the design of algorithms for various computational models, such as parallel algorithms for MapReduce.
    \item \textbf{Extra Things}. Perhaps the Fast Fourier Transform?
\end{enumerate}

\section{Morris's Algorithm for Approximate Counting}

Here is the \textit{counting problem}: 
\begin{displayquote}
    \textbf{Input}: a stream of button presses, observed one at a time. \\
    \textbf{Goal}: output the number of observed button presses. \\
    \textbf{Performance metric}: use as little space as possible.
\end{displayquote}
Any algorithm that exactly counts $n$ distinct items must use at least $\log_2(n)$ bits, so no exact algorithm beats the simple approach of incrementing an integer for each button press. In the next few lectures, we will study a randomized, approximate algorithm that uses only $O(\log_2 \log_2 (n))$ bits.

\begin{algo}[Morris's Algorithm] \hfill
\setstretch{0.8}
\begin{enumerate}
    \item Set $X = 0$.
    \item For each input button press:
    \begin{enumerate}
        \item with probability $2^{-X}$, set $X = X+1$.
    \end{enumerate}
    \item Output $\hat{n} = 2^{X} - 1$.
\end{enumerate}
\setstretch{1}
\end{algo}
%\begin{proof}
%The proof is by induction. Let $E_n$ be the expected output for $n$ input button presses. It is clear that $E_0 = 0$ and $E_1 = 1$. For $n \geq 1$, let $X_n$ be the value of $X$ at $n$ iterations and let $I_n$ indicate the event that $X$ is incremented 1 on the $n$th iteration. So, $X_n = X_{n-1} + I_n$, which implies
%\begin{align*}
%    E_n & = \mathbb{E}[2^{X_n} - 1] = \mathbb{E}_{X_{n-1}} \left[ \mathbb{E}_{I_n} \left[ 2^{ X_{n-1} + I_n } - 1 \mid X_{n-1} \right] \right] \\
%    & = \mathbb{E}_{X_{n-1}} \left[ \left(2^{X_{n-1} +1} - 1 \right) \text{Pr}(I_n = 1 \mid X_{n-1}) +  \left(2^{X_{n-1}} - 1 \right) \text{Pr}(I_n = 0 \mid X_{n-1}) \right] \\
%    & =  \mathbb{E}_{X_{n-1}} \left[ \left(2^{X_{n-1} +1} - 1 \right) (2^{-X_{n-1}}) +  \left(2^{X_{n-1}} - 1 \right) (1 - 2^{X_{n-1}}) \right] \\
%    & = \mathbb{E}_{X_{n-1}} \left[ 1 + (2^{X_{n-1}}- 1)  \right] = n.
%\end{align*}
%Hence $E_n = n$ as desired.
%\end{proof}

\noindent
We will analyze this algorithm next class. Here is some background material that we will use:
\begin{enumerate}
    \item Expectations. For a random variable $X$, the expected value of $X$ is $\mathbb{E}[X] = \sum_{a} a \text{Pr}(X = a)$. Expectations are linear: for $a, b \in R$, $\mathbb{E}[a X_1 + b X_2] = a \mathbb{E}[X_1] +  b \mathbb{E}[X_2]$. 
    \item Variance. The variance of $X$ is $ \sigma^2 = \mathbb{E}[(X - \mathbb{E}[X])^2] = \mathbb{E}[X^2] - \mathbb{E}[X]^2$. The standard deviation $\sigma$ measures how far typical values of $X$ are from the mean. 
\end{enumerate}

A random algorithm should be correct on average, but it should also have small standard deviation. Otherwise, its typical outputs will be far from the average/correct value. Using the mean and variance, we can extract performance guarantees using \textit{concentration bounds}:
\begin{enumerate}
    \item \textit{Markov Bound}. If $X$ is non-negative, $\text{Pr}( X > \lambda) \leq \frac{\mathbb{E}[X]}{\lambda}$.
    \item \textit{Chebyshev Bound}. $\text{Pr}( | X - \mathbb{E}[X]| > \lambda) \leq \frac{\text{Var}[X]}{\lambda^2}$.
\end{enumerate}
\end{document}