This repo contains infamous capstone project for CMSC420 by Dr. Michelle Hugueat, known as "MeeshQuest", at University of Maryland College Park. Overall, it is one of the most challenging course projects for CMSC senior udergrad and graduate students at UMD.

The project wiki: https://wiki.cs.umd.edu/cmsc420/index.php?title=MeeshQuest

The primary motivation of this project was to give students the experience of building portions of a real world application using the data structures and algorithms learned in the data structures class. During the semester students worked independently to implement a stripped down version of MapQuest that is capable of drawing maps of a general area and supporting the following functions: displaying a highlighted route; calculating shortest routes (based on time or distance); generating driving instructions (complete with correct "turn left and then go straight for 2.34 miles" annotations); determining closest points of interest, such as all of the "Internet Cafes" within a 20 mile radius of College Park, MD.

The project comprises four parts, which build upon one another to produce the desired features of an on-line mapping system.

• Part 0: A warmup on Java language. Implement a data dictionary that supports both city names and city coordinates as keys, using treemap and treeset as the backbone. Write an interpreter that is able of handling basic XML commands.
• Part 1: Implement a spatial map using a Point Region (PR) quadtree. The role of the spatial map is to support range searches where, given a location in 2-d space and a radius, we will find all the cities within that circle, including on the border. These types of operations are allegedly not efficient using the treemap of coordinates.
• Part 2: Implement a treap that implements the SortedMap interface with insertion and deletion and use it to replace treemap. Make a PM3 Quadtree to store both cities and roads. Make a road adjacency list for use in finding the shortest path between two cities. Implement Dijkstra's algorithm.
• Part 3: Implement a PM1 Quadtree and the delete method of PM3 Quadtree for storing cities and roads. Construct a minimum spanning tree using Prim's algorithm.

The PR and PM quadtree are essential to the overall efficiency of the application. The PR quadtree represents a collection of data points in two dimensions by decomposing the region containing the data points into four equal quadrants, subquadrants, and so on, until no leaf node contains more than a single point. A PM quadtree is similar to PR quadtree, but stores lines instead of points and ends up storing both (a line is defined by two points). There are three main classes of PM Quadtrees, which vary depending on what information they store within each black node (see the wiki page). Quadtrees are often used in video games for their blazing fast collision detection.

In addition to the data structures, students also implemented the "good old" dijkstra's algorithm for finding shortest paths and Prim's algorithm for finding minimum spanning trees.

All code is in Java. Students put into practice object-oriented design and the Mediator design pattern, which means objects don't communicate directly with each other, but instead communicate through a mediator.

Fan Yang