\documentclass[12pt,letterpaper]{article}
\usepackage{fullpage}
\usepackage[top=2cm, bottom=4.5cm, left=2.5cm, right=2.5cm]{geometry}
\usepackage{amsmath,amsthm,amsfonts,amssymb,amscd}
\usepackage{lastpage}
\usepackage{ulem}
\usepackage{enumerate}
\usepackage{fancyhdr}
\usepackage{mathrsfs}
\usepackage{graphicx}

\setlength{\parindent}{0.0in}
\setlength{\parskip}{0.05in}
% Edit these as appropriate
\newcommand\course{CSCI 1550 / 2540}
\newcommand\hwnumber{2}             % <-- homework number
\newcommand\Namea{Partner 1}           % <-- Name of partner #1
\newcommand\Nameb{Partner 2}     
\newcommand\Namec{Partner 3}  
\newcommand{\DUEDATE}{March 6, 2025}
\usepackage{subfiles} % Best loaded last in the preamble

\pagestyle{fancyplain}
\headheight 35pt
\lhead{\Namea \\ \Nameb \\ \Namec}
\chead{\textbf{\Large Homework \hwnumber}}
\rhead{\course \\ February 20, 2025}
\lfoot{}
\cfoot{}
\rfoot{\small\thepage}
\headsep 1.5em

\begin{document}

\begin{center}
    \vspace{10pt}
    \textit{Due:} \DUEDATE\\
    Remember to show your work for each problem to receive full credit.
\end{center}
\section*{Problem 1 (40 Points)}

In this exercise, we design a randomized algorithm for the following packet routing problem. We are given a network that is an directed connected graph $G$, where nodes represent processors and the edges between the nodes represent wires. We are also given a set of $N$ packets to route. For each packet we are given a source node, a destination node, and the exact route (path in the graph) that the packet should take from the source to its destination. (We may assume that there are no loops in the path.) In each time step, at most one packet can traverse any single edge. A packet can wait at any node during any time step, and we assume unbounded queue sizes at each node.

A \textit{schedule} for a set of packets specifies the timing for the movement of packets along their respective routes. That is, it specifies which packets should move and which should wait at each time step. Our goal is to produce a schedule for the packets that tries to minimize the total time and the maximum queue size needed to route all the packets to their destinations.

\begin{enumerate}[(a)]
    \item The dilation $d$ is the maximum distance traveled by any packet. The congestion $c$ is the maximum number of packets that must traverse a single edge during the entire course of the routing. Argue that the time required for any schedule should be at least $\Omega(c + d)$.

    \item Consider the following unconstrained schedule, where many packets may traverse an edge during a single time step. Assign each packet an integer delay chosen randomly, independently, and uniformly from the interval $[1, \lceil \frac{\alpha c}{\log(Nd)}\rceil]$, where $\alpha\leq 1$ is a constant. A packet that is assigned a delay of $x$ waits in its source node for $x$ time steps; then it moves on to its final destination through its specified route without ever stopping. Prove that with probability $1-(Nd)^{-\frac{1}{3\alpha}}$
    no more than $\frac{2\log (Nd)}{\alpha}$ packets use a particular edge E, at a particular step t.

    \item Again using the unconstrained schedule of part (b), show that there exists a constant $\alpha$ such that the probability that more than $O(\log(Nd))$ packets pass through any edge at any time step is at most $\frac{1}{Nd}$.
    [Hint: argue that since there are $N$ packets, and each packet traverses $\leq d$ edges, we need to apply union bound over no more than $Nd$ events.]

    \item Use the unconstrained schedule to devise a simple randomized algorithm that, with high probability (in $N$), produces a schedule of length $O(c + d\log(Nd))$ using queues of size $O(\log(Nd))$ and following the constraint that at most one packet crosses any single edge per time step.

\end{enumerate}




\newpage
\section*{Problem 2 (20 points)}
In many wireless communication systems, each receiver listens on a specific frequency. The bit $b(t)$ sent at time $t$ is represented by a 1 or $-1$. Unfortunately, noise from other nearby communications can affect the receiver's signal. A simplified model of this noise is as follows. There are $n$ other senders, and the $i$th has strength $p_{i} \leq 1$. At any time $t,$ the $i$th sender is also trying to send a bit $b_{i}(t)$ that is represented by 1 or $-1$. The receiver obtains the signal $s(t)$ given by
\[s(t) = b(t) + \sum_{i=1}^n p_i b_i(t)\]
If $s(t)$ is closer to 1 than $-1,$ the receiver assumes that the bit sent at time $t$ was a 1 otherwise, the receiver assumes that it was a $-1$.

Assume that all the bits $b_{i}(t)$ can be considered independent, uniform random variables. Give a Chernoff bound to prove the probability that the receiver makes an error in determining $b(t)$ is less than or equal to following quantity
\[ \exp(\frac{-1}{2 \sum_{i = 1}^n p_i^2}).\]

\newpage
\section*{Problem 3 (35 points)}
Bob is facing a very challenging math question in \textbf{CSCI1550/2540}. Even if this math question is very hard, it has a simple binary answer $Y \in \{0,1\}$ (both answers are equally likely). Bob asks for help from $n$ fellow math-loving friends (numbered from $1$ to $n)$, and each of them provides an answer to this math question. However, as this math question is very hard, there is no guarantee that these answers are the same. In particular, friend $i$ provides an answer $X_i \in \{0, 1\}$, for $i=1,\ldots,n$. Bob knows the expertise of each friend; in particular, he knows that for each $i=1,\ldots,n$, we have that:
  \begin{align*}
    X_i =
    \begin{cases}
      Y  \hspace{15pt} &\mbox{ with probability } p_i >1/2\\
      1-Y \hspace{15pt} &\mbox{ with probability } 1-p_i
    \end{cases}
  \end{align*}
Formally, $X_1,\ldots,X_n$ are random variables function of $Y$. Bob also assumes that these friends won't collaborate with each other; that is, given $Y$, the random variables $X_1,\ldots,X_n$ are independent.

Bob wants to use a function $f(X_1,\ldots,X_n) : \{0,1\}^n \rightarrow \{0,1\}$ to obtain the final answer to the hard math problem. He would like to minimize the error that the function $f$ makes a mistake, i.e., he wants to minimize:
\begin{align}
\label{minimization}
    \Pr( f(X_1,\ldots,X_n) \neq Y) 
\end{align}
If a function $f$ minimizes $\eqref{minimization}$, we say that $f$ is optimal. Let $\vec{X} = (X_1,\ldots,X_n)$.

\begin{enumerate}[(a)]
    \item For $y \in \{0,1\}$, let 
    \begin{align*}
    g(\vec{x},y) = \Pr( \vec{X}=\vec{x} | Y = y ) = \prod_{i : x_i = y} p_i  \prod_{i : x_i = 1-y} (1-p_i) =
    \exp \left ({\sum_{i : x_i = y}
    \log p_i + \sum_{i : x_i = 1-y} \log (1-p_i)}\right )
\end{align*}
   Show that a function $f$ is optimal if and only if for any $\vec{x} \in \{0,1\}^n$, it holds that
   \begin{align*}
        f(\vec{x}) = \arg\max_{y \in \{0,1\}} g(\vec{x},y)
    \end{align*}
\end{enumerate}



\begin{enumerate}[(b)]
\item Bob considers a family of functions that is called weighted majority vote. That is, he wants to assign a different weight to the answer of the different friends, based on their competence. Let $\vec{w} = (w_1,\ldots,w_n) \in \mathbb{R}^n$. Given $\vec{w}$, we define:
\begin{align*}
    f(\vec{x}; \vec{w}) = 
    \begin{cases}
      1  \hspace{15pt} &\mbox{if }\sum_{i=1}^n X_i w_i \geq \sum_{i=1}^n (1-X_i) w_i \\
      0 &\mbox{otherwise}
    \end{cases}
\end{align*}
    Let $\vec{w}^* = (w_1^*, \ldots, w_n^*)$, where $w_i^* = \ln \left( \frac{p_i}{1-p_i} \right)$. Use the answer to question $a.$ to  show that the function $f( \bullet ; \vec{w}^*)$ is optimal.
\end{enumerate}

\begin{enumerate}[(c)]
\item Let $f^*(\bullet) = f( \bullet ; \vec{w}^*)$. Use Hoeffding's bound to show an upper bound on the error probability
\begin{align*}
    \Pr( f^*(X_1,\ldots,X_n) \neq Y)
\end{align*}
\textbf{Hint}: Show that if $f^*(X_1, ..., X_n) \neq Y$, then the sum of weights $w_i$, whose corresponding answer $X_i$ is correct, is less than or equal to $\frac{1}{2} \sum_{i = 1}^n w_i$.
\end{enumerate}

\begin{enumerate}[(d)]
\item Suppose that for each $i=2,\ldots,n$, we have that $p_i = 0.9$, and let $p_1 \rightarrow 1$. What happens to the upper bound computed in question $c.$? Is this upper bound useful or not in this scenario?
\end{enumerate}

\newpage
\section*{Problem 4 (25 points)}

This problem demonstrate the difference between additive and multiplicative error deviation bounds.

Let $G = (V,E)$ be an undirected graph, $V= \{ 1,\ldots,n \}$ and $E \subseteq \{ \{i,j\} : i,j \in V \mbox{ and } i \neq j \}$.
We know the number of vertices $|V|=n$. We want to estimate the  fraction of pairs $\{i,j\}$ of  connected by an edge, $\rho = m/ \binom{n}{2}$, where $m = |E|$.
We can query an oracle, that given a pair $\{i,j\}$, tells us if $i$ and $j$ are connected by an edge in the graph $G$, i.e. whether $\{i,j\} \in E$ or not. 


\begin{enumerate}[(a)]
\item {\bf Additive error bound:} Use the Hoeffding's bound to bound the number of queries of pairs, chosen uniformly at random, needed to estimate $\rho$ within an $\epsilon$ additive error, i.e. output $\tilde{\rho}$ such that 
$|\tilde{\rho}-\rho|\leq \epsilon$ with probability at least $1 - \delta$.

\item {\bf Multiplicative error bound:}
\begin{enumerate}[1.]

    \item Assume that you given a lower bound $d$ on the fraction $\rho$. If this lower bound is true, how many random queries are needed to find an estimate $\tilde{\rho}$ that satisfies an $\epsilon$ multiplicative error, i.e.
    $|\tilde{\rho}-\rho|\leq \epsilon\rho$, with probability at least $1-\delta$?
    
    \item
    Assume now that you don't have a lower bound of $\rho$. Design and analyze an algorithm that estimates $\rho$ with a number of sample adjusted to the unknown $\rho$. [\textbf{Hint:} Assume first that $\rho >1/4$, if the condition doesn't hold assume $\rho >1/8$, etc. Remember to bound the total error probability. ]
\item For which values of $\rho$ is it better to just check all pairs?
\end{enumerate}
\end{enumerate}
\end{document}