\documentclass[12pt]{exam}

\usepackage[utf8]{inputenc}  % For UTF8 source encoding.
\usepackage{amsmath}  % For displaying math equations.
\usepackage{amsfonts} % For mathematical fonts (like \mathbb{E}!).
\usepackage{upgreek}  % For upright Greek letters, such as \upvarphi.
\usepackage{wasysym}  % For additional glyphs (like \smiley!).
% For document margins.
\usepackage[left=.8in, right=.8in, top=1in, bottom=1in]{geometry}
\usepackage{lastpage} % For a reference to the number of pages.

% TODO: Enter your name here :)
\newcommand*{\authorname}{[Your name goes here]}

\newcommand*{\psetnumber}{0}
\newcommand*{\psetdescription}{Concept Refresher}
\newcommand*{\duedate}{Tuesday, April 10th}
\newcommand*{\duetime}{2:30 pm}

% Fancy headers and footers
\headrule
\firstpageheader{CS166\\Spring 2018}{Problem Set \psetnumber\\\psetdescription}{Due: \duedate\\at \duetime}
\runningheader{CS166}{Problem Set \psetnumber}{\authorname}
\footer{}{\footnotesize{Page \thepage\ of \pageref{LastPage}}}{}

% Exam questions.
\newcommand{\Q}[1]{\question{\large{\textbf{#1}}}}
\qformat{}  % Remove formatting from exam questions.

% Useful macro commands.
\newcommand*{\ex}{\mathbb{E}}
\newcommand*{\bigtheta}[1]{\Theta\left( #1 \right)}
\newcommand*{\bigo}[1]{O \left( #1 \right)}
\newcommand*{\bigomega}[1]{\Omega \left( #1 \right)}
\newcommand*{\prob}[1]{\text{Pr} \left[ #1 \right]}
\newcommand*{\var}[1]{\text{Var} \left[ #1 \right]}

% Custom formatting for problem parts.
\renewcommand{\thepartno}{\roman{partno}}
\renewcommand{\partlabel}{\thepartno.}

% Framed answers.
\newcommand{\answerbox}[1]{
\begin{framed}
\hspace{\fill}
\vspace{#1}
\end{framed}}

\printanswers

\setlength\answerlinelength{2in} \setlength\answerskip{0.3in}

\begin{document}
\title{CS166 Problem Set \psetnumber: \psetdescription}
\author{\authorname}
\date{}
\maketitle
\thispagestyle{headandfoot}

\begin{questions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Q{Problem One: Fibonacci Fun!}

The Fibonacci numbers are a famous sequence defined as
\[
	F_0 = 0 \qquad F_1 = 1 \qquad F_{n+2} = F_n + F_{n+1}
\]

For example, the first few terms of the Fibonacci sequence are
\[
	0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \ldots
\]

The Fibonacci numbers show up in surprising places in the analysis of algorithms and data structures.

One nice property of the Fibonacci numbers is that $F_n = \bigtheta{\upvarphi^n}$, where $\upvarphi$ is the $\emph{\textbf{golden ratio}}$. The golden ratio is $\upvarphi = \frac{1+ \sqrt{5}}{2}$ and is the positive root of the equation $x^2 = 1+x$.

\begin{parts}

\part Using the formal definition of big-O notation, prove that $F_n = \bigo{\upvarphi^n}$. To do so, find explicit choices of the constants $c$ and $n_0$ for the definition of big-O notation, then use induction to prove that those choices are correct.

\begin{solution}
Your solution goes here!
\end{solution}

\part Using the formal definition of big-$\Omega$ notation, prove that $F_n = \bigomega{\upvarphi^n}$. As before, find explicit choices of $c$ and $n_0$ needed by the definition of big-$\Omega$ notation, then use induction to prove that those choices are correct.

\begin{solution}
Your solution goes here!
\end{solution}

\end{parts}
\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Q{Problem Two: Probability and Concentration Inequalities}

Let $X_1, X_2, \ldots, X_n$ be a collection of $n$ nonnegative random variables such that $\ex\left[X_i\right] = 1$ for each variable $X_i$. (Note that these random variables might not all be independent of one another.)

\begin{parts}

\part Prove that $\prob{\sum_{i=1}^n X_i \geq 2n} \leq \frac{1}{2}$. You may want to use Markov's inequality.

\begin{solution}
Your solution goes here!
\end{solution}

Now, suppose you learn that $\var{X_i} = 1$ for each variable $X_i$ and these variables are all pairwise independent (that is, $X_i$ and $X_j$ are independent for any $i \neq j$).

\part Prove that $\prob{\sum_{i=1}^n \geq 2n} \leq \frac{1}{n}$. You may want to use Chebyshev's inequality.

\begin{solution}
Your solution goes here!
\end{solution}

What happens, though, if the conditions from part (ii) of this problem are weakened so that the variables are not necessarily pairwise independent?

\part Pick a natural number $n$ and define a collection of random variables $X_1, X_2, \ldots, X_n$ such that
\begin{itemize}
\item each $X_i$ is nonnegative,
\item $\ex[X_i] = 1$ for each variable $X_i$,
\item $\var{X_i} = 1$ for each variable $X_i$, but
\item $\prob{\sum_{i=1}^n X_i \geq 2n} > \frac{1}{n}$.
\end{itemize}

This shows that the pairwise independence requirement is essential for part (ii) of this problem to work. Once you've done this, go back to your proof from part (ii) and make sure you can point out the specific spot where the math breaks down once you've removed that requirement.

\begin{solution}
Your solution goes here!
\end{solution}

\end{parts}

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Q{Problem Three: Binary Search Trees}

This one is all coding, so you don't need to write anything here. Make sure to submit your final implementation on myth.
\vspace{.2 in}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Q{Problem Four: Event Planning}

You're trying to figure out what Fun and Exciting Things you'd like to do over the weekend. You download a list of all the local events going on in your area. Each event is tagged with its location, which you can imagine is a point in the 2D plane. (We'll pretend that the world is flat, at least in a small neighborhood around your location. Thanks, multivariable calculus.) You also have your own $(x, y)$ location. 

Design a algorithm that, given some number $k$, returns a list of the $k$ events that are closest to you. Your algorithm should run in time $\bigo{n}$, where $n$ is the number of nearby events (notice that this runtime bound is independent of $k$.) Then prove your algorithm is correct and meets the required time bounds.

Some specific details and edge cases to watch for:
\begin{itemize}
\item Your algorithm can produce the list of the $k$ nearest events in whatever order you'd like.
\item If there are multiple events tied for the same distance, you can break ties arbitrarily.
\item By ``distance", we mean Euclidean distance. We're already assuming the world is flat, so while we're at it seems pretty reasonable to also ignore things like roads and speed limits. \smiley{}
\end{itemize}

A note on this problem, and other problems going forward: when measuring runtime in the context of algorithms and data structures, it's important to distinguish between \emph{\textbf{deterministic}} and \emph{\textbf{randomized algorithms}}. There's a lot of research into how to take \emph{randomized} algorithms with a nice \emph{expected} runtime and convert them into \emph{deterministic} algorithms with a nice \emph{worst-case} runtime. Since this problem set is designed as a warm-up, we'll accept either a deterministic algorithm with a worst-case runtime of $O(n)$ or a randomized algorithm with an expected runtime of $\bigo{n}$, though in the future we'll tend to be a bit stricter about avoiding randomness.

As a hint, think about using a fast selection algorithm.

\begin{solution}
Your solution goes here!
\end{solution}

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

\end{questions}
\end{document}