Subject Computer Science Data Structures and Algorithms

Question

Purpose

To give you experience with graphs and graph algorithms which are fundamental to the field of computer science.

Action Items

1- Part 1- Problem: For the following problem:
A- Choose an appropriate problem solving technique;

b- Select your favorite programming language such as C, C++, or Java. In that language, write, implement, and test an algorithm using the problem solving technique that you chose;

c- Analyze your implementation using either order notation analysis or empirical analysis. You must prepare a separate page providing the instructions to compile and execute your program, such as the development environment (e.g., Visual Studio). If no such information is provided, and your program fails to build and run, points will be deducted by your professor, as appropriate.

The Colonel Motors Corporation of Frankfort, Kentucky has produced a new line of vehicles which require chicken droppings for fuel. Because of this unusual fuel requirement, there are only certain fueling stations in the country where the vehicles can be refilled. Thus, to get from one place to another, an owner must plan a route that ensures that he can get refills along the way. The Colonel Motors Corporation has hired Professor Sanders of the Kentucky Institute of Technology as a consultant to prepare an online route-finding service. To use the computerized service, an owner will enter the driving range of his vehicle (the distance the vehicle can go on a single fill-up), the "distance to empty" (the distance the vehicle can go with the fuel that's now in the tank), his/her initial location (source), and his/her desired destination. The service will either respond with a shortest route from the source to the destination such that the owner never runs out of fuel, or it will deem that no such route exists. Model the professor's problem in terms of a weighted, directed graph in which streets are edges, intersections are vertices, and some intersections have fueling stations, and design an efficient algorithm to solve it. Assume that a driver's source and destination are also at intersections.

2- Part 2- Research Paper: Choose ONE of the following applications or another application that interest you. After conducting your own research, write a paper (minimum length, 3 pages, double-spaced, 12-point font, such as Times New Roman) describing the use, importance, and design of a graph algorithm or graph algorithms in your chosen application.
Power Routing
Cosmology
Biomedical Image Analysis
Astronomy
Weather Data Interpretation
Robot Navigation

Note:

You are required to use appropriate APA citation and referencing for this paper. Use the current edition of the American Psychological Association (APA) Publication Manual, to determine the correct format for the citations and references that you use:

a- Use properly formatted in-text citations and a reference list to accurately cite the sources of information that you use to write your paper. Failure to use proper citations and references is plagiarism and could result in a charge of academic dishonesty.

b- Consult APA Style & Academic Integrity Guidelines if you need further information about APA style and format.
Verify with your professor to ensure that you are able to:
Submit your paper to Turnitin.com;
Review your Originality Report from Turnitin.com; and
Re-submit your paper after you make changes (but before the due date).

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

#include<iostream>
using namespace std;

#define max 100 // maximal number of locations
#define infinity 999999    // infinite distance
// #define range 22 // maximal driving range on a single fill-up   

int main ()
{
//input edge weights of the graph
    //input driving rangle R
//input ditance to empty E

double graph[max][max];...

This is only a preview of the solution. Please use the purchase button to see the entire solution

$1.00

or $1 if you
register a new account!

Related Homework Solutions

5 Problems Involving Greedy Algorithms
Homework Solution
$50.00
Greedy
Algorithm
Analysis
Optimal
Program
Disk
Megabyte
Storage
Capacity
Decimalization
Denomination
Change-making
Half-crown
Florin
Shilling
Sixpence
Threepence
Pence
Coin
Solution
Selection
Sort
Framework
Decomposition
Egyptian
Get help from a qualified tutor
Live Chats