Finding Nearby Differences
Finding Nearby Differences
Consider a one-based array a of integers of arbitrary size. We will define the distance-weighted difference d(i,j) between a distinct pair of numbers a[i] and a[j] in the array to be the magnitude of the difference between the numbers divided by the distance between their positions:
d(i,j) = |a[i] - a[j]| / |i - j|
In this exercise, you are asked to give an algorithm for finding an i and j that maximize d(i,j) for a given array a.
Write a formal problem description. It should have a name, an instance description, and a solution specification.
Give an algorithm for solving instances of the problem. It need not be efficient.
Give the big-O complexity of your algorithm. Be sure to specify what this complexity is a function of, and what your fundamental operation is.
Give an argument for the correctness of your algorithm. It need not be a full formal proof, but should be sufficient to convince our graders that the algorithm is correct.
You may submit the assignment by typing or pasting it directly in to Moodle, or you may upload a PDF. It is fine to do your homework with paper and pencil and submit a PDF of a scan. You may not submit office file formats or the like: they're too hard for the graders to read.