Problem : Devise an efficient algorithm that, given an sequence of integers $a_1, a_2, \ldots, a_n$, the length of the sequence ($n$), and an integer $k$, determines if there is a run of at least $k$ consecutive equal values in the sequence. For example, if the sequence is $1, 3, 3, 1, 1, 2, 2, 2, 37$ and $k = 3$ then the result should be true because there are 3 2's in a row, but if $k = 4$ then the result should be false. Use an invariant to prove that your algorithm is correct.

Problem : Mermaid Coffee (MC) has a rewards program. MC frequently runs promotions of the form "make $x$ purchases with your rewards card in $y$ days, and get $z$ bonus points." Some MC customers game the system: when such a promotion is running and they want coffee and a scone, they will place an order for their coffee, then, while waiting for their coffee to brew, get back in line and order their scone, thus getting credit for two purchases instead of the one they would have gotten if they had ordered both items at once (some such customers feel a little scandalized by their own actions and make one of the orders a mobile order so the baristas don't know what they're doing).

MC would like to prevent customers from gaming their promotions. They intend to impose new rules on the promotions so that any purchases in a 1-hour interval count as a single purchase. A given sequence of purchases may be covered by different sets of intervals. For example, if you make purchases at 8:30am, 9:30am, 9:50am, 10am, and 10:45am, then the intervals (8-9am), (9:30am-10:30am), (10:45am-11:45am) cover all the purchases, as do the intervals (8:30-9:30am) and (9:45am-10:45am). MC would like to find, for any given sequence of order times, the minimum number of purchases they can credit the customer for under these new rules, so they would favor the latter set of intervals.

We convert this into a more formal problem: given a sorted list of distinct integer order times $t_1, t_2, \ldots, t_n$ and a positive width for the intervals, $T$, find a set of intervals that covers all of the times in the list using as few intervals as possible (the intervals are closed – they include both endpoints).

• Prove that there is an optimal solution where none of the intervals overlap except possibly at the endpoints.
• Describe an efficient algorithm to solve this problem and prove that your algorithm is correct (for this and other problems where the output must be optimal in some sense, correctness includes optimality of output). (Hint: consider an optimal solution and show that your algorithm builds a solution that is in some sense at least as good at each step).

Problem :

• Consider the following job scheduling problem. We are given all at once $n$ jobs with positive lengths $t_1, t_2, \ldots, t_n$. We can schedule only one job at a time and once we start a job we must run it to completion. A schedule for a set of jobs is then the starting time for each job $s_1, s_2, \ldots, s_n$. Find an efficient algorithm to schedule the jobs to minimize the total wait time, where the wait time for a job is the difference between the time the job arrived and when it finished. Since all jobs arrive at the same time $t=0$, the wait time for job $i$ simplifies to $s_i + t_i$ and so the problem is to schedule the jobs to minimize $\sum_{i=1}^n(s_i + t_i)$. Prove that your algorithm is correct.
• Consider the above problem, but associate with the jobs positive values of importance $w_1, \ldots, w_n$, and minimize $\sum_{i=1}^n w_i(s_i + t_i)$. Find an efficient algorithm to determine an optimal schedule in this case. You need not prove that your algorithm is correct.

---