Implement an algorithm to simulate car re-organizing, Data Structure & Algorithms

Design  and implement  an algorithm  to simulate car  re-organizing of the train at the railway switching junction. You can only use stacks as the data structure to represent the train and the cars in each transit rail.

Task 1: For any given  input of car order is  c1,c2,...,cn  and  a number  k  of transit rails (k≥2), design and implement an algorithm to simulate the car ordering procedure by using stack operations only so that the output of the car order is 1,2,...,n.

Task 2:  Analyse efficiency of your algorithm using Big-O notation by counting the number of stack operations used in your algorithm ( worst case analysis).

Task 3: Assume that k=n/2+1. Improve your algorithm so that its complexity is in O(n).  

Task 4: Discuss the efficiency of your algorithm in relation to k if k can be any number such that k≥2.

Posted Date: 3/29/2013 5:28:09 AM | Location : United States







Related Discussions:- Implement an algorithm to simulate car re-organizing, Assignment Help, Ask Question on Implement an algorithm to simulate car re-organizing, Get Answer, Expert's Help, Implement an algorithm to simulate car re-organizing Discussions

Write discussion on Implement an algorithm to simulate car re-organizing
Your posts are moderated
Related Questions
The searching technique that takes O (1) time to find a data is    Hashing is used to find a data

write an algorithm for multiplication of two sparse matrices using Linked Lists

implement multiple stacks in a single dimensional array. write algorithm for various stack operation for them

Program segment for the deletion of any element from the queue delmq(i)  /* Delete any element from queue i */ { int i,x; if ( front[i] == rear[i]) printf("Queue is

1) preorder, postorder and inorder 2) The main feature of a Binary Search Tree is that all of the elements whose values is less than the root reside into the nodes of left subtr

Q. A Binary tree comprises 9 nodes. The preorder and inorder traversals of the tree yield the given sequence of nodes: Inorder :          E     A    C    K    F     H    D

Two-dimensional array is shown in memory in following two ways:  1.  Row major representation: To achieve this linear representation, the first row of the array is stored in th

Each of the comparison in the binary search decrease the number of possible candidates where the key value can be searched by a factor of 2 as the array is divided into two halves

B-trees are special m-ary balanced trees utilized in databases since their structure allows records to be added, deleted & retrieved with guaranteed worst case performance. A B-

What data structure would you mostly likely see in a nonrecursive execution of a recursive algorithm? Stack