A visualization of elevation data scaled to 0-255 grayscale values
Read a set of topographic (land elevation) data into a 2D array, write some methods for computing "best" paths through the mountains, and visualize them with simple graphics.
This is a 2D array assignment in which the basic task is pretty easy to understand (cool, even?) and motivate. The low bar is to use basic 2D array processing techniques as building blocks toward a fairly nifty result - visualizing an aerial view of a mountainous region of the U.S. Students also implement a relatively straightforward greedy algorithm to find a west-to-east path through the mountains.
The high bar is fairly high, in that students seeking a challenge can implement more sophisticated path-finding algorithms, or even invent their own to fit the context.
| Summary | Find paths through the mountains using various algorithms and very simple USGS elevation data. |
| Topics |
** The graphics package I use leverages the fabulously useful DrawingPanel class from Building Java Programs by Reges and Stepp. |
| Audience |
Appropriate for CS1 or a later
course. |
| Difficulty |
This is an intermediate to
advanced assignment, taking 1 or 2 weeks for a high school students in an AP course. It's "hard" because it takes some time and, because the results are slightly different every time, you can't resist experimenting with it with once you get it working. |
| Strengths |
A non-trivial but accessible 2D array assignment! Hallelujah. A strength is that it can be used as an extended example of 2D arrays to cover all the topics listed, but it can also be easily modified by the instructor to focus on one or only a few topics. As an instructor (of high school students) I also like it because both the problem and the solution is so unequivocally computational while at the same time revealing the number of human choices and imperfections that go into finding algorithms to solve problems. The fact that the naive, brute force solution to this problem is effectively not computable, giving way to the idea of "greedy" algorithm is pretty engaging for students, and (I think) revelatory at an early stage in their programming careers. |
| Weaknesses |
|
| Dependencies |
I think this is appropriate to use as an assignment in CS1 right after you introduce 2D arrays. Here's my recommended list of prerequisites for doing this assignment:
I would recommend that students have constructed and processed a trivial 2D array just to get their feet wet before diving into this application. They should know how to instantiate a 2D array, know row-major v. column-major ordering, and be able to construct a canonical nested loop for processing all the elements. |
| Variants |
Many variants are possible because even though this is a 2D array assignment it clearly represents a map, so many advanced students take it in a graph theory direction for doing path finding, shortest path, all pairs shortest path, etc. You can also make it just an interesting file I/O, or graphics assignment |
There are many contexts in which you want to know the most efficient way to travel over land. When traveling through mountains (let's say you're walking) you might want to take the route that requires the least total change in elevation with each step you take - call it the path of least resistance. Given some topographic data it should be possible to calculate a "greedy lowest-elevation-change walk" from one side of a map to the other.
A "greedy" algorithm is one in which, in the face of too many possible choices, you make a choice that seems best at that moment. For even the relatively small maps we are dealing with there are roughly 7.24x10405 possible paths you could take starting from western side of the map and taking one step forward until you reach the eastern side.
Since our map is in a 2D grid, we can envision a "walk" as starting in some in some cell at the left-most edge of the map (column 0) and proceeding forward by taking a "step" into one of the 3 adjacent cells in the next column over. Our "greedy walk" will assume that in your walk you will choose the cell whose elevation is closest to the elevation of the cell you're standing in. (NOTE: this might mean walking uphill or downhill).
The diagrams below show a few scenarios for choosing where to take the next step. Assume that in the case of a tie, you would always perfer to just go straight forward. In the case of a tie between the two non-forward locations, you should flip a coin to choose where to go.
|
|||
|
Case 1: smallest change is 5. Go Down. |
Case 2: smallest change is 3. Go forward. |
Case 3: Tie. Smallest change is 3. Forward is possible so go forward. |
Case 4: Tie. Smallest change is 5. Flip a coin to go up or down. |
There are other ways to choose a path through the mountains that can be explored in the "above and beyond" section of this assignment.
|