Question

General Instructions In this task, answer all the following questions and complement each answer with a detailed explanation 1. Design a 0(n log n)-time algorithm that, given a set S of n integer numbers and another integer x determines whether or not there exist two elements in S whose sum is exactly x 2. A Stack data structure provides Push and Pop, the two operations to write and read data, respectively. Extend this data structure so that, in addition to these two operations, it also provides the Min operation to return the smallest element of the stack. Remember that the new data structure must operate in a constant 0(1) time for all three aforementioned operations.

Answer 1

Q1.) Algorithm for the first question :

Sum_in_set(S[],n,x)

1. Sort the array in increasing order. (sorting method should be either merge sort or heap sort - for n.logn time complexity)

2. Initialize two variables with the leftmost and rightmost index.

Suppose l and r are two variables. Then l=0 and r=n-1.

3.While l<r :

a) If (S[l] + S[r] < x ) then l++.

b) else If (S[l] + S[r] ==x) return True.

c) else r--.

4. If no such pair found ,return False.

example : let set be S={2,9,4,5,3}. Sorted set={2,3,4,5,9} and sum to be find be 9.

initialize l=0, r=4

S[l]+S[r] i.e. 2+9 = 11 > 9 Therefore decrement r. Now r=3.

S[l]+S[r] i.e. 2+5 = 7 <9 Therefore increment l .Now l=1.

S[l]+S[r] i.e. 3+5 = 8<9 Therefore increment l. Now l=2.

S[l]+S[r] i.e. 4+5=9 .Found...returns True.

-------------------------------------------------------------------------------------------------------------------------------------------------

Q.2) To do the stack operations (push, pop, min) in a constant O(1) time, we have to implement it using two stacks - actual and auxiliary stack.

The top element in the auxiliary stack will always be the minimum element.

Push (int x) :

1. If x is the first element, push it in actual as well as auxiliary stack.

2. Else, push x to the actual stack.

3. Compare x with the top element of the auxiliary stack. Let the top element in auxiliary stack be y. If x < = y, then push x to auxiliary stack. // the = sign will duplicate the value in auxiliary as it will be helpful during pop operation in case two elements repeat.

Pop () :

1. Pop the top element of the actual stack

2. If the top element of the actual stack is equal to the top element of the auxiliary stack, pop the top element of the auxiliary stack. // to maintain auxiliary stack so that it always has top as minimum element of actual stack

int Min() :

1. Return the top element of the auxiliary stack.

Example :

When we push 9,   Actual : 9 <-top Auxiliary: 9 <-top

When we push 10, Actual : 9 10 <-top Auxiliary: 9 <-top

When we push 2, Actual : 9 10 2 <-top Auxiliary: 9 2 <-top

Hence, top in the auxiliary always point to the minimum element.

------------------------------------------------------------------------------------------------------------------------------------------------------------

If you find anything wrong or have any doubt, please ask in the comment section.