Map-based Educational Tools for Algorithm Learning (METAL)

led by Dr. James D. Teresco

Motivation

"An algorithm must be seen to be believed, and the best way to learn what an algorithm is all about is to try it." |

- Donald E. Knuth, *The Art of Computer Programming, Volume 1* (1997), p. 4. |

Nearly any topic in a course working with data will be more
interesting for students if the data has connections to the real world
and if they can visualize the data and results in a meaningful way.
When using graph data, such as in a data structures or algorithms
class, it needs to be small enough to be manageable, but large enough
to be interesting. This might consist of a small road system, airline
flight schedules, or even the layout of a campus or building.
The

*Map-based Educational Tools for Algorithm Learning (METAL)*
project provides data and visualization capabilities for this purpose.
METAL's graph data sets range in size from a few vertices and edges to
several hundred thousand. Its data is derived from
the

Travel Mapping (TM)
Project, and represents highway systems from around the world.
Its map-based visualization capabilities are built
with

Leaflet Maps. METAL's
interactive code-level algorithm visualization capabilities with
debugger-like controls are intended to aid student understanding of
graph and other algorithms. Students can implement graph algorithms
themselves and display, in map form, the results of computations using
those algorithms when applied to METAL data.

Wouldn't it be more fun and interesting
to work with this graph

than this one?

Graph Data

TM's data is updated daily, and
an

updated collection of
graphs is generated almost as frequently from this data. These
graphs represent the highways in various regions, countries, and
highway systems, and are provided in
two

formats. Those interested can
read

more about where it comes from and how it is
generated. The highway systems available
in

Travel Mapping (TM), from which
METAL derives its data, vary in size, meaning graph data can be
generated at a variety of scales. They vary in size from just a
handful of vertices and edges for systems in small island nations to
hundreds of thousands for the entire data set.

The Highway Data Examiner

Leaflet is an open-source JavaScript library that provides interactive
maps. It is an attractive alternative to services like Google Maps or
Bing which have significant usage restrictions. The

Highway Data Examiner (HDX) is built using Leaflet,
and that allows plotting of the TM and derived data, and supports
interactive algorithm visualizations.

Usage in Class Assignments

These graph data files can be used as input for class examples or
assignments in a data structures, algorithms, or other courses. This
data was first used in a laboratory assignment for a data structures
course at Mount Holyoke College where students were required to build
a graph structure representing a highway system then perform
Dijkstra's algorithm to compute the shortest route between two
specified waypoints. Student programs generated output files listing
the road segments along the shortest path. These were then uploaded
to a course web server, where an instructor-provided program (an early
predecessor to today's HDX) used the Google Maps API to visualize
their results. Students were able to develop and debug their programs
using small data sets like the Hawaii Interstates, then use those
programs to compute much more complex routes using the larger data
sets. The software has been updated and extended and used in several
courses at Siena College and The College of Saint Rose. Successful
assignments include the creation of custom classes to store the
information about the points and connections between them, storing
these points and connection in a data structure and then searching
within and sorting those points (a great way to motivate comparators),
finding convex hulls, performing graph traversals, and more advanced
graph algorithms including Dijkstra's algorithm.

Interactive Algorithm Visualization

HDX includes support for interactive algorithm visualization. After
loading a graph data file into HDX. From there, an algorithm can be
chosen, along with any needed parameters (e.g., a starting vertex for
a traversal). A set of controls are used to start, pause, reset, or
change the speed of the simulation. During the simulation, the data
is displayed in both tabular and map form, and with HDX's action-based
framework, an algorithm's code can be simulated line-by-line, and
conditional breakpoints can be used to stop the simulation at points
of interest. Our expanding set of algorithms supported include simple
vertex- and edge-based searches, closest pairs, graph traversals,
finding connected components, finding convex hulls, Dijkstra's
algorithm for single-source shortest paths, and Prim's algorithm and
Kruskal's algorithm for minimum spanning trees.