Keith Schwarz (htiek@cs.stanford.edu)
This CS2 assignment asks students to implement a literal flood fill. Students are given a terrain containing bodies of water, then write a flood fill algorithm to determine what parts of the terrain will be under water as sea levels rise. Our provided starter files include terrains from around the world and allow students to explore how coastal areas will be impacted by differing amounts of sea level rise. The underlying model is very simple - students see the terrain as a 2D array of real numbers representing heights in meters, and water can flow in each of the four cardinal directions. The resulting images give a striking sense of how coastal areas may be impacted by climate change.
| Vélingara, Senegal | South San Francisco Bay Area, United States |
|---|---|
|
|
| Pearl River Delta, China | North Island / Te Ika-a-Māui, New Zealand |
|
|
In the version of the assignment I use, I provide starter code to load and visualize terrains. Students then implement the back end logic: given a 2D array of heights, a location of water source locations, and a water level, return a 2D grid of booleans indicating, for each grid cell, whether it's under water. In Java, for example, the function students code up might have this signature:
public static boolean[][] floodedRegionsIn(double[][] terrain,
GridLocation[] sources,
double height);
However, the assignment could easily be expanded by having students do the appropriate file I/O to load the terrains, write the graphics logic to display the terrains on screen, etc.
This assignment was inspired by Baker Franke's "Mountain Paths" Nifty Assignment from 2016. The data files are taken from a mix of different sources, with credits in the ATTRIBUTION.txt text file bundled with the starter code. Some of the text in the writeup is adapted from a description of breadth-first search written by the fabulous Julie Zelenski.
| Abstract | This CS2 assignment asks students to implement a literal flood fill. Students are given a terrain containing bodies of water, then write a flood fill algorithm to determine what parts of the terrain will be under water as sea levels rise. Our provided starter files include terrains from around the world and allow students to explore how coastal areas will be impacted by differing amounts of sea level rise. The underlying model is very simple - students see the terrain as a 2D array of real numbers representing heights in meters, and water can flow in each of the four cardinal directions. The resulting images give a striking sense of how coastal areas may be impacted by climate change. |
| Topics | Arrays, search algorithms. |
| Audience | CS2 |
| Difficulty | The difficulty of this assignment can be tuned by adjusting how much support is given to students. I use this
assignment early in a CS2 course as a way of learning about breadth-first search and collections classes by providing pseudocode for
BFS and asking students to translate it into code. I also provide code to do the necessarily file I/O and graphics. Students can
usually complete this assignment in around one week. However, the assignment could also be suitable later in a CS2 course by not giving explicit pseudocode and instead asking students to code up breadth-first search from scratch, or by requiring students to do their own visualization of the output, or by requiring students to load the data files for themselves, etc. |
| Strengths | Flood fill algorithms are a common way of showcasing graph algorithms (depth-first search or breadth-first search) or recursion (particularly, a recursive DFS). These algorithms are often presented in the context of graphics programming or image processing. This assignment provides the same algorithmic content, but in a wholly different context that may appeal more broadly to student interests. It also enables students to explore answers to socially-relevant questions (what mitigations are needed for climate change, and how will different areas be impacted?) on their own using their own code. |
| Weaknesses | The "nifty" part of this assignment depends in large part on the data files provided to students, which make the assignment feel more "real." Some of these data files are large. I've hosted the files on my university's web servers and had the starter files download them as needed, but there might be a better solution to the problem. In the same vein, it can take a bit of effort for students to create their own data files, since they need to get a terrain height map and annotate it with the locations of water sources in abstract 2D space. |
| Dependencies | The Java version of this assignment is built purely using the standard Java libraries and has no dependencies. The C++ version of
this assignment uses Qt for graphics and uses a custom set of C++
libraries that we've adopted for our CS2 course. Students need to be familiar with a non-recursive flood-fill algorithm. We use multisource breadth-first search, but this is only one of many options. Recursive solutions will not work here because the terrains are too large for the recursion to fit on the call stack. The version of the assignment I've bundled here doesn't require students to be familiar with graphics code. However, you could easily adopt this assignment to require students to do their own graphics. The terrain files that ship with the starter code contain some that point to resources on my university's web servers. If you want to adopt the assignment, please, as a courtesy, download your own versions of those files once and place them on your own university's web servers. Thank you! :-) |
| Variants | Rather than returning a boolean[][] indicating which grid cells are under water, it would be possible to ask students to instead return a double[][] indicating the minimum water height needed to flood each cell. This then converts the problem to solving the minimum-bottleneck path problem on the grid, which can be done with a simple edit to Dijkstra's shortest paths algorithm. However, I have not yet tried this. |