Introduction and General Overview

Welcome to Part 2 of the Summer 2018 edition of Dr. Hugue's CMSC 420 project. Note that you may need to refer to the part 1 specification since parts 2 and 3 build on it. A substantial portion of your grade in this course will be determined by your performance on several programming assignments (collectively referred to as The Project). The time commitment required on your part varies from student to student, but expect to spend a good bit of time planning as well as coding and debugging each part of the projects.

The primary motivation of this project is to give you the experience of building portions of a real world application using the data structures and algorithms that we will study during the semester. This semester's long term goal is to mimic some of the functionality of MapQuest ². By the end of this course, if you have worked hard and done your job well, you will have a program 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; and just generally impressing friends and family with its awesome ability to tell you how to get to where you want to be in both plain text and picture form. And, even if things don't go smoothly, you will have had the opportunity to think about data structures, and programming in general, in new and interesting ways.

Note on the integrity policy: We will provide you with a working implementation of the previous part, and resources (including some pseudocode) for implementing the structures required for part 2. However, you may be tempted to search for code online. Using any code from github (especially from someone who has taken this class in the past) is prohibited. Using any code from the internet to implement the PM quadtree is not allowed. You may only use code we give you, or class resources. For implementing SortedMap with the Avl-G, you are permitted to adopt from the source code of Java's implementation of the SortedMap interface - TreeMap. It implements a red-black tree, while you will be implementing a avl-g, so any part of it that uses the red-black tree must be modified to use a avl-g instead. You are not allowed to explicitly use a TreeMap, TreeSet, skiplist, or any other complex data structure in your Avl-G implementation.

Any code you use that you did not write yourself must be documented in the README file, and wherever you used it. This includes, but is not limited to, the previous part canonical, TreeMap's source code, and source code from any other built in Java class. If you're unsure if you can use a piece of code, ask us.

Please read the complete integrity policy in Section 8.4.