\documentclass[11pt]{article}
\usepackage{amsmath, amssymb, amsfonts}
\usepackage[margin=1in]{geometry}
\usepackage{fancyhdr}
\usepackage{tcolorbox}
\usepackage{enumerate}
\usepackage{tikz}

\usepackage{algorithmic}

\newcommand{\zo}{\{0,1\}}
\usetikzlibrary{shapes.geometric,arrows,fit,matrix,positioning}
\tikzset
{
    treenode/.style = {circle, draw=black, align=center, 
                          minimum size=1cm, anchor=center}
}

\newcommand{\mfive}{\text{Median5}}

\begin{document}

    \setlength{\headheight}{26pt}
    \pagestyle{fancy}
    \fancyhead[C]{\textbf{Basic Algorithms (Section 7)}\\Fall 2024}
    \fancyhead[R]{HW4 (Due 10/9 22:00)\\ Instructor: Jiaxin Guan}
    \fancyfoot[C]{}
    \fancyfoot[R]{\thepage}
    \renewcommand{\headrulewidth}{0.4pt}
    \renewcommand{\footrulewidth}{0.4pt}
    
    %%%% EDIT THIS PART 
    %Put your name and Net ID here
	\fancyhead[L]{Name:  \\ Net ID: }
    %Write your collaborators' names here
    \fancyfoot[L]{Discussion Partners:}
    %%%%%

     %Problem 1
    \begin{tcolorbox}[title={Problem 1 (Selection Algorithm, 35 pts)}] \setlength\parindent{1em}
        Recall the deterministic selection algorithm for the median that we saw in class (Lecture $8$, but see lecture note $7$). In there, to compute the "approx-median" (element within the middle $40\%$), we break the elements into small sets of size $5$, compute the median for each small set, and then output the median of these $n/5$ medians as the "approx-median".
        \begin{enumerate}[(a)]
           \item If instead of breaking into small sets of size $5$, we break into small sets of size $3$:
           \begin{enumerate}[i.]
               \item Will the "approx-median" we get in this way still be in the middle $40\%$? Find $k$, such that the "approx-median" we get will be guaranteed to be in the middle $k$ portion. For example, if it is guaranteed to be in the middle $40\%$, then $k=\frac{2}{5}$. Justify your answer, and $k$ should be as tight (small) as possible.
               \item Will the deterministic selection algorithm be still correct in this case? Briefly justify your answer.
               \item Give a recurrence relation for the runtime of this version of the deterministic selection algorithm. Can we still argue that it is in linear time? Justify your answer.
           \end{enumerate}
           \item If instead of breaking into small sets of size $5$, we break into small sets of size $7$:
           \begin{enumerate}[i.]
               \item Will the "approx-median" we get in this way still be in the middle $40\%$? Find $k$, such that the "approx-median" we get will be guaranteed to be in the middle $k$ portion. Justify your answer, and $k$ should be as tight (small) as possible.
               \item Will the deterministic selection algorithm be still correct in this case? Briefly justify your answer.
               \item Give a recurrence relation for the runtime of this version of the deterministic selection algorithm. Can we still argue that it is in linear time? Justify your answer.
           \end{enumerate}
           \item Any advantages of using 5 as opposed to some other number? In other words, was our choice of $5$ arbitrary?
       \end{enumerate}
    \end{tcolorbox}
    %Write your solution here!


    \newpage
    %Problem 2
    \begin{tcolorbox}[title={Problem 2 (Finding Duplicates, 30 pts)}] \setlength\parindent{1em}
        Consider an array $A$ of $n$ elements where each element appears exactly twice in $A$, e.g. $A=[9, 7, 7, 1, 9, 1, 3, 5, 3, 5]$. For any two elements $A[i]$, $A[j]$ in the array, we may only compare the elements by testing equality, i.e., $A[i] \overset{?}{=} A[j]$. With this in mind,
        \begin{enumerate}[(a)]
            \item Give an algorithm that returns two indices in $A$ that have the same element using at most $n-2$ comparisons/equality tests. \emph{Note: there are multiple pairs of these indices, and only outputting one pair is sufficient. For example, $(1, 5), (2, 3), (4, 6), (7, 9), (8, 10)$ are all valid outputs of this algorithm on $A$.}
            \item Prove that your algorithm really needs $n-2$ comparisons in the worst case (i.e., there are inputs where it uses that many comparisons before terminating). Specifically, give an example of a worst-case input for $n = 10$. Note that this worst-case input only needs to work for \emph{your} algorithm in part (a), not \emph{any} algorithm.
        \end{enumerate}
    \end{tcolorbox}
    %Write your solution here!

    %Problem 3
    \begin{tcolorbox}[title={Problem 3 (Minimum and Maximum — Lower Bound, 35 pts)}]\setlength\parindent{1em}
    
    Suppose we have an array $A$ of $n$ distinct integers, and we want to find both the minimal and the maximal number. In Lecture $8$ (see lecture note $7$ though) we saw how to do this using $\frac{3n}{2} + O(1)$ comparisons, as opposed to the na\"{i}ve algorithm that uses $2(n-1)$ comparisons by making two separate passes to find the minimum and the maximum separately. Here, we will show that this is actually optimal in the comparison model by proving a lower bound of $\frac{3n}{2} - O(1)$ (and therefore the complexity of this problem is $\frac{3n}{2} + \Theta(1)$).

    \vspace{1em}
    
    For the lower bound, suppose there is an \emph{arbitrary} comparison-based algorithm that finds the minimum and maximum of $A$. Suppose we run this algorithm on some input and consider the situation after some step of the algorithm. Let us say that the element of the array has \emph{lost} comparison if it was compared with some other element and turned out to be smaller. Let us say that the element has \emph{won} comparison if it was compared to another element and it turned out to be larger. 

    \vspace{1em}
    
    Consider the following three parameters: 
    \begin{enumerate}
        \item Let $a$ be the number of elements of the array that have not been compared at all.
        \item Let $b$ be the number of elements that have both lost and won comparisons.
        \item Let $c$ be the number of elements that have either only lost or only won comparisons (at least $1$ comparison).
    \end{enumerate}
    
    \begin{enumerate}[(a)]
        \item What are the values of $a$, $b$, and $c$ at the beginning of the algorithm — before any comparisons are made?
        \item What are the values of $a$, $b$, and $c$ at the end of the algorithm — after the algorithm successfully found the largest and the smallest numbers?
        \item What relationship do $a$, $b$, and $c$ fulfill throughout the execution of the algorithm?
        \item Describe an adversarial strategy for answering comparison queries (consistent with some input) that makes the parameters $a$, $b$, and $c$ change as little as possible through the execution of the algorithm. Notice that you cannot control which elements are compared each time; you can only control the outcome. So you might want to produce the comparison outcome depending on the inputs. Deduce the $\frac{3n}{2} - O(1)$ lower bound in the comparison model.
    \end{enumerate}
    \end{tcolorbox}
    %Write your solution here!
    
\end{document}