In this project students will implement a binary search tree and its underlying algorithms (insert, find, etc) using Live USGS Earthquake data. The BRIDGES API (links below) will be used as part of this project to:
- Retrieve a user specified number of Earthquake Tweets through the Bridges API and will be stored a list of objects (Java or C++).
- The binary search tree and its underlying algorithms (insert, find, etc) will be implemented using the BSTElement type provided by BRIDGES.
- The elements in the binary search tree support visual attributes (highlight specific quake events by location, month, etc can become tasks as part of the project.
- Bridges API will be used to visualize the binary search tree.
Through the BRIDGES project, we have set up an asynchronous process to collect and parse the USGS earthquake tweets; the data gets stored in a MongoDB and is transparent to the user. Thus, each time a driver is run to extract the quake data, by default, the latest set of quakes (a user specified number through the BRIDGES API) is extracted, enabling a user to see the most recent quakes!
In addition to the attached earthquake project description, the following links will be helpful in students to get started with:
- http://bridgesuncc.github.io/bridges_setup.html [Getting started with Bridges - installation, IDE instructions]
- http://bridgesuncc.github.io/Hello_World_Tutorials/BST.html [Shows a simple example to retrieve earthquake data and build/visualize a binary search tree using the BRIDGES API]
- It is recommended that the project be divided up into 3 parts, (1) implement a binary search tree and required algorithms without the use of BRIDGES (most textbooks provide implementations), (2) modify the implementation to use the relevant BRIDGES elements, and (3) bring in the earthquake data and add visual attributes to each specified task and visualize the resulting tree (grading/assessment involves checking the visualizations).
This project is meaningful and relevant as students analyze real time earthquake data (each execution of the project will retrieve the latest set of quakes) from the US Geological Survey. Possible tasks student can be assigned with this project include implementing algorithms to:
- Algorithms to find the strongest set of quakes (specified within a range of magnitudes).
- Retrieve a large set of quakes from the data source, perform some filtering by magnitudes, date/time, or location and look at the quakes by highlighting subgroups within the visualized binary search tree (note that each node in the binary search tree supports a labe, that can describe details of each quake).
- Use the AVLTreeElement (derived from the BSTElement) and build balanced binary search trees (must implement rotations to maintain balance), when needing to explore very large trees and ensuring good search performance.
Overall, the learning goal is reinforce binary search algorithms and its structure (balancing and implications on search complexity), while interacting with a dataset from another relevant and topical discipline (we hear of earthquakes regularly). The use of BRIDGES visualizations also helps engage the students to see their own output in more compelling ways and share them via web links.