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
Overlapping or Intersecting A polygon overlaps or intersects the current background if any of its sides cuts the edges of the viewport as depicted at the top right corner of th

Describe different methods of developing algorithms with examples.

Question 1 Explain how the shuttle sort algorithm works by making use of the following list of integers:11, 4, 2, 8, 5, 33, 7, 3, 1, 6. Show all the steps. Question 2

If a node in a BST has two children, then its inorder predecessor has No right child

A graph G might be defined as a finite set V of vertices & a set E of edges (pair of connected vertices). The notation utilized is as follows: Graph G = (V, E) Consider the g

The fundamental element of linked list is a "record" structure of at least two fields. The object which holds the data & refers to the next element into the list is called a node .

In the book the following methods are presented: static void selectionSort(Comparable[] list) static void insertionSort(Comparable[] list) static boolean linearSearch(Comparable

Evaluate the frequency counts for all statements in the following given program segment. for (i=1; i ≤ n; i ++) for (j = 1; j ≤ i; j++) for (k =1; k ≤ j; k++) y ++;

Explain the Scan-Line Algorithm This image-space method for removing hidden surfaces is an extension of the scan-line algorithm for filling polygon interiors. Instead of fillin

What is String Carrier set of the String ADT is the set of all finite sequences of characters from some alphabet, including empty sequence (the empty string). Operations on s