PROBLEM 3 (20 pts.):

The function below distributes jelly beans to n children. Analyze the code and answer the question to the right.

Analyze the function and a tight worst-case runtime bound for it (you are looking for a big- bound).

Apply the same guidelines as in the previous problems.

void jelly(int a[], int n) {

int i, j;

int beans=10*n;

// all children start with

// zero beans.

for(i=0; i<>

a[i]=0;

// hand out beans one by one

// to a random child

while(beans > 0){

i = rand() % n;

a[i]++;

beans--;

}

// print one line of beans

// for each child

for(i=0; i<>

cout

for(j=0; j

cout

cout

}

}

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.

PROBLEM 6: algorithm design (40 points):

You are given two arrays each containing n floating point numbers with the following properties:

f[]: values are in non-decreasing order (smallest to largest)

g[]: values are non-increasing order (largest to smallest).

We want to find an index i such that MAX(f[i], g[i]) is minimized (over all indices i).

In other words, we have the following objective (sometimes called a "minimax" objective):

i: 0i<>

(A): Warmup - Given an example instance of this problem with n=10.

1. Specify the contents of both arrays f[] and g[].

2. Make things "non-trivial" -- e.g., although two arrays populated with identical values is a valid input, it is not very interesting.

3. For each index show the maximum of the two corresponding array entries.

4. Identify an index which yields the minimum value from (3). (In general, there may be more than one such index).

(template given below...)

f[]

g[]

max

(B): Now the fun part: devise an O(n) time algorithm for this problem. Give a full implementation and explain the key concepts in your approach.

// returns index i minimizing max(f[i], g[i]) [assume n>0]

int minimax(double f[], double g[], int n) {

}

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