Setup/Notation

We now setup notation that is needed to state the algorithm (and also point out what parts need to change to handle non-distinct $x$ and $y$ values.

• Let $P_x$ be the list of points sorted by lexicographic order (i.e. sort by $x$ co-ordinate first and for points with the same $x$ co-ordinate sort them by their $y$ co-ordinate), and let $P_y$ be the list of points sorted by $y$ coordinate.

  Note

  Note that the definition of $P_x$ is not the same as we did in class (where we just sorted by $x$ co-ordinate). Note that under the assumption that the $x$ co-ordinates are distinct, the order above matches the one we did in class.

• Let $(x^*,y^*)$ be the the middle element of $P_x$.
• We will divide the plane into two halves based on $(x^*,y^*)$. The points $(x,y)$ lexicographically smaller than $(x^*,y^*)$ goes into the left half (called $Q$ from here on) and the rest of the points go into the right half (called $R$ from here on).

  Note

  Note that the definition of $Q$ is not the same as we did in class (where we just made the decision based on the $x$ co-ordinate). Note that under the assumption that the $x$ co-ordinates are distinct, the order above matches the one we did in class.

• Under the more general definition of $Q$ and $R$ above, the following claim, which we say in class for the case of distinct $x$ values still holds and is left as an exercise. (The generalization is the obvious one.)

  Exercise (for students)

  Given $P_x$ and $P_y$ as above, compute $Q_x,Q_y,R_x$ and $R_y$ in $O(n)$ time.

Fibonacci Sequence

This is the sequence $0,1,1,2,3,5,8,13,\dots$.

More formally, the sequence is defined as for any $n\ge 2$: \[\text{fib}[n] = \text{fib}[n-1] + \text{fib}[n-2],\] with the base case \[\text{fib}[0] = 0 \text{ and } \text{fib}[1] = 1.\]

Chapter 6, Ex 2

The input are pairs $(\ell_i,h_i)$ for $i\in [n]$. For each week $i$, your algorithm has to decide if to pick a low-stress job (in which case you will get $\ell_i$ dollars) or pick a high stress job (in which case you will get $h_i$ dollars but you should not have chosen any job) or not pick any job (in preparation for a high stress job in week $i+1$). The goal of the algorithm is to maximize the total dollars it can collect.

The problem

Consider the following natural algorithm (where we define $h_i=\ell_i=0$ for any $i> n$):

                            i=1

                            while i <= n
                                if hi+1 > li+li+1
                                    Choose no job for week i
                                    Choose high stress job for week i+1
                                    i += 2
                                else
                                    Choose low stress job for week i
                                    i += 1

                        

As the name of the algorithm above suggests, it is not a correct algorithm. Present an example input, where the algorithm above does not produce a plan that generates the most amount of dollars. You should state what the algorithm above outputs as well as state what the maximum value a plan can generate from your example input.

The Problem

We come back to the issue of many USA regions not having high speed internet. In this question, you will consider an algorithmic problem that you would need to solve to help out a (fictional) place SomePlaceInUSA get high speed Internet. Fortunately, the town has secured a small grant to install a high speed Internet connection to one computer in the town's library. In this problem you will explore how effectively the town can share the resource of this one computer among the needy citizens of SomePlaceInUSA in order to maximize the social good that this computer with high speed Internet connection can provide to the town as a whole.

Residents of SomePlaceInUSA have applied to use the library's high speed Internet computer. Each of the $n$ citizens provide the following information. The $i$'th citizen submits a tuple $(s_i,f_i,w_i)$, where $s_i$ and the $f_i>s_i$ are the start and finish times of when the applicant plans to use the computer every weekday; $w_i$ is their estimation of the worth of getting to use the terminal from $s_i$ to $f_i$. (Note: the larger the value of $w_i$ the better for citizen $i$ and you can assume that $w_i\ge 0$ are integers.)

Your initial goal is to determine the maximum worth among all valid subset of citizens $S\subseteq [n]$. A subset $S$ is valid if the start and finish times of any citizen $i\neq j\in S$ do not conflict (i.e. either $s_i> f_j$ or $s_j> f_i$). Further, the worth of a subset is \[w(S)=\sum_{i\in S} w_i.\]

The Problem

Citizens of SomePlaceInUSA realize that the current problem as stated above could be monopolized by a citizen who (perhaps legitimately) can get a huge worth by using the computer terminal for the entire day. They come to you to help them solve the following updated version of the problem:

• The input to your algorithm is now the set of triples $\{(s_i,f_i,w_i)|i\in [n]\}$ along with an integer threshold $\tau\ge 0$. Your algorithm should output the maximum worth among all valid subset $S\subseteq [n]$ with $|S|\ge \tau$. and output one with the maximum worth among all such valid subsets (of size at least $\tau$). Note that the optimal worth can be $0$ (if there is no valid subset of size at least $\tau$).

Sample Input/Output

Here is a sample input/output pair (the input is stated as $\tau;[(s_1,f_1,w_1),\dots,(s_n,f_n,w_n)]$):

1. Input: $2;[(1,4,10),(5,10,20),(1,10,100)]$.
   Output: $30$ (for valid subset $\{1,2\}$).
2. Input: $3;[(1,4,10),(5,10,20),(1,10,100)]$.
   Output: $0$ (since there is no valid subset of size $3$).

The Problem

Citizens of SomePlaceInUSA realize that the current problem as stated above might not be representative of their town. In particular, they would like the valid subset to be representative of the economic diversity of their town. In particular, now they want your solution to meet some more requirements:

• The input to your algorithm is now the set of $4$-tuples $\{(s_i,f_i,w_i,e_i)|i\in [n]\}$ (where $s_i,f_i,w_i$ are as before and $e_i\in \{1,2,3\}$ being an identifier for the range of their household income) along with there real numbers $0\le \rho_1,\rho_2,\rho_3\le 1$ such that $\rho_1+\rho_2+\rho_3\le 1$. Your algorithm should output the maximum worth among all valid subset $S\subseteq [n]$ with the following minimum requirement of the economic diversity-- for every $j\in [3]$, we must have \[\left|\{i\in S|e_i=j\}\right|\ge \rho_j\cdot |S|.\] Note that the optimal worth can be $0$ (if there is no valid subset that can meet the economic diversity constraint).

Sample Input/Output

Here is a sample input/output pair (the input is stated as $(\rho_1,\rho_2,\rho_3);[(s_1,f_1,w_1,e_1),\dots,(s_n,f_n,w_n,e_n)]$):

1. Input: $\left(\frac 13, \frac 12, 0\right);[(1,4,10,1),(5,10,20,2),(1,10,100,3)]$.
   Output: $30$ (for the valid subset $\{1,2\}$).
2. Input: $\left(\frac 13, \frac 13, \frac13\right);[(1,4,10,1),(5,10,20,2),(1,10,100,3)]$.
   Output: $0$ ($\emptyset$ is the only valid subset that satisfies the economic diversity constraint).

The Problem

There are $n$ sites for a billboard, each at a location $x_i$ and each site generates $r_i$ revenue. (You can assume that $x_1\le x_2\le \cdots \le x_n$.)

The goal is to pick a subset of sites that maximizes the total revenue with the constraint that if sites $x_i$ and $x_j$ (for any $i\neq j$) are chosen, then: $|x_i - x_j| > 5$.