# CMI2018-B-7

231 views

A First In First Out queue is a data structure supporting the operation Enque, Deque, Print, Enque(x) adds the item $x$ to the tail of the queue. Deque removes the element at the head of the queue and returns its value. Print prints the head of the queue.

1. You are given a queue containing $5$ elements. Using a single additional temporary variable $X,$ write down a sequence of statements each being one of Enque, Deque, Print so that the output of the program results in the $5$ elements of the queue being printed in reverse order.
2. If the queue had $n$ elements to begin with, how many statements would you need to print the queue in reverse order?
in DS
recategorized

Let queue contains elements $\bf{(1,2,3,4,5)}$ in order, with $1$ being the head. Therefore the below sequence of instructions will be displayed whenever the state of the queue changes.

Initial queue
X = Deque; Enque(X);
X = Deque; Enque(X);
X = Deque; Enque(X);
X = Deque; Enque(X);
Print;
X = Deque; Enque(X);
X = Deque; Enque(X);
X = Deque; Enque(X);
X = Deque; Enque(X);
Print;
X = Deque; Enque(X);
X = Deque; Enque(X);
X = Deque; Enque(X);
X = Deque; Enque(X);
Print;
X = Deque; Enque(X);
X = Deque; Enque(X);
X = Deque; Enque(X);
X = Deque; Enque(X);
Print;
X = Deque; Enque(X);
X = Deque; Enque(X);
X = Deque; Enque(X);
X = Deque; Enque(X);
Print;

$12345$
$23451$
$34512$
$45123$
$51234$

prints $5$

$12345$
$23451$
$34512$
$45123$

prints $4$

$51234$
$12345$
$23451$
$34512$

prints $3$

$45123$
$51234$
$12345$
$23451$

prints $2$

$34521$
$45123$
$51234$
$12345$

prints $1$

Hence, the number of statements in the program = $45$

When we perform X = Deque followed by Enque(X), the elements at the head are moved to the tail. When these two statements are repeated for $n-1$ times the last element will be moved to the head position. Now when $\bf{print}$ statement is called it will print the current head element of the list (which was the last element, previously)

So total instructions needed to move the last element to the head position and print it are: $2(n-1)+1$.

So, finally if the code or the above block of $2(n-1) + 1$ is repeated n times then we will get the above queue in the reverse order.

So total statements required = $\bf{n(2n-1)}$

edited by
Let queue contains elements (1,2,3,4,5) in order, with 1 being the head. Therefore the below sequence of instructions will be displayed whenever the state of the queue changes.

Initial queue  # 12345
X = Deque; Enque(X); # 23451
X = Deque; Enque(X); # 34512
X = Deque; Enque(X); # 45123
X = Deque; Enque(X); # 51234
Print; Deque; # prints 5, queue now is 1234

X = Deque; Enque(X); # 2341
X = Deque; Enque(X); # 3412
X = Deque; Enque(X); # 4123
Print; Deque; # print 4, queue now is 123

X = Deque; Enque(X); # 231
X = Deque; Enque(X); # 312
Print; Deque; # print 3, queue now is 12

X = Deque; Enque(X); # 21
Print; Deque; # print 2, queue now is 1

Print; # print 1

Hence, the number of statements in the program = 29

This is a superior solution compared to the one with 45 steps. The saving comes from the fact that you don't need to preserve the element you just printed.

So total statements required is:
$\sum\limits_{i=1}^n 2i - 1$

## Related questions

1 vote
1
150 views
Consider the following non-deterministic finite automata(NFA) $A_{1}$ and $A_{2}:$ Give an example of a word which is accepted by both $A_{1}$ and $A_{2}.$ Give an example of a word which is accepted by $A_{1},$ but not by $A_{2}.$ Draw the deterministic finite automaton(DFA) equivalent to $A_{1}.$
Let $G$ be a simple graph on $n$ vertices. Prove that if $G$ has more than $\binom{n-1}{2}$ edges then $G$ is connected. For every $n>2$, find a graph $G_{n}$ which has exactly $n$ vertices and $\binom{n-1}{2}$ edges, and is not connected.
You are given a sorted array of $n$ elements which has been circularly shifted. For example, $\{35,42,5,12,23,26\}$ is a sorted array that has been circularly shifted by $2$ positions. Give an $O(\log n)$ time algorithm to find the largest element in a circularly shifted array. (The number of positions through which it has been shifted is unknown to you.)