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) {

}

Appendix: what makes a good "Algorithm Description"??

First, an algorithm description is not the same as a program. What makes a good/correct algorithm description? Like a lot of things, we know it when we see it, but a formal set of rules is not always so easy. Nevertheless, Ill try below:

1. It should be translatable to an actual implementation by any competent computer scientist. After you have a draft, re-read your description as if you are seeing it for the first time. Does it pass this test? Are there ambiguities that you should resolve?

2. Just the right amount of detail. It does not get bogged down with language specific issues and implementation details. For example, for Problem-2, we would probably represent an interval as a structure in C; including the code for an INTERVAL typedef would not be expected or desired! The person described in (1) knows how to do this already!

3. Step-by-step presentation. It avoids a narrative (paragraph form) presentation in favor of a step-by-step description. Maybe expressed as bullet points.

4. You do not need to re-invent known algorithms. If, for example, you want to perform a sort of some kind, you dont have to re-invent merge-sort. You can just say use merge-sort to. The ... part is probably important though! What exactly are you sorting and the sorting criteria are important in an algorithm description.

5. Drawings! A diagram or two is often useful. Pay careful attention to how you label your diagrams.

6. The Big Picture. Often a birds-eye view description of the key concepts in the algorithm before a more detailed description can make a huge difference!

A good algorithm description also usually needs two things along with it:

1. Correctness. Some kind of argument of correctness -- why it works. It is up to you to show us that it works; it is not our job to determine if/why it does/does not work. This may be folded into the algorithm description in some cases, but it must be in there somehow.

2. Runtime analysis. Sometimes this will be trivial, but it must still be in there.