\oddsidemargin=-1.0in                        % Left margin minus 1 inch.
\evensidemargin=-1in                         % Same for even-numbered pages.
\textwidth=8.5in                             % Text width (8.5in - margins).
\topmargin=-1in                              % Top margin minus 1 inch.
\headsep=0.7in                               % Distance from header to body.
\textheight=10in                             % Body height (incl. footnotes)

\documentclass[10pt]{article}
\usepackage{fullpage}
\usepackage{fancyhdr}
\pagestyle{fancyplain}
\usepackage{amssymb}
 
\addtolength{\headheight}{2 pt}

\lhead{\small \bf CSCI 1550}
\chead{}
\rhead{\small {\bf Spring \number\year}}

\lfoot{}
\cfoot{\small \thepage}
\rfoot{}

%\setlength{\footrulewidth}{0.0 pt}

\usepackage{float}

\floatstyle{boxed}
\newfloat{ImpText}{htbp}{loa}
\floatname{ImpText}{ImpText}

\newcommand{\problem}[1]{\subsection*{Problem #1}}
\newcommand*\Rade{\mathsf{R}}
\newcommand*\Erade{\hat{\Rade}}

\begin{document}
\begin{center}
  $ $
  
  \huge\bf{Final Examination (Take Home)}
\end{center}

\begin{center}
{\large Out: Thursday, April 10, \number\year\\
Due: Tuesday, April 24, \number\year\ } 
\end{center}

\underline{\bf Exam instructions (please read carefully):} 

\begin{itemize}
\item \textbf{Allowed resources.} You are allowed to consult the course
web site, your notes, and the course textbook. You are not allowed to 
use other resources, such as other books, other web sites, or other people.

\item \textbf{Non-collaboration.} No collaboration is permitted on this
exam. It is trusted that you will not discuss this exam or related course
material with any other person (classmate or otherwise). You must abide by
the Brown University Academic Code concerning examinations, quizzes, and
tests (see
\verb+http://goo.gl/mQtfSa+).

\item \textbf{Questions.} There will be no TA hours April 10-24. For any clarification of possible textual ambiguities email \verb+cs1550tas@lists.brown.edu+ with
your question.
\emph{We will post clarifications (anonymously) to Ed Discussion.}

\item \textbf{Handing in.} Submit to Gradescope by the due date.
\end{itemize}
\vspace{-.5cm}

\begin{ImpText}
{\bf PLEASE SIGN (failure to sign voids the exam)}: I solemnly
state that I have abided by the exam instructions stated above, including the tenets of the Brown University Academic Code concerning examinations, quizzes and tests.
\medskip
\begin{center}
\begin{tabular}{rl}
        {\bf Signature:}           &    \rule{10cm}{0.5mm} \\
\medskip        &       \\
        {\bf Name (please print):} &    \rule{10cm}{0.5mm} \\

\end{tabular}
\end{center}
\end{ImpText}
\vspace{-.5cm}

\rule{6.0in}{1mm}


\clearpage

\setlength{\headsep}{1cm}

\begin{center}
\textbf{\large GENERAL EXAM INSTRUCTIONS ON PREVIOUS PAGE}
\end{center}

\bigskip

\section* {Problem~1 (20 points)}
Suppose we are given an $n$-vertex undirected graph $G=(V,E)$, where the
vertices are numbered $1,2,\dots,n$. An independent set of~$G$ is a
subset~$W\subseteq V$ of the vertices such that there is not an
edge~$e\in E$ connecting two vertices in~$W$.
We wish to find a (hopefully large)
independent set in $G$. Given a permutation $\sigma$ of the vertices,
define a subset $S(\sigma)$ of the vertices as follows: for each
vertex $i,\ i\in S(\sigma)$ if and only if no neighbor $j$ of $i$
precedes $i$ in the permutation $\sigma$.
\begin{enumerate}
\item Show that each $S(\sigma)$ is an independent set in $G$.
\item Suggest a natural randomized algorithm to produce $\sigma$ for
which you can show that the expected cardinality of $S(\sigma)$ is
\[\sum_{i=1}^n\frac1{d_i+1},\]
where $d_i$ denotes the degree of vertex $i$.
\item
Prove that $G$ has an independent set of size at
least $\sum_{i=1}^n\frac1{d_i+1}$.
\end{enumerate}

\section* {Problem~2 (20 points)}
Consider the following model for a digital communication channel with noise.  Alice wants to communicate a message $m$ to Bob.  First, Alice encodes $m$ as a string $s$ of length $n$, using an error-correcting code.  This means that it is enough for Bob to have $n(1 - q)$ correct bits of $s$ (where $q$ is a constant between 0 and 1) in order to correctly decode it and obtain Alice's original message $m$.  That is, if Bob has a string $s'$ that matches $s$ in at least $n(1 - q)$ places, then Bob can recover $m$.

Each bit that Alice sends over the channel is received correctly by Bob with probability $p > 1/2$, independently of other bits.  Alice wants to send $s$ over the channel, but to improve the probability that Bob can recover $m$, Alice sends $s$ several times and Bob takes the majority value for each bit to obtain $s'$.  Bob then attempts to recover $m$ from $s'$.

\begin{enumerate}
\item Fix a constant $r \in (0, 1)$. How many times does Alice need to send $s$ so that the probability that a given bit of $s$ has a correct majority is at least $1-r$?

\item Now, for which values of $r \in (0, 1)$ does Alice need to use so that Bob can recover $m$ correctly with probability at least $1-\epsilon$? You can give an inequality involving $r$, instead of solving for $r$ explicitly.
\end{enumerate}

\section*{Problem~3 (20 points)}
\begin{enumerate}
\item Given two range spaces $(X, \mathcal{R}_1)$ and $(X, \mathcal{R}_2)$, each with VC-dimension $d$, we define a ``union'' range space $(X, \mathcal{R}_{1\cup 2})$:
$$
\mathcal{R}_{1\cup 2} = \{r_1 \cup r_2 \mid r_1\in \mathcal{R}_1 \mbox{ and } r_2\in \mathcal{R}_2 \}.
$$

Prove that the VC dimension of $\mathcal{R}_{1\cup 2}$ is $O(d)$.

You may use without proof the result of Exercise 14.9: for $n \ge 2d$ and $d \ge 1$, the growth function satisfies $G(d, n) = \sum_{i = 0}^d %\binom{n}{i}
{n \choose i}
\le 2\left(\frac{ne}{d}\right)^d$. (You may not use Theorem 14.5 or Corollary 14.6 directly, because those results are not proven in the book.)

\item The Martian citizens are electing a new leader and Jupiter's evil team is trying to influence the election results. To maximize its influence the Jupiter team wants to identify the 5 circles of Martian population most likely to vote for candidate Good.

Let $C=\{S_1,\ldots,S_5\}$ be a set of 5 circles (each $S_i$ is a circle). For a location (point) $X$ on the map, we denote $X\in C$ if $X\in \cup_{i=1}^5 S_i$. We also denote $P$ as the set of all Martian locations planning to vote for  candidate Good. Define the \textbf{error} of $C$ as
$$
\textrm{err}(C) = \textrm{Pr}(X\in P,X\notin C) + \textrm{Pr}(X\notin P,X\in C),
$$
which measures how well $C$ minimizes the coverage of places not voting for Good and maximizes the coverage of locations voting for Good. Let $C^*$ be the set of the 5 circles with minimum error.
The Jupiter team can sample uniformly at random a locations in the country and check who they plan to vote for. For a given $\epsilon>0$, their goal is to find a set $C'$ such that $\textrm{err}(C')\leq \textrm{err}(C^{*})+\epsilon$. How many samples do they need in order to find such a set of 5 circles with probability at least $1-\delta$, for $\delta\in (0,1)$? You can give the sample complexity using big $O(\cdot)$ notation. [You can use the known fact that all Martians live in a 2-D planar region.]
\end{enumerate}

\section*{Problem 4  (20 points)}
Consider a random walk $Z_t = (X_t, Y_t)$ on the the 2-dimension integer grid.
The walk starts at point $Z_0=(0,0)$, and
at each step the walk moves with equal probabilities one step left, right, up or down. I.e.
\[
Pr(Z_t=(x,y)~|~Z_{t-1}=(x',y')) =
\left \{ \begin{array}{ll}
1/4 &\mbox{if $x=x'+1$ and $y=y'$} \\
1/4 &\mbox{if $x=x'-1$ and $y=y'$} \\
1/4 &\mbox{if $x=x'$ and $y=y'+1$} \\
1/4 &\mbox{if $x=x'$ and $y=y'-1$} \\
0 & \mbox{otherwise}
\end{array} \right .
\]

\begin{enumerate}
    \item Answer the following questions.
    \begin{enumerate}
        \item Show that each of the sequences $X_0,X_1, \ldots$ and
         $Y_0,Y_1, \ldots$ are martingales.
        \item Let $A_t = X_t + Y_t$ for $t \geq 0$. Show that the sequence $A_0, A_1, \ldots$ is a martingale.
    \end{enumerate}
    \item Fix a value $t \geq 0$. Define a (small) set $S(t)$ of points on the grid, such that
    $$Pr(Z_t \not\in S)\leq \delta <1 .$$
    The total number of points in $S(t)$ should be $O(t\ln (1/\delta))$.
\end{enumerate}

\section*{Problem 5 (20 points)} 
\begin{enumerate}
\item We prove an extension of the Chernoff bound that 
was implicitly assumed in class. 
Let $X = \sum_{i=1}^n X_i$, where the $X_i$'s are independent 0-1 random
variables.  Let $\mu = E[X]$.  Choose any $\mu_L$ and $\mu_H$ such that
$\mu_L \le \mu\le \mu_H$.  Prove the following:
\begin{enumerate}
\item For any $\delta > 0$,
$$Pr(X \ge (1 + \delta)\mu_H) 
\le \left(\frac{e^{\delta}}{(1 + \delta)^{(1 + \delta)}}\right)^{\mu_H}.$$
\item For any $0 < \delta < 1$,
$$Pr(X \le (1 - \delta)\mu_L) 
\le \left(\frac{e^{-\delta}}{(1 - \delta)^{(1 - \delta)}}\right)^{\mu_L}.$$
\end{enumerate}

[Hint: Contract random variable $Y_{1},\dots, Y_{n}$ and $Z_{1},\dots, Z_{n}$ such that for all $1\leq i\leq n$, we always have $Y_{i} \leq X_{i}\leq Z_{i}$, and their sums have the required expectations.]
\item
An $(\epsilon,\delta)$-confidence interval for an unknown constant $T$ is a (random) interval $[A-\epsilon, A+\epsilon]$ such that
$$Pr(T\not\in [A-\epsilon, A+\epsilon])\leq\delta.$$

Let $X_{1},\dots,X_{n}$ be $n$ independent observations such that $X_{i}=1$ with unknown probability $P$, otherwise $X_{i}=0$. Let $\bar{X}=\frac{1}{n}\sum_{i=1}^{n}X_{i}$. Use the first part of this question to bound the error probability $\delta$ of the 
confidence interval $[\bar{X}-\epsilon,\bar{X}+\epsilon]$ for $P$.
\end{enumerate}

\end{document}