\documentclass[12pt]{article}

\begin{document}
\begin{center}
	\bf
	Algorithms \\
	Computer Science 140 \& Mathematics 168 \\
	Spring 2009 \\
	\rm
	Homework 3a \\
	Due Thursday, February 5
\end{center}

\begin{enumerate}
\item {\bf [20 Points] Load Balancing on the Snapple Computer!} 
First the utterly gratuitous story:  Snapple Computers is an emerging manufacturer of personal computers using
dual core (two processors) technology.
You've been hired to design algorithms
for the operating system (OS Y) of Snapple's new personal computer, the
Snapple Mango Melon Madness (referred to hereafter as the ``$M^{3}$'').
The $M^3$ has {\bf two} identical UltraSuperMangoPower processors.  

When run in batch mode, the operating system receives an array $S$ of the integer running times of $n$ tasks.
That is $S[1], \dots, S[n]$ are integer running times for $n$ tasks.
The objective of the operating system is to find an optimal {\bf load
balance} for these tasks on the two processors.
That is, we wish to find a partition of the tasks in $S$ into
two sets (such that the tasks in one set will be executed on one of the
processors and the set of tasks in the other set will be executed on
the second processor in parallel) that minimizes the total elapsed
time required to complete all the tasks.

For example, if $S$ contains five tasks with running times 2, 1, 3, 5,
7 then we can assign the tasks with running times 2 and 7 to one
processor and the tasks with running times 1, 3, and 5 to the other,
resulting in an elapsed execution time of 9.  On the other hand,
if the five running times had instead been 2, 1, 3, 5, 8 the best we
could do is have a partition of 2, 3, and 5 on one processor and
1 and 8 on the other, with an elapsed running time of 10.

We will solve this problem in a sequence of steps.  Be patient.
        \begin{enumerate}
                \item 
                Your boss, Dr.~I.~Stee, has proposed a brute-force
                algorithm that involves simply enumerating all
                possible partitions of the task set $S$ and finding
                the best one.  If the $M^{3}$ can evaluate
                one million partitions per second and the set $S$ 
                contains just 50 tasks, how long does it take the
                $M^{3}$ to find the optimal load balance?  Explain
                how you found your answer. 
        
                \item Now consider a variant of this problem called the 
		\emph{Partition Problem}.  In this problem we are given the
		set $S$ of $n$ running times and we are also given a 
		positive integer $C$.  Our objective is to return the boolean
		\textbf{true} if there exists a subset of $S$ which adds up to 
		\emph{exactly} $C$ and otherwise return the boolean \textbf{false}.
		To this end, give informal and clearly written 
		pseudo-code or a clear English description for a recursive function 
		\texttt{partition}($i$, $C$) which returns the boolean
		\textbf{true} if there is a subset of $S[1], \dots, S[i]$ which
		adds up to exactly $C$ and returns \textbf{false} otherwise. 

		\item Give a lower bound argument to explain why 
		\texttt{partition}($n$, $C$) can take exponential time.
					    	
                \item Next, describe a dynamic programming algorithm
                that takes as input the set $S$ and a number $C$ and
                determines if there exists a subset of $S$ that
                adds up to exactly $C$.  Describe your algorithm carefully by
                doing the following:
                	\begin{enumerate}
   		 	\item Describe what the dynamic programming table looks like and its
				dimensions. 

					\item Explain what each cell represents. 

   					\item Describe the order in which the cells in the table are filled
					in and the rule used to fill in each cell.  Be sure to explain how to
					fill in the ``easy'' cells at the beginning as well as the rule for
					filling in the other cells. 		
		\end{enumerate}
	      
                \item What is the asymptotic running time of your algorithm as a function
                of $n$ and $C$?  Explain.
                
                \item Now let's reconsider Snapple's load balancing problem.
	       Show how your dynamic programming algorithm can be used to
                determine an optimal partition of $S$ into two subsets
                such that the total elapsed running time of the
                resulting partition is minimized.  Your algorithm must
                determine the actual partition.  Please describe your approach in clear English
                rather than pseudo-code.
                Explain the running
                time of this algorithm?   (Try to keep it as low as possible!) 
                         
         \end{enumerate}
        
\end{enumerate}

\end{document}