— You will be graded on clarity,  correctness,  and precision.   When asked to present an algorithm, you should give at least 2-3 sentences explaining your approach, then pseudo-code, then a run-time analysis, and a short explana- tion for why the algorithm is correct.  For example, in the case of dynamic programming problems, be sure to define what the variables in your equa- tion represent in words and give an equation explaining the recursive struc- ture of the problem. Do not write contradictory or ambiguous statements in your answers.

— You may consult the lecture slides as posted on my website under 22s-58oo.

No other external resources or aids are allowed.

— This is an individual exam. You must not discuss the exam problems with

anyone else except the course staff.  Do not give or receive any assistance to anyone else in the course.  Prepare and type each answer individually without assistance.

— You must tag the pages of your solution when you submit in Gradescope. pRPBLEM 1 Fewer Routes with 3 hops

Your second homework asked you to construct a o(n log n)-segment North- South route system (i.e., all of the routes in the system are only allowed to move from i to j _ i) that allows any commuter to get from stop i to j using at most 2 segments.

In this problem, we design a new North-South system that allows any com- muter to get from stop i to j _ i in at most 3 “hops", but only requires o(n log log n) segments. Hint: the basic idea is to divide the n stops into groups of size [,n ]. Build a system for these groups recursively so that any travel entirely within these groups can be accomplished in 3 hops.  In addition, each group has designated “hubs" which have both incoming and out-going segments to other stops.  It is then possible to add o(n) segments to and from these hubs so that a person can get from any stop i to any stop j within another group using at most 3 route seg- ments.  Note:  these extra routes cannot start at a node j and go backwards to a node i < j.

(a) Fully describe this scheme in 3-4 sentences. Clearly specify how to add the

o(n) segments to implement the 3-hop property in your route system.       (b) State a recurrence that counts the segments required by your route system.

(c) Prove a tight upper bound on your recurrence using induction.

pRPBLEM 2  Top earnings

You manage a hedge fund. Suppose you are given an array of numbers a1, . . . , an that summarizes a trader’s earnings (or losses) for n days. Your goal is to present a dynamic programming algorithm that computes the most lucrative trading pe- riod for this trader; i.e., your algorithm must find the pair (i, j) where i < j that maximizes the sum s = Ek(j)=iak.  The algorithm should output (i, j, s) and run in o(n) time.

(a) Define a variable BEsrn  in the style of DP solutions that can help solve this

problem. Use sentences to explain what the variable represents.

(b) Provide an equation that defines this variable.

BEsrn  =

(c) Provide pseudo-code for a o(n)-time algorithm. Prove your algorithm cor- rect and analyze its running time.  (Assume additions are O(1)-time oper- ations.)  Your pseudo-code should require < 20 lines in total and should output (i, j, s).

pRPBLEM 3  COVID testing

During this pandemic, epidemiologists have been faced with many challenging problems.  One issue that arose was tracking the dominant variant of the virus that was infecting the population.

Suppose a testing lab is given n viral samples from a population on a given day.   Using specialized test equipment, it is possible to use a pPMpARE test to determine whether two samples are the same or different variants. Although this test is expensive, it is faster and cheaper than running full genetic sequencing on both strands and then comparing the sequences; however, the test only returns whether the two samples are the same or not.

On input the n samples  (s1, . . . , sn),  give the pseudo-code of a divide and conquer algorithm that uses only o(n) calls to pPMpARE (si, sj) to determine if there is one variant that is a majority among the day’s samples. Explain why your algorithm is correct. Analyze the number of tests your algorithms performs using a recurrence.

Hint:  this problem is similar to the counting problem from our first lecture. Be careful to handle all base cases properly. Your pseudo-code should require no more than 15 lines in total.

pRPBLEM 4 Day Trader’s Decisions

A day trader wants to trade n . 100 shares of the stock AAPL in blocks of 1oo. Temporary market rules prevent her from short-selling; in other words, she must own a block of shares before selling them.  To avoid price slippage from large orders, she can only buy or sell 1oo shares, i.e., 1 block, at a time. At the end of the day, she wants to own zero shares of AAPL.

How many ways can she do her trading?   For example, when n  = 2, she can do "BUY, SELL, BUY, SELL" or "BUY, BUY, SELL, SELL" and so there are 2 ways. Present your answer as a recurrence and clearly explain why the recurrence captures this number.

pRPBLEM 5 Faster Price Run

This question develops the challenge problem from Price Run in Homework 3. In the problem you are given a list of closing stock ticker prices p1, p2, . . . , pn and the goal is to find the length of the longest (not necessarily consecutive) streak of prices that increase or stays the same.  For example, given the prices 2, 5, 2, 6, 3, 3, 6, 7, 4, 5, there is the streak 2, 5, 6, 6, 7 of prices that increase or stay the same, but an even longer streak is 2, 2, 3, 3, 4, 5. Thus, the answer is 6.

One solution to this problem is to define a variable LPNci  to be the length of the longest sub-sequence of prices that only increase or stay the same in height among the prices from p1, . . . , pi  that ends with price pi .

First observe that LPNc1  = 1. Next, note that if pi  is larger than pj, then i can be added to the longest subsequence of prices that ended at j to form a longer subsequence. In other words, if pi  2 pj, then one can form a sequence of length 1 + LPNcj by considering ..., pj, pi where the ... represents the prices in the longest sequence that ends at price j. Thus we have

LPNci  = x r L(1)PNcj + 1

if pj  _ pi

if pj  < pi

(1)

Finally, the longest overall sub-sequence is simply max1 {LPNci }. Computing each value LPNci  takes O(n).  There are n such values; thus, the overall running

time is o(n2 ) because the last step of finding the max takes o(n).

PRIpEs(h1, . . . , hn)

1   LPNc1  - 1

2   for i = 2 to n

3     LPNci  = maxj(i)1(1) 

4   Output max{LPNc1, . . . , LPNcn }

In this problem you will improve the solution to an O(n log n) time algorithm. Notice that line 3 uses a linear scan requiring o(i) steps to find the price that is smaller than pi  and currently has the largest length.

We can improve our solution by maintaining a slightly different DP variable that allows us to use binary search instead of linear scan for this step.  The idea is to consider the variable FAsri  which maintains “the index of the smallest price that ends a sequence of length i that increases or stays the same." If no such value exists, we define it to be o.  To compute, it is index k which has the smallest pk among the set of indicies

{k such that k _ FAsri _1 A pk  _ pFAsri _1 }

(a) In a problem of size 1, what is FAsr1 ?

(b) Assuming we have computed FAsri for i = 0, . . . , j, explain in words how to update the values given the next price pj+1 .