\documentclass[12pt]{article}
\usepackage[margin=1in]{geometry} 
\usepackage{amsmath,amsthm,amssymb,amsfonts}
\usepackage{graphicx,epstopdf,fancyhdr,xspace,algorithm,algorithmic}
\usepackage[space]{grffile}
\pagestyle{fancy}
\usepackage{epsfig}
\usepackage[space]{grffile}
\usepackage{titlesec}
\usepackage[table]{xcolor}
\usepackage[hyphens]{url}
\usepackage{enumitem} % package used to generate bulleted lists 
\usepackage{tikz}
\usetikzlibrary{arrows,automata}
\theoremstyle{definition}
\renewcommand{\epsilon}{\varepsilon}
\newtheorem{problem}{Problem} %
\cfoot{\thepage}
\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\headwidth}{\textwidth}
\renewcommand{\footrulewidth}{0.4pt}

\newtheorem{claim}{Claim}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{observation}{Observation}
\newtheorem{question}{Problem}
\titleformat*{\section}{\large\bfseries}
\newenvironment{solution}{\bigskip\noindent{\em Solution.}  \ignorespaces}{}
\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,      
    urlcolor=cyan,
}
 
\urlstyle{same}
\PassOptionsToPackage{hyphens}{url}
\newcommand{\homework}[6]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf CS358: Applied Algorithms\hfill} }
       \vspace{6mm}
       \hbox to 6.28in { {\Large \hfill #1 \normalsize{(#2)}  \hfill} }
       \vspace{6mm}
     \hbox to 6.28in { {\it Instructor: #3 \hfill } }
       %\hbox to 6.28in { {\it TA: #4  \hfill #6}}
   %   \vspace{2mm}
   }
   }
   \end{center}
   \markboth{#1}{#1}
   \vspace*{4mm}
}
\definecolor{grayX}{gray}{0.95}





\newcommand{\N}{\mathbb N} %you can define shorthands this way, here we are defined \N as a shorthand for math bold N for natural numbers



\begin{document}
\homework{Assignment 1: Two Towers Revisited}{due 9/22/21 }{Sam McCauley}{}{}{}

\section*{Instructions}

All submissions are to be done through github.  This process is detailed in the handout ``Handing In Assignments'' on the course website.  Answers to the questions below should be submitted by editing this document.  All places where you are expected to fill in solution are marked in comments with ``FILL IN.''

Please contact me at \url{srm2@williams.edu} if you have any questions or find any problems with the assignment materials.


\section*{Problem Description}

\textsc{Input:} The input to the problem will be an array of at most 64 signed 64-bit integers (this array will be given as a pointer of type \texttt{int64\_t*}), along with an integer representing how many elements there are in the array.

\bigskip

\noindent
\textsc{Output:}  The output is a single signed 64-bit integer whose bits represent a subset of the blocks in the array.  For example, the subset consisting of only the first element in the array would be represented by the integer $1$; the subset consisting of the first, third, and fourth elements of the array would be represented by $13$.

\bigskip

\noindent
\textsc{Goal:}  The input represents a set of blocks; the $i$th integer in the input represents the ``area'' of the $i$th block.  The height of a block is the square root of its area.

The goal is to partition the blocks into two sets (which we call towers), such that the height of the towers is as close as possible. The value returned should be the blocks that make up the smaller of these two towers.

\section*{Testing Parameters}

The \texttt{main()} method of the testing program (in \texttt{test.c}) takes two arguments, each of which is a file containing instances of the two towers problem.  An instance of the problem is represented by a sequence of integers (separated by spaces) on one line, and the intended solution (represented as a decimal number) on the second line.  You can test your program by first running \texttt{make}, and then running \texttt{./test.out testData.txt timeData.txt}.

\begin{itemize}
\item For all instances, the best solution is guaranteed to be at least .0001 larger  than the second-best solution (i.e. the smaller tower in the optimal solution is .0001 larger than any other tower smaller than half the height).  This guarantee is to help rule out issues with floating point errors.  This also means that the smaller tower is strictly smaller than the larger tower---you do not need to worry about tiebreaking.
\item These instances were tested using $64$-bit \texttt{double}s.  Higher-precision numbers such as \texttt{long double}s are acceptable (and are available on the lab computers), but are not necessary to obtain a correct solution.  $32$-bit \texttt{float}s may not be sufficient.
\item All input block areas will be between $1$ and $9223372036854775807$ (this is the largest number that fits in a signed 64 bit integer).  For the timed testing case, these inputs were (essentially) randomly generated.  This means that you can assume that the inputs are approximately randomly distributed.  However, your algorithm should work for any input.
\item Two solutions with running times within $.1$ seconds of each other will be considered tied for the purposes of this assignment. 
\end{itemize}  

\section*{Questions}

\textbf{Code}~(50 points).  Implement the meet in the middle algorithm for the two towers algorithm.  Please give a very brief (2-3 sentence) description of your approach below.

\begin{solution}
%FILL IN YOUR ANSWER HERE
\end{solution}

\bigskip
\bigskip

\begin{question}[15 points]
	What proportion of your algorithm's running time is spent on sorting?\footnote{It's OK if the version of your implementation that you use for this experiment does not exactly match the version you hand in.  If your implementation does not use sorting at all, design and perform an experiment to estimate the time a sort would take compared to your implementation's total running time.}

	Describe specifically how you performed your experiment.  How did you measure the time it took?  What input did you use?  Did the experiment entail any changes to the running of your implementation that might change its performance?
\end{question}

\begin{solution}
%FILL IN YOUR ANSWER HERE
\end{solution}

\begin{question}[10 points]
	Can meet in the middle be modified to efficiently return the $k$ best solutions, rather than just the best?   Describe how this modification could be made and analyze its running time  (the running time should be in terms of $n$, the number of blocks, and $k$, the desired number of solutions---you should not assume that $k$ is a constant).  Make sure your methodology is correct and is clearly described.
\end{question}

\begin{solution}
%FILL IN YOUR ANSWER HERE
\end{solution}

\begin{question}[25 points]
	Consider a similar problem: again we are given a list of $n$ blocks (let's call it $S$), but now we want to partition them into \textit{three} towers such that the heights are as close as possible.  In particular, the goal is to minimize 
	\[
		\text{the height of the tallest tower} - \text{the height of the smallest tower}.
	\]
	In this problem you will design a meet in the middle approach to solve this problem.  I have broken the question into several parts below to help you find a solution.

	\bigskip
	\bigskip

	\textbf{(a)}~First, give a simple algorithm to solve this problem in $O(n3^n)$ time.  How much space does it require?

	\bigskip
	\begin{solution}
	%FILL IN YOUR ANSWER HERE
	\end{solution}
	\bigskip

	\textbf{(b)}~Now, let us consider two sets $S_1$ and $S_2$ that partition $S$ (i.e.\ they satisfy $S_1\cap S_2 = \emptyset$ and $S_1\cup S_2 = S$).  Consider an assignment of each element of $S_1$ to the small, medium, and large tower; let's call this assignment $A_1$.  Given assignment $A_1$, what constraints are there on an assignment $A_2$ that assigns each element of $S_2$ to the small, medium, and large tower?\footnote{In particular, given $A_1$, we'd better ensure that any assignment $A_2$ of elements of $S_2$ results in the ``small tower'' having the smallest total height, and the ``large tower'' having the largest total height.  This is similar to how we, in the original two towers problem, assigned elements to the smaller of the two towers and capped its height at half the sum of all elements in $S$.}  Of assignments that meet this constraint, which gives us the best overall solution?

	In particular, let's say $s_1$, $m_1$, and $\ell_1$ are the total heights of blocks that $A_1$ assigns to the small, medium, and large tower respectively; similarly, let's say $s_2$, $m_2$, and $\ell_2$ are the assignments to the small, medium, and large tower for $A_2$.  This question is asking for constraints on $s_2$, $m_2$, and $\ell_2$ in terms of $s_1$, $m_1$, and $\ell_1$---they'll help us in part (c).

	\bigskip
	\begin{solution}
	%FILL IN YOUR ANSWER HERE
	\end{solution}
	\bigskip

	\textbf{(c)}~Using your ideas from part (b), give an $O(n3^{n/2})$ space, $O(n2^{n/2})$ time method that can, for any assignment of elements of $S_1$ to the three towers, find an optimal assignment of elements from $S_2$ to the three towers.

	\textit{Hint: Let's say a set of elements $S'\subseteq S_2$ is assigned to the smallest tower.  How quickly can you find the best way to assign the remainder of $S_2$ to the middle and tallest tower? This is where you should be precomputing a lookup table.}

	\bigskip
	\begin{solution}
	%FILL IN YOUR ANSWER HERE
	\end{solution}
	\bigskip

	\textbf{(d)}~Using part (c), give an $O(3^{n/2}\cdot n2^{n/2})$-time,\footnote{This is approximately $O(n3^{.82n})$, quite a bit faster than $O(n3^n)$.} $O(n3^{n/2})$-space algorithm to find the optimal solution to a three towers instance.


	\bigskip
	\begin{solution}
	%FILL IN YOUR ANSWER HERE
	\end{solution}
	\bigskip

	\textbf{(e)}~\textbf{Extra credit} (5 points): Improve upon your result from part (d)---give an asymptotically faster algorithm.  (The improvement needs to be exponential; improving by a $O(n)$ factor is not enough.)

	\bigskip
	\begin{solution}
	%FILL IN YOUR ANSWER HERE
	\end{solution}
	\bigskip
\end{question}


\section*{Tips and tricks}
\begin{itemize}
\item Remember to create a correct program before worrying about creating a fast one!
\item You need to iterate through all possible subsets.  One way to do this is to store each subset as an integer, and increment it to obtain a new subset.  If you are unfamiliar with this technique, it may be useful to read the version of this lab given in CSCI 136, which can be found here for example: \url{https://williams-cs.github.io/cs136-s21-www/labs/two-towers.html} (there's also now a video for that lab here: \url{https://www.youtube.com/watch?v=MFU0hGOWvuk}).
\item Since the problem asks for the items that make up the solution, your meet in the middle approach will need to keep track of both the cost of a subset, and the items in the subset.  There are many ways to do this.  One easy way may be to keep track of a subset using a 64-bit integer, and to keep track of a partial solution using a struct containing both the cost of the subset and the integer representing its items.  Other solutions are also possible, such as storing two arrays (one for costs and one for subsets), or storing a hash table keeping track of which solution corresponds to which cost.
\end{itemize} 
\end{document}
