Train reorganising, Data Structure & Algorithms

Assignment Help:

A freight train from Melbourne is approaching Sydney, carrying n cars of cargos. The cargos are to be delivered to n different cities in the metropolitan area of Sydney - one car for one city. To avoid delays of stoping at each city station, the train is to dismiss a car once the car arrives its destination station without unloading the car, providing the car was at the end of the train. Since all these cars of the train were collected on the way from Melbourne to Sydney, the order of these cars does not match the order of their designations. The train have to be reorganised in the Railway Switching Junction outside Sydney to reorder its cars to match the order of their destinations (See Figure). The aim of this assignment is to design and implement an algorithm to simulate the procedure of car re-ordering. 

1646_Train Reorganising.png

The above figure shows the diagram of the railway switching junction. The junction has a single entrance and a single exit on the main railway from Melbourne to Sydney. There are k transit rails, denoted by T1, T2, ..., and Tk, linked to the main railway for a train to transfer cars. The train can drive in or out each transit rail either forward or backward.

The train can be disconnected at any point between two cars. A car can be parked in a transit rail but cannot be left on the main track. A car cannot move without connecting to the engine (only one engine). We assume that the transit rails and their distance in between are long enough for the train to drive in and out in full length.

Assume that the destination stations in Sydney are labelled from 1 to n, arriving Station n first and ending at Station 1. Each car of the train is marked in accord with its destination.

When the train arrives, the order of the cars from the engine to the last car is c1,c2,...,cn, which can be any permutation of the numbers 1,2,...,n. As an example shown in Figure 1, when the train arrives the junction, the order of the cars is 4,3,5,1,2. The cars need to be re-ordered into 1,2,3,4,5 to be delivered at their destination stations.


Related Discussions:- Train reorganising

Cohen sutherland algorithm, Using the cohen sutherland. Algorithm. Find the...

Using the cohen sutherland. Algorithm. Find the visible portion of the line P(40,80) Q(120,30) inside the window is defined as ABCD A(20,20),B(60,20),C(60,40)and D(20,40)

Depth first search and breadth first search, Q. Illustrate the result of ru...

Q. Illustrate the result of running BFS and DFS on the directed graph given below using vertex 3 as source.  Show the status of the data structure used at each and every stage.

Method to add an element in circular queue, Q. Let us consider a queue is h...

Q. Let us consider a queue is housed in an array in circular fashion or trend. It is required to add new items to the queue. Write down a method ENQ to achieve this also check whet

Explain the different types of traversal on binary tree, Question 1 What i...

Question 1 What is a data structure? Discuss briefly on types of data structures Question 2 Explain the insertion and deletion operation of linked list in detail Qu

Explain avl tree, AVL tree An AVL tree is a binary search tree in which...

AVL tree An AVL tree is a binary search tree in which the height of the left and right subtree of the root vary by at most 1 and in which the left and right subtrees are again

Time required to delete a node x from a doubly linked list, The time needed...

The time needed to delete a node x from a doubly linked list having n nodes is O (1)

Infix expression into the postfix expression, Q. Write down an algorithm to...

Q. Write down an algorithm to convert an infix expression into the postfix expression.     Ans. Algo rithm to convert infix expression to post fix expression is given as

In-order traversal, Write steps for algorithm for In-order Traversal Th...

Write steps for algorithm for In-order Traversal This process when implemented iteratively also needs a stack and a Boolean to prevent the execution from traversing any portion

Queue be represented by circular linked list, Q. Can a Queue be represented...

Q. Can a Queue be represented by circular linked list with only one pointer pointing to the tail of the queue? Substantiate your answer using an example. A n s . Yes a

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd