Computer Science 385
Design and Analysis of Algorithms

Spring 2017, Siena College

Home     Syllabus     Schedule

Homework Set 3
Due: Start of Class, Monday, April 10, 2017

You may work alone or with a partner 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 will not prepare you for the exams.

Please submit a hard copy: print your code (consider 2-up double-sided printing), and either a typeset (preferred) or handwritten (must be legible) set of responses for the written problems. Only one submission per group is needed.

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 homework set if you wait until the last minute. A slow and steady approach will be much more effective.

Written Problems

1. (10 points) In the fraudulent voters problem, the input consists of two arrays: V[0...n-1] contains the names of n voters that participated in a recent election, and IE[0...m-1] contains the names of m persons ineligible to vote (because of something such as a felony record, deceased, etc...) In this problem, the task is to determine how many of the voters in V were actually ineligible to vote. For example, for the two arrays below, 2 should be returned as the answer, because voters "T. Smith" and "J. Doe" were ineligible to vote. You may assume there are no duplicate names in the arrays. 

V[0...7] = {"A. Turing", "T. Smith", "B. McKeon", "G. Gordon",
   "J. Doe", "M. Taylor"}
IE[0...4] = {"Z. McBeth", "J. Doe", "T. Jones", "T. Smith", "N. Wirth"}

You could easily write a brute force algorithm solving this problem in O(nm) time. But the number of voters in both arrays is very large, and so an asymptotically more efficient algorithm is required. Write such an algorithm below, give its worst case running time, and briefly explain how you got it. 

  // Returns the number of voters that were ineligible to vote.
  ALGORITHM NumFraudulentVoters(V[0...n-1], IE[0...m-1])

2. (15 points) You learned about d-heaps as part of the last lab. You also know about heapsort, which uses a 2-heap as an intermediate representation to sort the contents of an array. Let's consider a generalization of the heapsort idea:

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.). For each of the following underlying PQ structures, state which sorting algorithm proceeds in the manner most similar to the PQ-based sort using that PQ structure, and explain your answer. Each response should be at least a few sentences long, and should discuss how the pattern of comparisons and swaps, and the resulting efficiency relates to the sorting algorithm.

  1. 1-heap
  2. 3-heap
  3. (n-1)-heap
  4. binary search tree
  5. balanced binary search tree

3. (15 points) For the robot coin collection problem described in section 8.1 of Levitin, do the following:

a. Complete the pseudocode below that uses a recursive exhaustive search algorithm to solve it. 

// Returns the maximum number of coins the robot can collect if she starts
// at row r and column c and only moves once cell right or down in each step
// and stops only when she reaches the lower right corner.
  
ALGORITHM RobotCoinCollection( r, c, C[1..n,1..m] )

b. Now rewrite your algorithm from above so that it uses top-down dynamic programming to get a recursive algorithm that is more efficient. 

// Assume each entry of sols[1..n][1..m] is initialized to -1 before
// the first call.

ALGORITHM RobotCoinCollection( r, c, C[1..n][1..m], sols[1..n][1..m] )

c. What is the worst case running time of your algorithm in part (b)? Explain.

Dijkstra's Road Trip

Your programming task for this assignment is to develop a 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!

Overview of Basic Requirements

You should use a variant of Dijkstra's Algorithm to compute shortest path from a given starting point (a graph vertex) to a given destination point. The general form of Dijkstra'a Algorithm computes the shortest paths from a starting vertex to all other vertices, but you will be able to stop one you find a shortest path to the specified destination rather than calculating the shortest path to all other places. You will also need to make sure that you can efficiently print/write the computed route in the proper order (starting point to destination point).

Once a shortest path is computed, you will need to be able to output it to the terminal in a human-readable form and to a file in a format plottable by METAL's Highway Data Examiner (HDX).

For example, if you load the NY-all.tmg file (available from METAL's graph repository ), and compute a shortest path for a few nearby points: US9/NY2 (Latham Circle). and NY5/NY32 (next to the Times Union Center in downtown Albany), your path would traverse the following points: 

US9/NY2, US9/NY155, US9/NY378, US9/NY377,I-90(6)/US9,
US9/US9W, US9/NY32, NY5/NY32

Your "human readable" output might look something like this: 

Travel from US9/NY2 to US9/NY155
 for 0.78 along US9, total 0.78
Travel from US9/NY155 to US9/NY378
 for 2.24 along US9, total 3.02
Travel from US9/NY378 to US9/NY377
 for 2.04 along US9, total 5.06
Travel from US9/NY377 to I-90(6)/US9
 for 0.44 along US9, total 5.50
Travel from I-90(6)/US9 to US9/US9W
 for 0.87 along US9, total 6.38
Travel from US9/US9W to US9/NY32
 for 0.64 along US9, total 7.02
Travel from US9/NY32 to NY5/NY32
 for 0.34 along NY32, total 7.36

Your plottable data for HDX should be in a ".pth" file. This file format must match the following: 

START US9/NY2 (42.748115,-73.761048)
US9 US9/NY155 (42.736832,-73.76225)
US9 US9/NY378 (42.704925,-73.754568)
US9 US9/NY377 (42.675873,-73.747659)
US9 I-90(6)/US9 (42.669562,-73.748817)
US9 US9/US9W (42.659938,-73.759975)
US9 US9/NY32 (42.654285,-73.750019)
NY32 NY5/NY32 (42.649869,-73.752787)

Here, each line describes one "hop" along the route, consisting of the road name of the segment (i.e., your edge label), the waypoint name (i.e., the label in your vertex), and the coordinates of that point. The exception is the first line, where we substitute START, since you don't have to take any road to get to your starting point.

These files should be given a .pth extension. Once such a file is created, it can be visualized by directing a browser at /metal/hdx/ and uploading the .pth file in the file selection box at the top of the page.

Please take advantage of HDX to view the graphs themselves and your computed paths!

Starter Code

To get you started, a small collection of Java classes are provided that expand on the graph structure we worked with earlier in the semester.

In particular, the HigwayGraph class, and its auxiliary classes, HighwayVertex, HighwayEdge, and LatLng, provide much of the underlying functionality you will need. Note that most of the fields are declared as protected, so you can access them directly from your code as long as 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 you can focus on the actual algorithm implementation.

There is also a class Dijkstra provided that 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.

Note that there is a named constant DEBUG that should be used to turn on or off "debugging" output. It will be much easier to develop your Dijkstra's algorithm implementation step-by-step if you work on a small graph and print lots of information about the vertices and edges being considered at each step by the algorithm. If you encapsulate all of this kind of output inside if (DEBUG} { ... } blocks, you can simply set DEBUG to false when you want to turn it off.

What You Need to Add

Your task is to implement Dijkstra's algorithm to compute and report the shortest path from start to dest.

You should follow the algorithm as discussed in class, with the following modifications:

When your main loop terminates (because you found the shortest path to dest), you will print out the driving directions from start to dest.

If four command-line parameters were specified (that is, if args.length == 4), then args[3] will contain the name of a file where you should write a .pth file with the route that can be plotted on the map by HDX.

Implementation Details

Bonus Opportunties

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

  1. Directions that mention every intersection, even those where you are simply supposed to continue along in the same direction on your current road, can be a little verbose. For 4 bonus points, compress the human-readable directions to mention only those points where your route changes (i.e., where the edge label changes from one segment to the next). For example, getting directions in NY-all.tmg from US9/NY2 (Latham Circle) to NY86@MirLakeDr (Lake Placid) results in a path length of 38. However, since many of those are consecutive points from one I-87 exit to the next or along US 9, the compressed directions simplify to: 
    Travel from US9/NY2 to US9/NY7
 for 0.89 miles along US9, total 0.89
Travel from US9/NY7 to I-87(7)/NY7
 for 0.35 miles along NY7, total 1.24
Travel from I-87(7)/NY7 to I-87@14&NY9P@I-87&NY9PTrkSar@NY9P
 for 22.17 miles along I-87, total 23.41
Travel from I-87@14&NY9P@I-87&NY9PTrkSar@NY9P to
 I-87(15)/NY9PTrkSar/NY29TrkSar/NY50
 for 1.74 miles along I-87,NY9PTrkSar, total 25.15
Travel from I-87(15)/NY9PTrkSar/NY29TrkSar/NY50 to I-87(30)/US9
 for 72.23 miles along I-87, total 97.38
Travel from I-87(30)/US9 to US9/NY73
 for 2.14 miles along US9, total 99.52
Travel from US9/NY73 to NY9N_S/NY73_S
 for 11.19 miles along NY73, total 110.71
Travel from NY9N_S/NY73_S to NY9N_N/NY73_N
 for 1.64 miles along NY9N,NY73, total 112.36
Travel from NY9N_N/NY73_N to NY73/NY86
 for 13.45 miles along NY73, total 125.81
Travel from NY73/NY86 to NY86@MirLakeDr
 for 0.87 miles along NY86, total 126.68
  2. 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.

Deliverables and Grading Breakdown

The required functionality here is worth 60 points total.