%Do not change
\documentclass[12pt, oneside]{article}
\usepackage{amssymb,amsmath,amsthm}
\usepackage[margin=1in]{geometry}
\usepackage{textpos}
\usepackage{mathtools}
\usepackage{xspace}
\usepackage{enumitem}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}
\newcommand\myeq{\stackrel{\mathclap{\normalfont\mbox{?}}}{=}}
\newcommand\eq{\stackrel{\mathclap{\normalfont\mbox{def}}}{=}}
% You may add the packages you need here
\newcommand\rd{\textsuperscript{rd}\xspace}
\newcommand\nth{\textsuperscript{th}\xspace}
\begin{document}
% Do not modify
%Do not modify other than putting your name, Purdue ID and names of collaborators where stated
\begin{textblock*}{30cm}(-1.7cm,-2.3cm)
\noindent {\large CS 381-Fall 2019} \\
\noindent {\large Name: } \\
\noindent {\large Purdue ID: } \\
\noindent {\large Date: \today}
\end{textblock*}
\vspace{1cm}
%Do not modify other than typing the homework number after #
\begin{center}
\textbf{\Large Homework 2} \\
\textbf{Due Date: September 16, 2019 at 11:59PM on Gradescope.} \\
\textbf{Instructor: Jeremiah Blocki}\\
\end{center}
\subsection*{Homework Guideline Reminders}
\begin{itemize}
\item Assignments must be typed. Submit one pdf file to Gradescope by 11:59PM, or else late penalties will apply. The pdf file can include hand-drawn images of figures.
\item Each question needs to start with the resources and collaborator (RC) statement. You will not be penalized for using resources or having collaborators if your answers are expressed in your own words. If you consulted no resources outside of course material or had no collaborators, you must state so. A question without a complete RC statement will not be graded.
\end{itemize}
\subsection*{Question 1: Recurrences (28 points)}
Find upper and lower bounds for the following functions (big $O$ and $\Omega$). You may use the Master Theorem without proof (when applicable), but you should explain which case is being used. If you solve the recurrence using another technique you will need to prove that your solution is correct. You may assume that $1 \leq T(n) \leq 381^{2020}$ whenever $1 \leq n \leq 100$.
\begin{enumerate}[label=\textbf{(\alph*)}]
\item T(n) = 8T(n/5) + $n^5 $ \hfill (3 points)
\item T(n) = 5T($n^{1/10}$) + 2$\log_2 n$\hfill(3 points)
\item T(n) = 5T(n/2) + $n^{log_{7} 22}\cdot \log(n^2) $\hfill (3 points)
\item T(n) = $n + \sum_{i=1}^{k}$ T($a_i n$) where $\sum_{i=1}^k a_i = 1-\epsilon$ for some constants $\epsilon > 0$, $k\geq 1$ and $a_i > 0$ for each $i \leq k$. \hfill (5 points)
\item T(n) = $n + \sum_{i=1}^{k} $ T($a_i n$) where $\sum_{i=1}^k a_i = 1$ and $a_i > 0$ for each $i \leq k$. You may assume that $k \geq 2$ is a constant. \hfill (5 points)
\item T(n) = 36T(n/9) + $10n \cdot n^{\log_3 112}$ \hfill (3 points)
\item T(n) = 9T(n/3) + $n^2$ \hfill (3 points)
\item T(n) = T(n-1) + 2020$n^{2020}$ \hfill (3 points)
\end{enumerate}
\medskip
\noindent {\bf Resources: }
\\
\noindent {\bf Collaborators: }
\\
\noindent {\bf Solution: } \\
\subsection*{Question 2: Linear Time Selection (22 points)}
Consider the algorithm $\mathtt{FindKthLargest}$ (defined below) which takes as input an (unsorted) array $x_1,\ldots,x_n$ and an integer $k$ and outputs the $k$th smallest item in the array. Formally, if $y_1,\ldots, y_n = \mathtt{Sort}(x_1,\ldots,x_n)$ then the algorithm should return $y_k$.
\begin{enumerate}[label=\textbf{(\alph*)}]
\item The algorithm $\mathtt{FindKthLargest}$ is parameterized by an integer $t \geq 1$. When $t=2$ we have $(2t+1)=5$ and we get the ``Median of Fives'' algorithm discussed in class. Write down a recurrence describing the running time of this algorithm. Use this recurrence to upper/lower bound the running time.
\item The algorithm $\mathtt{FindKthLargest}$ is still correct when we set $t=1$. Write down a recurrence describing the running time of this algorithm. Use this recurrence to upper/lower bound the running time.
\item Write down the general recurrence describing the running time of $\mathtt{FindKthLargest}$ when $t > 2$. What is the running time of the algorithm when $t$ is a constant greater than 2?
\item Use induction to prove that the algorithm $\mathtt{FindKthLargest}$ (described below) is correct.
\end{enumerate}
\begin{algorithm}[H]
\begin{algorithmic}[1]
\caption{$\mathtt{FindKthLargest}\left( \{x_1,\ldots,x_n\}, k\right) $}
\State If $n \leq (2t+1)$ then sort the list $\{x_1,\ldots,x_n\}$ to obtain $y_1 \leq y_2 \leq ... \leq y_n$ and return $y_k$.
\State Partition $x_1,\ldots, x_n$ into $n/(2t+1)$ groups
$$G_1 = \{x_1,\ldots,x_{2t+1}\},
G_2 = \{x_{2t+2},\ldots, x_{4t+2}\}, \ldots $$
and compute the median $y_i$ of each group $G_i$ by setting
$$y_i \leftarrow \mathtt{FindKthLargest}(G_i,t+1). $$
\State Recursively compute the median $y_{med}$ of the list $y_1,\ldots,y_{n/(2t+1)}$ by running
$$ y_{med} \leftarrow \mathtt{FindKthLargest}\left( \{y_1,\ldots,y_{n/(2t+1)}\}, k=n/(4t+2)\right)$$
\State Split $x_1,\ldots, x_n$ into lists
$$L = \{x_i : x_i < y_{med}\},$$
$$M=\{x_i : x_i = y_{med}\},$$
$$R = \{ x_i : x_i > y_{med}\}.$$
\State If $k \leq |L|$ then return $\mathtt{FindKthLargest}\left( L, k\right)$; else if $k \leq |L| +|M|$ return $y_{med}$; otherwise return $\mathtt{FindKthLargest}\left(R, k-|L|-|M|\right)$.
\end{algorithmic}
\end{algorithm}
\medskip
\noindent {\bf Resources: }
\\
\noindent {\bf Collaborators: }
\\
\noindent {\bf Solution: } \\
\subsection*{Question 3: Divide and Conquer (25 points)}
After invading Zone 51, invaders have gathered $n$ items with distinct positive weights and stacked them in a pile. A pair of items in the pile is said to be ``$\gamma$-unbalanced" for $\gamma \geq 1$ if the weight of the upper item times $\gamma$ exceeds (is strictly greater than) the weight of the lower item. Moving the pile in a vehicle is very risky unless stacked in a particular order of weights from top to bottom such that there is no $\gamma$-unbalanced pairs. Such an ordering is called a $\gamma$-ordering. Invaders want to know how far the pile is from $\gamma$-ordering. Invaders are in a time constraint as they are being chased by security personnel; given a specific $\gamma$, they need an efficient algorithm to compute the number of $\gamma$-unbalanced pairs in the pile. Note that invaders do not need the actual $\gamma$-ordering, once they know the number of $\gamma$-unbalanced pairs, they can do the $\gamma$-ordering by themselves.
\begin{enumerate}[label=\textbf{(\alph*)}]
\item Help the invaders by providing such a divide and conquer algorithm to find the number of $\gamma$-unbalanced pairs. Prove the correctness of your algorithm.
\item Convince the invaders that your algorithm is efficient by showing time complexity analysis. State and explain the recurrence relation describing the running time of your algorithm. Solve the recurrence and provide the asymptotic running time.
\end{enumerate}
\medskip
\noindent {\bf Resources: }
\\
\noindent {\bf Collaborators: }
\\
\noindent {\bf Solution: } \\
\subsection*{Question 4: Divide and Conquer (25 points)}
Jane was given a square matrix of size $n \times n$ with entries 0's and 1's, the goal was to come up with an efficient divide and conquer algorithm to find the length of the longest sequence of 1's in the matrix. The sequence can be horizontal or vertical, in other words, it can be contiguous sequence of 1's in a row or in a column. Note that a combination of of both horizontal and vertical is NOT valid, for example, L shaped figures are not to be considered. \\\\
Jane devised the following algorithm to solve the problem:
\begin{enumerate}
\item If matrix is size $1\times 1$, return value of the single element.
\item Divide matrix into 4 quadrants each having side of length $\frac n 2$. Recursively find the longest sequences in each quadrant: $S_1, S_2, S_3, S_4$.
\item In the combine step, compare each pair of adjacent quadrants. For each pair, check the length of all possible sequences of 1s that go across the two quadrants. For instance, if we are looking at quadrants 1 and 2, for each row, count the number of consecutive 1s on the right side of the row in quadrant 1 and on the left side of the row in quadrant 2, and sum them to obtain the longest sequence of 1s in that particular row across the two quadrants. Choose the row with the maximum length sequence of 1s found. We will end up with the lengths of the longest sequences of 1s between each pair of adjacent quadrants: $S_{12}, S_{23}, S_{34}, S_{41}$.
\item Return maximum of all values: longest sequences in each quadrant and calculated lengths of sequences that go across quadrants. That is,
$$\max (S_1, S_2, S_3, S_4, S_{12}, S_{23}, S_{34}, S_{41})$$
\end{enumerate}
For this problem,
\begin{enumerate}[label=\textbf{(\alph*)}]
\item State and explain the recurrence relation describing the running time of Jane's algorithm. Solve the recurrence and provide the asymptotic running time.
\item Unfortunately, Professor Blocki is not happy with the run-time of her algorithm. He believes she can do better. Can you help Jane by tweaking her algorithm to give a divide and conquer solution with a better runtime? Clearly specify the divide step, conquer step, and what values are returned during each iteration. You must use divide and conquer even if there are other simpler solutions.
\item State and explain the recurrence relation describing the running time of your modification of Jane's algorithm. Solve the recurrence and provide the asymptotic running time.
\end{enumerate}
\medskip
\noindent {\bf Resources: }
\\
\noindent {\bf Collaborators: }
\\
\noindent {\bf Solution: } \\
\end{document}