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
Following are some of the drawback of sequential file organisation: Updates are not simply accommodated. By definition, random access is impossible. All records should be

Explain an efficient way of storing a sparse matrix in memory.   A matrix in which number of zero entries are much higher than the number of non zero entries is called sparse mat

1. Give both a high-level algorithm and an implementation (\bubble diagram") of a Turing machine for the language in Exercise 3.8 (b) on page 160. Use the ' notation to show the co

Q. Write down an algorithm to sort a given list by making use of Quick sort method. Describe the behaviour of Quick sort when input given to us is already sorted.

Since memory is becoming more & cheaper, the prominence of runtime complexity is enhancing. However, it is very much significant to analyses the amount of memory utilized by a prog


Algorithm to Delete a given node from a doubly linked list Delete a Node from Double Linked List DELETEDBL(INFO, FORW, BACK, START, AVAIL,LOC) 1. [Delete Node] Set FOR

The above 3 cases are also considered conversely while the parent of Z is to the right of its own parent. All the different kind of cases can be illustrated through an instance. Le

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

ESO207: Programming Assignment 1 Due on 6 Sept, 2015. To be submitted online. Problem In this assignment you are required to implement k-way Merge Sort algorithm. In this version p