It\'s a written practice paper, no code required. I think pseudo-code is ok thou
ID: 3687360 • Letter: I
Question
It's a written practice paper, no code required. I think pseudo-code is ok though.
For a given stack and 4 numbers, say, 1, 2, 3 and 4, do the followings, (1) push the first number; (2) push the second number; (3) pop the stack; (4) push the third number; (5) push the fourth number; (6) pop the stack; (7) pop the stack; (8) pop the stack. As a result of these operations the original order of the numbers, 1234, has been changed into 2431. We say that the operations from (1) to (8) permute the original order into another order. Now, suppose there are 6 numbers, 1, 2, 3, 4, 5 and 6, with the original order 123456, can they be permuted into the order 325641? Can they be permuted into the order 154623? If possible, show how to do it. (b) The operations (1) through (8) in (a) can be described by the code IIOIIOOO, where I stands for "push an number into the stack" and O stands for "pop the sfcacic". Some sequences of I's and O's specify meaningless operations, since there may be no numbers available in the stack; for example, the sequence OIIOOIIO cannot be carried out, since we assume that the stack is initially empty. Let us call a sequence of I's and O's admissible if it contains n I's and n O's, and the operations it specified can be performed. Formulate a rule by which it is easy to distinguish between admissible and inadmissible sequences; show furthermore that no two different admissible sequences give the same output permutation. (c) Consider the (a) part of this question, with a queue substituted for a stack. What permutations of 12 n can be obtained with use of a queue?Explanation / Answer
a)Now,we are having 6 numbers 1,2,3,4,5,6.
To get permutation sequence 325641:
steps: push(1),push(2),push(3),pop(),pop(),push(4),push(5),pop(),push(6),pop(),pop(),pop()
To get permutation sequence 154623
we didn't get this permutation.Why becasue?
push(1),pop(),push(2),push(3),push(4),push(5),pop(),pop(),push(6),pop() afer perfroming these
steps on stack we get 1546..after that we pop stack means we get 3 not 2
b)For every number we perform two operation only.either push(x),pop().
If we are getting after these operation at every number.we get the same number then it is admissible.otherwise inadmissable.
For every admissible sequence we are having different permutation.No thought of same output permutation.
IF(SEQ OF OPERATION ON GIVEN NUMBER)==PERUMUTATION NUMBER
set result as ADMISSIBLE
ELSE
set result as INADMISSIBLE
c)Replacing stack with queue..then we get permutation how that sequence proceed.if we take the elements as
enqueue(1),enqueue(2),then apply dequeue().we get the values as 1 not 2.because queue operates FIFO
fashion.stack operates iLIFO fashion.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.