Lab 6

Overview

Hill Finding Implement an efficient hill-finding algorithm for general 2D input arrays of h x w numbers. A hill is strictly a location that is at a higher or equal elevation than the adjacent locations in the grid. In this lab, a hill is defined as a location the one with higher than or equal elevation than its neighbors.

Your algorithm should work on all inputs, in particular, for grids where h >= 1 and w >= 1 (If the grid has size 1×1, then the single elevation at (0,0) is trivially a hill.)

Input:

• A grid or a 2D matrix of values of type Double. The input is of type ElevationGrid.

Output:

• A location on the grid. The output is of type Location.

A location $(r,c)$ in the grid is a hill if all of the following conditions are true:

E(r,c) >= E(r-1,c), if r > 0.

E(r,c) >= E(r+1,c), if r < h-1.

E(r,c) >= E(r,c-1), if r > 0.

E(r,c) >= E(r,c+1), if r < w-1.

The if clauses capture boundary conditions. For example, if r=0, then the location (r,c) is in the first (top) row of the grid, and so it has no adjacent neighbor above it. In short, a location has to be higher than or equal to any adjacent locations that exist in the grid. Diagonals are not adjacent locations, for the purpose of this definition.

Step 1: A Hill on a 1D Array

In this step, the grid is a 1D array (h=1, and w is arbitrarily wide).

1. For an input size of n=10, and given the above definition of a hill, assign numbers to locations such that there is/are:

   a) Only one hill (if possible).

   b) Several hills (if possible).

   c) Exactly 10 hills (if possible).

   d) No hills (if possible).

Check Answer with TA

1. Describe and analyze an efficient algorithm that takes as input a one-dimensional array of n elevations and outputs a hill location (any one). The output is essentially a column number of the hill (i.e., an index of the array). Hint. Think about devising a sub-linear solution for this case. It helps to draw the question on the board.

Step 2: A Hill on a 2D Array

In this step, think about how to find any hill on a 2D array (see image below) that is more efficient than merely checking for every location, i.e., more efficient than O(h x w).

1. For an input size of h=7 and w=7, and given the above definition of a hill, assign numbers to locations such that there is/are:

   a) Only one hill (if possible).

   b) Several hills (if possible).

   c) No hills in one half of the array (if possible).

   d) No hills (if possible).

Check Answer with TA

1. Describe and analyze an efficient algorithm that takes as input of h x w elevations and outputs a hill location (any one). Some hints are:

   a) Think about a divide-and-conquer strategy to reduce the problem to a smaller version of itself.

   b) Think about the use of the solution of a 1D array in your algorithm.

   c) The different cases of number assignments you did in (1) may be helpful.

   For the time/space complexity analysis, you can assume either h or w are constant. You can alternatively assume h=w=n, whichever is useful for your recurrence relation.

Step 3: Submit the writeup

• Each group member should submit the same markdown file to Moodle. In the submission comment add a link to the hedgedoc file and also indicate who you worked with.

Step 4: Understanding the program requirements

The Moodle page has a link to submit your code. Please submit your Progam7.java file only. You do not have to submit the ElementGrid.java and Location.java files. If you do, they will be overwritten by the original versions when the auto-grader compiles and runs your code.

Starter Files

There are three starter files for this assignment:

• Program7.java contains the entry point for your algorithm, a function called findHill described below.

• ElevationGrid.java is the data structure that provides the input, a 2D array of elevations

• Location.java is a helper class for a (row, column) pair

Your task is to implement the function

public static Location findHill(ElevationGrid grid)

The input to this function is an ElevationGrid object that contains the elevation data. Although this is essentially a 2D array, you cannot access it’s values directly (more on this below).

The output is a Location object corresponding to a (row, column) pair. That location should be a hill in the input, meaning that its elevation is larger than all its existing adjacent neighbors (above, below, left, and right; existence depends on whether the location is at a boundary of the grid).

You should not modify Location.java or ElevationGrid.java. Your implementation will be compiled against the original versions of these files.

Accessing the elevations

The ElevationGrid object has the following methods:

• int height() and int width() return the number of rows and columns, respectively

• int compare(row1, col1, row2, col2) returns how the elevation at location (row1, col1) compares to the elevation at location (row2, col2). Following Java comparison conventions, it returns an integer that is:

  • $=0$, if the elevations are the same (this should never happen, as it is assumed that all elevations are distinct)

  • $>0$, if the elevation at (row1, col1) is higher than at (row2, col2)

  • $<0$, if the elevation at (row1, col1) is lower than at (row2, col2)

The height and width methods can be used to determine bounds for accessing the grid. And, although you cannot access the values directly, you can compare values at specified locations. This should be enough to implement an algorithm that is searching for a location with an elevation larger than its neighbors—the comparison between elevations is important, but the actual values shouldn’t matter.

The object tracks the number of times that compare is called. The count can be obtained by calling the comparisons() method on the ElevationGrid. You should strive to asymptotically minimize the number of calls to compare.

Returning the output

Once you find a hill at some location $(r,c)$, you simply need to return that pair in a Location object, for example:

return new Location(row, col);

The Location helper class allows your findHill function to return more than one primitive value bundled together, namely, the row index and column index of a hill.

Step 5 (homework): Coding, Testing, Program Submission

The Moodle page has a link to submit your code. Please submit your Program7.java file only.

Scoring

To get scores call “java ComputeScores” after compiling your source code.

Testing

The ElevationGrid class has some other methods that you can use for testing and debugging:

• There are three constructors:

  1. ElevationGrid(double[][] init): this creates an ElevationGrid object based on the provided 2D array init. It makes a copy of the input array, so changes to the array will not affect the grid. Please note that it does not check whether values are distinct.

  2. ElevationGrid(int height, int width): this creates a random 2D array of height rows and width columns

  3. ElevationGrid(int height, int width, long seed): this creates a random 2D array of height rows and width columns, but initializes the random-number generator with the provided seed. If you want a random array, but want to use it multiple times for testing, you should use this version: providing the same seed will result in the same (pseudo-)random grid. The seed can be any integer.

• The object has a toString method that neatly represents the grid, so it is possible to print an ElevationGrid object using the normal Java print functions (e.g., System.out.println(grid);).

Feel free to change the main function in Program7.java to test your code. Right now, there is some code that generates two test cases, convenient for testing; Grid 1, with user-defined elevations, and Grid 2, with randomly generated elevations but at scale.