Ask Question, Ask an Expert

+61-413 786 465

info@mywordsolution.com

Ask Computer Engineering Expert

Algorithms Assignment -

TASK -

1. Design and implement an efficient algorithm for determining the best route between two given stations in a given rail network.

2. The rail network should be passed to your program as an input. We will use a simplified version of the Sydney CityRail network given to you in RailNetwork.xml

3. Your program should NOT take into account the time of the day, but rather use an average time to travel from a station to a station on a particular line, and a flat time of 15min needed to change from one line to another. This information will be given as a part of the input rail network data.

4. Your task is to optimise the route based on the time traveled.

Your program should contain a header with information about what it does and what the input and output are. You must use a version of Dijkstra's algorithm that uses adjacency lists and indirect heaps.

Your program should also contain inline comments and be easy to follow.

The programs should be written in Java or C++.

INPUT -

Your program must be able to be used from the command line and must accept all input as command line arguments.

1. Your program must take as an input the name (including path if necessary) of an XML file containing an undirected graph of the rail network:

  • The graph is provided as a list of neighbours for each vertex in the graph.
  • Each vertex corresponds to a station in the network, and each vertex name consists of 2 strings: The name of the station, and the name of the rail line. A single station might thus be represented by multiple vertices if it is on multiple lines.
  • Each entry in the list of neighbours of vertex v contains the name of the neighbouring vertex, say u, followed by the weight of the edge vu. If the vertices v and u are on the same line, the weight of the edge vu is the time in minutes needed to travel from vertex v to vertex u (or vice-versa - it is assumed that the time is the same for both directions). If the vertices v and u are not on the same line, the weight of the edge vu is 15 (we are assuming that it takes 15 minutes to change lines at a station).

A sample input file RailNetwork.xml will be provided in Blackboard. You don't need to create other input files - you can use this one for the purpose of developing and testing your assignment.

It is advised that you investigate the many pre-existing libraries (for Java or C++) available for working with XML and incorporate those into your program. Then, reading the data from the xml file and navigating the data should amount to (reasonably) simple calls to the classes and methods of the library in question.

2. Your program must accept as input the names of two stations, say X and Y.

The order of command line arguments must be: xml file, station 1, station 2, optimisation criterion (if appropriate) see SUBMISSION section, below for more information.

OUTPUT

1. Individual assignment:

You program must output the quickest route in the following format: From X, take line a to station Z; then change to line b, and continue to W; then change to line c, and continue to Y. The total trip will take approximately n minutes.

Attachment:- Assignment Files.rar

Computer Engineering, Engineering

  • Category:- Computer Engineering
  • Reference No.:- M93135703

Have any Question? 


Related Questions in Computer Engineering

Question suppose that a remote transmitter sends a message

Question : Suppose that a remote transmitter sends a message at 2500 Baud and the receiver is expecting the data rate to be 2400 Baud. Calculate the accumulated sample error for one character. Give the answer in bits.

A random sample of n data values is obtained from a process

A random sample of n data values is obtained from a process having an absolutely continuous cdf of unknown shape. The metallurgist wants to select the best fitting distribution among several candidate cdfs. She decides t ...

Question suppose that the equallists function page 49 of

Question : Suppose that the equal_lists function (page 49 of Sebesta's Book Concepts of Programming Languages edition 11) is called with the lists ((A (B)) (C)) and ((A (B)) (C)) as the arguments. How many calls of equal ...

Its almost election day and the election officials need a

It's almost election day and the election officials need a program to help tally election results. There are two candidates for office-Polly Tichen and Ernest Orator. The program's job is to take as input the number of v ...

Suppose that alices rsa parameters are ma91 ea7 and da31

Suppose that Alice's RSA parameters are m_A=91, e_A=7, and d_A=31. And suppose that Bob's RSA modulus is m_B=187. a)If Bob's public exponent is e_B=13 and Alice wants to encrypt the message signature pair (x, delta)=(70, ...

Representing problems as graphs i have 10 and i plan to

Representing Problems as Graphs I have $10, and I plan to spend some or all of my money on three types of candy, which I will buy one piece at a time: chocolate bars cost $3, almond rocca cost $2, and caramel chunks cost ...

Subject digital securityimagine a scenario that you go to a

Subject: Digital security Imagine a scenario that you go to a restaurant and pay the meal using your credit card. What communication parties are involved and what information is exchanged in order to complete this transa ...

Starbucks the enclosed is the strategy definition for

Starbucks: The enclosed is the Strategy Definition for Starbucks. ( 1-2 pages rought draft) Using one of the cases studies in the text or one identifed by the team on its own, prepare a report addressing the following ke ...

Questionhow can you start business by mobile application

Question How can you start business by Mobile Application Development ? Discuss the testing process of Mobile Applications in detail ? List important steps for publishing an app in the Target Market ?

Question 1 select a specific activity or responsibility of

Question: 1. Select a specific activity or responsibility of the systems analyst. Define the purpose of the systems analyst and why it is important in the overall systems analysis process. Write this post to an audience ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

Why might a bank avoid the use of interest rate swaps even

Why might a bank avoid the use of interest rate swaps, even when the institution is exposed to significant interest rate

Describe the difference between zero coupon bonds and

Describe the difference between zero coupon bonds and coupon bonds. Under what conditions will a coupon bond sell at a p

Compute the present value of an annuity of 880 per year

Compute the present value of an annuity of $ 880 per year for 16 years, given a discount rate of 6 percent per annum. As

Compute the present value of an 1150 payment made in ten

Compute the present value of an $1,150 payment made in ten years when the discount rate is 12 percent. (Do not round int

Compute the present value of an annuity of 699 per year

Compute the present value of an annuity of $ 699 per year for 19 years, given a discount rate of 6 percent per annum. As