PROBLEM 4: algorithm design (50 points):

You are given as set of n time intervals {(s1, e1), (s2, e2), ..., (sn, en}). The interval (si, ei) has a start time of si and an ending time of ei.

You can think of each interval indicating that a process is active during that time. You may assume that ei>si. Or you can just think of them as horizontal line segments.

You want to find the maximum overlap among all of the given time intervals. Your algorithm simply determines this maximum value and reports it.

The diagram below illustrates an instance of the problem with 6 time intervals, each represented by horizontal line segments.

For this instance, the algorithm would report 4 as the maximum overlap.

Devise an algorithm solving this problem in O(nn) time.

Discussion/details:

• Time intervals are inclusive of their end points. As a result, if one interval ends at exactly the same time another begins, the two intervals are overlapping.

• The interval start and end times are given as floating point numbers.

• The intervals are given in an arbitrary order

• If your approach includes some kind of sorting operation, you can assume the existence of, for example, MergeSort (and its runtime). Exactly what you choose to sort and how you interpret the results are things you must explain and justify.

PROBLEM 5 (20 points): (estimation of asymptotic runtime from experiments) Log into bert or bertvm. In the directory ~jlillis/CS251-public you will find an executable called mystery (but no source code!). The program takes a single command line argument N ("problem size"). When you run the program it does some mysterious computations and eventually terminates. When it terminates it prints out the (approximate) CPU time taken by the run in seconds. For example if you do this: ~jlillis/CS251-public/mystery 2000 it will run with N=2000 and then report the elapsed CPU time in seconds. Your job: do some experiments by running the mystery program for a range of values of N and try to come up with a conjecture on the asymptotic runtime of the program as a function of N by doing some analysis. Assumption/hint: the actual runtime has the form (Nd) for some d. You are trying to figure out what d is.

SHOW YOUR WORK: describe the experiments you did and how you arrived at your final conclusion.

end start overlap:2 overlap: 1 overlap:4 (max) over lap:3 overlap: o time