# Project #49323 - Data Structures in Java homework

This homework has two parts, a written section, and a programming section.

Written

1. Weiss, Exercise 9.1.

2. Weiss, Exercise 9.7a.

3. Weiss, Exercise 9.10a.

4. Weiss, Exercise 9.15.

5. Weiss, Exercise 9.38a and 9.38b.

Programming

1. The file citypairs.dat contains selected city pairs and their distances. Each line of the file contains 2 city names and a distance. Assume that these links are bi-directional, if you can from NewYork to Boston, you can get from Boston to NewYork. Write a program to calculate the shortest path between any given city pair. Your program should do the following:

• Read in the city pairs and distances.
• Implement Dijkstra's algorithm using as the edge cost the given city pair's distance. You should use the priority queue implementation of Dijkstra's algorithm. Input should be via a Java GUI window that asks for the source and destination cities.
• Map the cities onto the window and draw the shortest path in the window between those cities. A list of (X,Y) coordinates for each of the cities can be found in the file cityxy.txt.
• Display in the window the path length of the shortest path.
2. Read in the cities from the cityxy.txt city/coordinate file that you used in the previous problem. Assume that the cities in the graph are fully connected - an edge exists between every city pair. Use the 2-D Euclidean distance between two cities as the edge cost. Using these edge costs (the path lengths), implement Kruskal's algorithm for finding the minim spanning tree of the city graph. Output the edge pairs that make up the minimum spanning tree to the console. Create a GUI window and draw a map of the cities, include the edges that are part of the MST that you calculated by Kruskal's algorithm.

What you need to submit:

The written portion of this assignment should be submitted as part of your electronic submission, include a word document or text file in your zip file.

DO NOT SUBMIT CLASS FILES, only submit the source java files and the README.txt. We will compile the programs for you. Once all the files are in place, make a zip file out of that directory.

 Subject Computer Due By (Pacific Time) 12/06/2014 05:00 pm
TutorRating
pallavi

Chat Now!

out of 1971 reviews
amosmm

Chat Now!

out of 766 reviews
PhyzKyd

Chat Now!

out of 1164 reviews
rajdeep77

Chat Now!

out of 721 reviews
sctys

Chat Now!

out of 1600 reviews

Chat Now!

out of 770 reviews
topnotcher

Chat Now!

out of 766 reviews
XXXIAO

Chat Now!

out of 680 reviews