1. Stacks and queues are dynamic sets in which the element removed from the set by the DELETE operation is prespecified.




2. In a stack, the element deleted from the set is the one most recently inserted: the stack implements a last-in, first-out, or LIFO, policy




3. Queue, the element deleted is always the one that has been in the set for the longest time: the queue implements a first-in, first-out, or FIFO, policy.

Stacks

1. The INSERT operation on a stack is often called PUSH, and the DELETE operation, which does not take an element argument, is often called POP.




2. The stack consists of elements S[1...S.top], where S[1] is the element at the bottom of the stack and S[S.top] is the element at the top.




3. When S.top = 0, the stack contains no elements and is empty. If we attempt to pop an empty stack, we say the stack underflows, which is normally an error. If S.top exceeds n, the stack overflows. Each of the three stack operations below takes O(1) time.

Stacks Operations - Pseudocode

1. STACK-EMPTY(S)

2. if S.top == 0

3.     return true

4. else return false

1. PUSH(S,x)

2. S.top = S.top + 1

3. S[S.top] = x

1. POP(S)

2. if STACK-EMPTY(S)

3.     error “underflow”

4. else S.top = S.top - 1

5.     return S[S.top + 1]

1. INSERT operation on a queue ENQUEUE, and we call the DELETE operation DEQUEUE; like the stack operation POP, DEQUEUE takes no element argument.




2. The queue has an attribute Q.head that indexes, or points to, its head. The attribute Q.tail indexes the next location at which a newly arriving element will be inserted into the queue.




3. The elements in the queue reside in locations Q.head, Q.head + 1, ... , Q.tail - 1, where we “wrap around” in the sense that location 1 immediately follows location n in a circular order. When Q.head = Q.tail, the queue is empty.




4. Initially, we have Q.head = Q.tail = 1. If we attempt to dequeue an element from an empty queue, the queue underflows. When Q.head = Q.tail + 1, the queue is full, and if we attempt to enqueue an element, then the queue overflows.

Queue Operations - Pseudocode

1. ENQUEUE(Q,x)

2. Q[Q.tail] = x

3. if Q.tail == Q.length

4.    Q.tail = 1

5. else Q.tail = Q.tail + 1

1. DEQUEUE(Q)

2. x = Q[Q.head]

3. if Q.head == Q.length

4.    Q.head = 1

5. else Q.head = Q.head + 1

6. return x

Q. Illustrate the result of each operation in the sequence PUSH(S,4),PUSH(S,1),PUSH(S,3),POP(S),PUSH(S,8),and POP(S) on an initially empty stack S stored in array S[1..6].

Q. Explain how to implement two stacks in one array A[1 .. n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The PUSH and POP operations should run in O(1) time.

We will call the stacks T and R. Initially, set T.top = 0 and R.top = n + 1. Essentially, stack T uses the first part of the array and stack R uses the last part of the array. In stack T, the top is the rightmost element of T. In stack R, the top is the leftmost element of R.

1. Algorithm 1: PUSH(S,x)

2. if S == T then

3.    if T.top + 1 == R.top then

4.        error "overflow"

5.    else

6.       T.top = T.top + 1

7.       T[T.top] = x

8.    end if

9. end if

10. if S == R then

11.    if R.top - 1 == T.top then

12.       error "overflow"

13.    else

14.       R.top = R.top - 1

15.       T[T.top] = x

16.    end if

17. end if

1. Algorithm 2: POP(S)

2. if S == T then

3.    if T.top == 0 then

4.       error "underflow"

5.    else

6.       T.top = T.top - 1

7.       return T[T.top + 1]

8.    end if

9. end if

10. if S == R then

11.    if R.top == n + 1 then

12.       error "underflow"

13.    else

14.       R.top = R.top + 1

15.       return R[R.top - 1]

16.    end if

17. end if

Q. Whereas a stack allows insertion and deletion of elements at only one end, and a queue allows insertion at one end and deletion at the other end, a deque (doubleended queue) allows insertion and deletion at both ends. Write four O(1) time procedures to insert elements into and delete elements from both ends of a deque implemented by an array.>

1. Algorithm 4: DEQUEUE
   

2. if Q.tail == Q.head then

3.    error "underflow"

4. end if

5. x = Q[Q.head]

6. if Q.head == Q.length then

7.    Q.head = 1
   

8. else

9.    Q.head = Q.head + 1
   

10. end if
    

11. return x

1. Algorithm 5: HEAD-ENQUEUE(Q,x)

2. Q[Q.head] = x

3. if Q.head == 1 then

4.    Q.head = Q.length

5. else

6.    Q.head = Q.head - 1

7. end if

1. Algorithm 6: TAIL-ENQUEUE(Q,x)

2. Q[Q.tail] = x

3. if Q.tail == Q.length then

4.    Q.tail = 1

5. else

6. Q.tail = Q.tail + 1

7. end if

1. Algorithm 7: HEAD-DEQUEUE(Q,x)

2. x = Q[Q.head]

3. if Q.head == Q.length then

4.    Q.head = 1

5. else

6.    Q.head = Q.head + 1

7. end if

1. Algorithm 8: TAIL-DEQUEUE(Q,x)

2. x = Q[Q.tail]

3. if Q.tail == 1 then

4.    Q.tail = Q.length

5. else

6.    Q.tail = Q.tail - 1

7. end if

1. A linked list is a data structure in which the objects are arranged in a linear order. Unlike an array, however, in which the linear order is determined by the array indices, the order in a linked list is determined by a pointer in each object.




2. Each element of a doubly linked list L is an object with an attribute key and two other pointer attributes: next and prev. The object may also contain other satellite data. Given an element x in the list, x.next points to its successor in the linked list, and x.prev points to its predecessor. If x.prev = NIL, the element x has no predecessor and is therefore the first element, or head, of the list. If x.next = NIL, the element x has no successor and is therefore the last element, or tail, of the list. An attribute L.head points to the first element of the list. If L.head = NIL, the list is empty.

Linked List Operations - Pseudocode

1. LIST-SEARCH(L,k)

2. x = L.head

3. while x ≠ NIL and x.key ≠ k

4.     x = x.next

5. return x

To search a list of n objects, the LIST-SEARCH procedure takes Θ(n) time in the worst case, since it may have to search the entire list.

1. Algorithm 2: LIST-INSERT(L,x)

2. x.next = L.head

3. if L.head ≠ NIL

4.    L.head.prev = x

5. L.head = x

6. x.prev = NIL

The running time for LIST-INSERT on a list of n elements is O(1).

1. Algorithm 3: LIST-DELETE(L,x)

2. if x.prev ≠ NIL

3.     x.prev.next = x.next

4. else L.head = x.next

5. if x.next ≠ NIL

6.     x.next.prev = x.prev

LIST-DELETE runs in O(1) time, but if we wish to delete an element with a given key, Θ(n) time is required in the worst case because we must first call LIST-SEARCH to find the element.

Q. 5 The given diagram shows the fowchart for a recursive function A(n). Assume that all statements, except for the recursive calls, have O(1) time complexity. If the worst case time complexity of this function is O(n^α), then the least possible value (accurate up to two decimal positions) of α is .
Flowchart for Recursive Function A(n)
(GATE 2016 SET B)

Ans . 2.32

Solution steps: In worst case, least possible value of α from the flowchart can be given as:
T(n) = 5T(n/2) + c, which evalutes to (By Master Method)
T(n) = log₂5 T(n) = 2.32 that is, α = 2.32

Q. 6 N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed. An algorithm performs the following operations on the list in this order: θ(N) delete, O(log N) insert, O(log N) find, and θ(N) decrease-key. What is the time complexity of all these operations put together? (GATE 2016 SET B)

1. O(log₂N)




2. O(N)




3. O(N²)




4. θ(N ²logN).

Ans . C

Solution steps: The time complexity of decrease-key operation is θ(1) since we have the pointer to the record where we have to perform the operation. However, we must keep the doubly linked list sorted and after the decrease-key operation we need to find the new location of the key. This step will take θ(N) time and since there are θ(N) decrease-key operations, the time complexity becomes O(N²).

Q.1 A queue is implemented using an array such that Enqueue and Dequeue operations are performed effciently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)? (GATE 2016 SET A)

1. Both operations can be performed in O(1) time




2. At most one operation can be performed in O(1) time but the worst case time for the other operation will be Ω(n)




3. The worst case time complexity for both operations will be Ω(n)




4. Worst case time complexity for both operations will be Ω(logn)

Ans : (A)

Solution steps:

1. In a Queue, ENQUEUE and DEQUEUE operations are performed at rear end and front end of Queue respectively with O(1) time.

Q. Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter
\(MultiDequeue(Q)\{ \)
\(m = k \)
\(while(Q \ is \ not \ empty) and ( m > 0) \{ \)
\(Dequeue (Q) \)
\(m = m - 1 \)
\(\} \)
\(\}\)
What is the worst case time complexity of a sequence of n queue operations on an initially empty queue? (GATE 2013 SET D)

1. \(\theta(n)\)




2. \(\theta(n + k)\)




3. \(\theta(n \times k)\)




4. \(\theta(n^2)\)

Ans . 1

Initially the queue is empty and we have to perform n operations.

1. One option is to perform all Enqueue operations i.e. n Enqueue operations. Complexity will be \( \theta(n)\).

2. We can perform a mix of Enqueue and Dequeue operations. It can be Enqueue for first n/2 times and then Dequeue for next n/2, or Enqueue and Dequeue alternately, or any permutation of Enqueues and Dequeues totaling n times. Complexity will be \( \theta(n)\).

3. We can perform Enqueues and MultiDequeues. A general pattern could be as follows:
   Enqueue Enqueue......(ktimes) MultiDequeue Enqueue Enqueue......(ktimes) MultiDequeue Up to total n
   .... k items enqueued .... k items deleted .... k items enqueued .... k items deleted .... and so on.
   The number of times this k-Enqueues, MutiDequeue cycle is performed = \(\frac{n}{k + 1}\) So,
   Complexity will be (k times Enqueue + 1 MultiDequeue) \(\times \frac{n}{k + 1} \)
   Which is \(\theta(2k \times \frac{n}{k+1}) = \theta(n) \)

4. We can just perform n MultiDequeues (or n Dequeues for that matter): Each time the while condition is false (empty queue), condition is checked just once for each of the n operations. So \(\theta(n)\)

Q.Consider a complete binary tree where the left and the right subtrees of the root are max-heaps. The lower bound for the number of operations to convert the tree to a heap is (GATE 2015 SET B)

1. O(logn)




2. O(n)




3. O(nlogn)




4. O(n2)

Ans . A

Solution:

This problem can be solved by using max-heapify function. Time complexity of max-heapify is O(Log n) as it recurses at most through height of heap.

Q.An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is (GATE 2015 SET B)

1. T(nlogn)




2. T(n)




3. T(logn)




4. T(1)

Ans . D

Solution:

We only need to consider any 3 elements and compare them. So the number of comparisons is constants, that makes time complexity as T(1)
we need to return any element that is neither maximum not minimum.
Let us take an array {10, 20, 15, 7, 90}. Output can be 10 or 15 or 20
Pick any three elements from given liar. Let the three elements be 10, 20 and 7.
Using 3 comparisons, we can find that the middle element is 10.

Q.A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is(GATE 2012)

1. Θ(n log n)




2. Θ\((n^2log n)\)




3. Θ\((n^2+log n)\)




4. Θ\((n^2)\)

Ans . 2

The height of the recursion tree using merge sort is logn and n2 comparisons are done at each level, where at most n pairs of strings are compared at each level and n comparisons are required to compare any two strings, So the worst case running time is O \((n^2 logn)\)

Q. Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are (GATE 2012)

1. full: (REAR+1) mod n==FRONT empty: REAR ==FRONT




2. full:(REAR+1)mod n==FRONT empty: (FRONT+1)mod n==REAR




3. full: REAR==FRONT empty: (REAR+1) mod n ==FRONT




4. full:(FRONT+1)mod n==REAR empty: REAR ==FRONT

Ans . 1

The counter example for the condition full : REAR = FRONT is
Initially when the Queue is empty REAR=FRONT=0 by which the above full condition is satisfied which is false

The counter example for the condition full : (FRONT+1)mod n =REAR is Initially when the Queue is empty REAR=FRONT=0 and let n=3, so after inserting one element REAR=1 and FRONT=0, at this point the condition full above is satisfied, but still there is place for one more element in Queue, so this condition is also false

The counter example for the condition empty : (REAR+1)mod n = FRONT is

Initially when the Queue is empty REAR=FRONT=0 and let n=2, so after inserting one element REAR=1 and FRONT=0, at this point the condition empty above is satisfied, but the queue of capacity n-1 is full here

The counter example for the condition empty : (FRONT+1)mod n =REAR is

Initially when the Queue is empty REAR=FRONT=0 and let n=2, so after inserting one element REAR=1 and FRONT=0, at this point the condition empty above is satisfied, but the queue of capacity n-1 is full here

Previous

Next