%---------change this for every latex homework
\def\yourid{mst3k}
\def\collabs{list collaborators's computing IDs}
\def\sources{Cormen, et al, Introduction to Algorithms. \emph{(add others here)}}
% -----------------------------------------------------
\def\duedate{Friday, March 4, 2022 at 11:30 pm }
\def\duelocation{via Gradescope}
\def\htype{Adv}
\def\hunit{A}
\def\hnumber{}
\def\course{{cs4102 - algorithms - spring 2022}}%------
%-------------------------------------
%-------------------------------------
\documentclass[10pt]{article}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[osf]{mathpazo}
\usepackage{amsmath,amsfonts,graphicx}
\usepackage{latexsym}
\usepackage[top=1in,bottom=1.4in,left=1.25in,right=1.25in,centering,letterpaper]{geometry}
\usepackage{color}
\definecolor{mdb}{rgb}{0.1,0.6,0.4}
\definecolor{cit}{rgb}{0.05,0.2,0.45}
\pagestyle{myheadings}
\markboth{\yourid}{\yourid}
\usepackage{clrscode}
\usepackage{tabularx}
\newcolumntype{Y}{>{\centering\arraybackslash}X}
\newenvironment{proof}{\par\noindent{\it Proof.}\hspace*{1em}}{$\Box$\bigskip}
\newcommand{\handout}{
\renewcommand{\thepage}{Unit \hunit: \htype~Homework \hnumber~-~\arabic{page}}
\noindent
\begin{center}
\vbox{
\hbox to \columnwidth {\sc{\course} \hfill}
\vspace{-2mm}
\hbox to \columnwidth {\sc due \MakeLowercase{\duedate} \duelocation\hfill {\Huge\color{mdb}\hunit\hnumber{\Large\MakeLowercase{\htype}}(\yourid)}}
}
\end{center}
\vspace*{1mm}
\hrule
\vspace*{1mm}
{\footnotesize \textbf{Collaboration Policy:} You are encouraged to collaborate with up to 3 other students, but all work submitted must be your own {\em independently} written solution. List the computing ids of all of your collaborators in the \texttt{collabs} command at the top of the tex file. Do not share written notes, documents (including Google docs, Overleaf docs, discussion notes, PDFs), or code. Do not seek published or online solutions for any assignments. If you use any published or online resources (which may not include solutions) when completing this assignment, be sure to cite by naming the book etc.\ or listing a website's URL. Do not submit a solution that you are unable to explain orally to a member of the course staff. Any solutions that share similar text/code will be considered in breach of this policy. Please refer to the syllabus for a complete description of the collaboration policy.
\vspace*{1mm}
\hrule
\vspace*{2mm}
\noindent
\textbf{Collaborators}: \collabs\\
\textbf{Sources}: \sources}
\vspace*{2mm}
\hrule
\vskip 2em
}
\newcommand{\solution}[1]{\color{blue}\hfill\break\noindent\textbf{Solution:} #1\color{black}}
%\newcommand{\altsolution}[1]{\color{blue}\hfill\break\noindent\textbf{Solution (Alternative):} #1\color{black}}
%\newcommand{\solution}[1]{}
\newcommand{\altsolution}[1]{}
\newcommand{\bit}[1]{\{0,1\}^{ #1 }}
%\dontprintsemicolon
%\linesnumbered
\newtheorem{problem}{\sc\color{cit}problem}
\newtheorem{practice}{\sc\color{cit}practice}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newcommand{\Z}{\mathbb{Z}} % This might be useful for Integers!
\begin{document}
\thispagestyle{empty}
\handout
%----Begin your modifications here
\begin{problem}Bazinga!\end{problem}
Theoretical Physicist Sheldon Cooper has decided to give up on String Theory in favor of researching Dark Matter. Unfortunately, his grant-funded position at Caltech is dependent on his continued work in String Theory, so he must search elsewhere. He applies and receives offers from MIT and Harvard. While money is no object to Sheldon, he wants to ensure he's paid fairly and that his offers are at least the median salary among the two schools' Physics departments. Therefore, he hires you to find the median salary across the two departments. Each school mantains a database of all of the salaries for that particular school, but there is no central database.
Each school has given you the ability to access their particular data by executing \emph{queries}. For each query, you provide a particular database with a value $k$ such that $1 \leq k \leq n$, and the database returns to you the $k^{th}$ smallest salary in that school's Physics department.
You may assume that: each school has exactly $n$ physicists (i.e. $2n$ total physicists across both schools), every salary is unique (i.e. no two physicists, regardless of school, have the same salary), and we define the \emph{median} as the $n^{th}$ highest salary across both schools.
\begin{enumerate}
\item Design an algorithm that finds the median salary across both schools in $\Theta(log(n))$ total queries.
\item State the complete recurrence for your algorithm. You may put your $f(n)$ in big-theta notation. Show that the solution for your recurrence is $\Theta(log(n))$.
\item Prove that your algorithm above finds the correct answer. \emph{Hint: Do induction on the size of the input.}
\end{enumerate}
\begin{problem}Castle Hunter\end{problem}
We are currently developing a new board game called \textit{Castle Hunter}. This game works similarly to \textit{Battleship}, except instead of trying to find your opponent's ships on a two dimensional board, you're trying to find and destroy a castle in your opponent's one dimensional board. Each player will decide the layout of their terrain, with castles placed on each hill. Specifically, each castle is placed such that they are higher than the surrounding area, i.e. they are on a local maximum, because hill tops are easier to defend. Each player's board will be a list of $n$ floating point values. To guarantee that a local maximum exists somewhere in each player's list, we will force the first two elements in the list to be (in order) $0$ and $1$, and the last two elements to be (in order) $1$ and $0$.
To make progress, you name an index of your opponent's list, and she/he must respond with the value stored at that index (i.e., the altitude of the terrain). To win you must correctly identify that a particular index is a local maximum (the ends don't count), i.e., find one castle. An example board is shown in Figure~\ref{fig:board}. [We will require that all values in the list, excepting the first and last pairs, be unique.]
\begin{figure}[h]
\centering
\begin{tabularx}{0.7\textwidth}{ | *{10}{Y|} }
\hline
& & & & & & & & & \\
0 & 1 & 4 & 23 & 18 & 14 & 15 & 13 & 1 & 0\\
& & & & & & & & & \\
\hline
\end{tabularx}
{\small\begin{tabularx}{0.7\textwidth}{ *{10}{Y} }
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9
\end{tabularx}}
\caption{An example board of size $n=10$. You win if you can identify any one local maximum (a castle); in this case both index $3$ and index $6$ are local maxima.}
\label{fig:board}
\end{figure}
\begin{enumerate}
\item Devise a strategy which will guarantee that you can find a local maximum in your opponent's board using no more than $O(\log n)$ queries, prove your run time and correctness.
\item Now show that $\Omega(\log n)$ queries are required by \emph{any} algorithm (in the worst case). To do this, show that there is a way that your opponent could dynamically select values for each query as you ask them, rather than in advance (i.e. cheat, that scoundrel!) in such a way that $\Omega(\log n)$ queries are required by \emph{any} guessing strategy you might use.
\end{enumerate}
\begin{problem} Goldilocks and the $n$ Bears \end{problem}
\noindent BookWorld needs your help! Literary Detective Thursday Next is investigating the case of the mixed up porridge bowls. Mama and Papa Bear have called her to help ``sort out'' the mix-up caused by Goldilocks, who mixed up their $n$ bear cubs' bowls of porridge (there are $n$ bear cubs total and $n$ bowls of porridge total). Each bear cub likes his/her porridge at a specific temperature, and thermometers haven't been invented in BookWorld at the time of this case. Since temperature is subjective (without thermometers), we can't ask the bears to compare themselves to one another directly. Similarly, since porridge can't talk, we can't ask the porridge to compare themselves to one another. Therefore, to match up each bear cub with their preferred bowl, Thursday Next must ask the cubs to check a specific bowl of porridge. After tasting a bowl of porridge, the cub will say one of ``this porridge is too hot,'' ``this porridge is too cold,'' or ``this porridge is just right.''
\begin{enumerate}
\item Give a {\em brute force} algorithm for matching up bears with their preferred bowls of porridge which performs $O(n^2)$ total ``tastes.'' Prove that your algorithm is correct and that its running time is $O(n^2)$.
\item Give an {\em randomized} algorithm which matches bears with their preferred bowls of porridge and performs expected $O(n \log n)$ total ``tastes.'' Prove that your algorithm is correct. Then, intuitively, but precisely, describe why the expected running time of your algorithm is $O(n \log n)$. {\em Hint: while this is not a sorting problem, your understanding of the sorts we've discussed in class may help when tackling this problem.}
\end{enumerate}
\end{document}