Computer Science 385

Design and Analysis of Algorithms

Spring 2018, Siena College

You may work alone or in a group of 2 or 3 on this assignment. However, in order to make sure you learn the material and are well-prepared for the exams, you should work through the problems on your own before discussing them with your partner, should you choose to work with someone. In particular, the "you do these and I'll do these" approach is sure to leave you unprepared for the exams.

All GitHub repositories must be created with all group members having
write access and all group member names specified in the
`README.md` file by 4:00 PM, Friday, April 20, 2018. This applies to those who choose
to work alone as well!

There is a significant amount of work to be done here, and you are sure to have questions. It will be difficult if not impossible to complete the assignment if you wait until the last minute. A slow and steady approach will be much more effective.

Getting Set Up

You will receive an email with the
link to follow to set up your GitHub repository, which will be named
`ps7-yourgitname`, for this problem set. One member of the
group should follow the link to set up the repository on GitHub,
then that person should email the instructor with the other group
members' GitHub usernames so they can be granted access. This will
allow all members of the group to clone the repository and commit
and push changes to the origin on GitHub.

Submitting

Your submission requires that all required code and other electronic deliverables are committed and pushed to the master for your repository's origin on GitHub. That's it! If you see everything you intend to submit when you visit your repository's page on GitHub, you're set.

For written questions, you may submit a hard copy (typeset preferred,
handwritten OK but must be legible) or you may answer the questions in
your repository's `README.md` file.

Only one submission per group is needed.

Backtracking Practice

Dijkstra's Road Trip

We've looked at Dijkstra's algorithm for single-source shortest paths in class and in an earlier lab. We will again work with METAL's visualization of this algorithm and then a Java implementation that can be used on larger examples. That Java program is capable of producing output that can be visualized in METAL's Highway Data Examiner (HDX).

Your repository includes a working implementation of Dijkstra's algorithm that produces simplified "driving directions" system based on the mapping data you have been working with. It will be like taking a road trip with Professor Dijkstra himself!

A Closer Look at Dijkstra's Algorithm

Let's experiment with Dijsktra's algorithm on some METAL graph data of
the local area. In particular, we'll travel from the Latham Circle
(graph waypoint `US9/NY2`, #501) to the Times Union Center (graph
waypoint `US9/NY32`, #552).

Point your browser at HDX at
`http://courses.teresco.org/metal/hdx/`
and load up the `siena-area50.tmg` graph (in the list as "Siena
College (50 mi radius)"). Choose "Dijkstra's Algorithm" and the
start and end vertices noted above. Start on a slow setting and watch
the progression. Shortly after you start, pause the simulation and
zoom in on the area near Siena so you can see what's happening.
Resume the simulation and pause it again when you notice the
destination vertex is in the priority queue (PQ).

Now let the simulation run to completion.

Now we will move on to the Java implementation of Dijkstra's algorithm. First, familiarize yourself with the code. Here are some notes:

- The
`HigwayGraph`class, and its auxiliary classes,`HighwayVertex`,`HighwayEdge`, and`LatLng`, provide much of the underlying functionality. Note that most of the fields are declared as`protected`, so they can be accessed directly from code in the`Dijkstra`class since it is also in Java's "default" package. This is not ideal from a design perspective, but is done to simplify much of the code so`Dijkstra`can focus on the actual algorithm implementation. - The provided class
`Dijkstra`processes the required command-line parameters and sets up the`HighwayGraph`and finds references to the`HighwayVertex`objects for the start and destination of the driving directions request. If four command-line parameters were specified (that is, if`args.length == 4`), then`args[3]`will contain the name of a file where the program writes a`.pth`file with the route that can be plotted on the map by HDX. - Note that there is a named constant
`DEBUG`that is used to turn on or off "debugging" output. Setting this to`true`(really only appropriate when working on a small graph) prints lots of information about the vertices and edges being considered at each step by the algorithm. - This version of the algorithm follows the pseudocode we
considered earlier. It uses a
`PriorityQueue`containing`PQEntry`objects, which are`Comparable`. It stops as soon as it finds the shortest path to the destination. This will be the stopping condition on your main loop. As written, it assumes that a path exists between your starting and ending vertices, so it is concerned that the priority queue will become empty. - When we traced the algorithm in class and lab, the values in the
table of shortest paths found included both the last edge traversed
and the total distance traversed. Here, we only need to keep the
last edge traversed. These are kept in a
`Map`with strings (vertex/waypoint labels) as keys and`HighwayEdge`objects as values.

The `siena50-area.tmg` graph is also in your repository.

Run `Dijkstra` with this example and with debug mode turned on,
using the same points as above (`US9/NY2`and `US9/NY32`) as your
start and end. Verify that your answer matches what you saw from the
HDX algorithm visualization.

Run the same example, now with the option to generate the path file
`latham-albany.pth`. View this file in HDX and generate a screen
capture.

The advantage of the Java implementation over the interactive algorithm visualization is that you can compute shortest paths on much larger graphs.

Also in your repository is a graph of all routes known to METAL in the
United States, called `USA-country.tmg`. Run the `Dijkstra`
program on this graph to compute the shortest path from `US9@FidLn`
(the closest point to Siena) to `US41@5thAve` (downtown Naples,
Florida). Create 3 screen captures: the closest view you can get
that has an overview of the entire route, a zoomed-in view showing the
route from its starting position to the Kingston area, and a zoomed-in
view showing all of the route as it passes through Maryland.

Bonus Opportunties

There are two opportunties to earn bonus points on this problem set. Make your suggestions for other bonus ideas and approved ideas will be added here.

- The first bonus opportunity that previously occupied this slot is cancelled, since the code distributed in your repositories included this! Sorry!
- For 2 bonus points, gracefully handle the situation where the
`start`and`dest`vertices are not connected. This could happen, for example, in Hawaii, if you ask for directions between two points on different islands.

Related Algorithms

We noted in a recent lab the similarities between Dijsktra's algorithm and a few others. Your task here is to make the small changes to the provided Dijkstra's algorithm implementation to make it an implementation of each of the algorithms listed below.

- Prim's algorithm
- Breadth-first traversal
- Depth-first traversal

It is your choice whether you prefer to add command-line parameters to
the existing code or make new classes that are almost identical to
`Dijkstra` to do each. However, you should make changes *only
to the value used as the priority for the PQEntry class*.
Everything else should be unchanged. This means that you will still
have a start and an end location and will stop when you first reach
the end location.

Your code submission for this part is worth 20 points.

Once you have this working, use your program(s) to compute the paths
that would be computed for each of the earlier examples (Latham Circle
to the Times Union Center, Siena College to Naples, and the one you
chose). **Note:** the Siena to Naples is done on a large graph, and
depth-first and breadth-first are likely to generate really long paths
and/or take a very long time to compute. You may replace that with a
an additional (different and smaller) example of your choice.

Generalized Heaps and Heapsort

You reviewed heapsort and learned about d-heaps as part of a recent lab. In a sense, heapsort uses a 2-heap as an intermediate representation to sort the contents of an array. Let's consider a generalization of the heapsort idea:

- First, insert the elements to be sorted into a PQ.
- Then, remove the elements one by one from the PQ and place them, in that order, into the sorted array.

For heapsort, the PQ is a 2-heap, but any PQ implementation would work
(naive array- or list-based with contents either sorted or unsorted, a
d-heap, or even a binary search tree). Depending on which underlying
PQ is used, the sorting procedure will proceed in a manner similar,
in terms of the order in which comparisons occur, to one of the other
sorting algorithms we have studied (*e.g.*, selection sort, quicksort,
*etc.*).

- 1-heap
- 3-heap
- (n-1)-heap
- binary search tree
- balanced binary search tree