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
QUESTION Explain the following data structures: (a) List (b) Stack (c) Queues Note : your explanation should consist of the definition, operations and examples.

Q. Explain the result of inserting the keys given. F, S, Q, K, C, L, H, T, V, W, M, R, N, P, A, B, X, Y, D, Z, E  in an order to an empty B-tree of degree-3.

REPRESENTATION OF ARRAYS This is not uncommon to determine a large number of programs which procedure the elements of an array in sequence. However, does it mean that the eleme

This is the most extensively used internal sorting algorithm. In its fundamental form, it was invented by C.A.R. Hoare in the year of 1960. Its popularity lies in the easiness of i

Which data structure is used for implementing recursion Stack.

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

The ?-Notation (Lower Bound) This notation provides a lower bound for a function to within a constant factor. We write f(n) = ?(g(n)), if there are positive constants n 0 and

A Stack has an ordered list of elements & an array is also utilized to store ordered list of elements. Therefore, it would be very simple to manage a stack by using an array. Thoug

CMY Model  The cyan, magenta, yellow (CMY) colour model is a subtractive model based on the colour absorption properties of paints and inks. As such it has become the standard

Multiplication Method: The multiplication method operates in 2 steps. In the 1ststep the key value K is multiplied by a constant A in the range O