edited by
17,292 views
67 votes
67 votes

A function $f$ defined on stacks of integers satisfies the following properties. $f(∅) = 0$ and $f (push (S, i)) = max (f(S), 0) + i$ for all stacks $S$ and integers $i$. 

If a stack $S$ contains the integers $2, -3, 2, -1, 2$ in order from bottom to top, what is $f(S)$?

  1. $6$
  2. $4$
  3. $3$
  4. $2$
edited by

2 Answers

Best answer
104 votes
104 votes
  • $i:$ Element to be pushed
  • Initial State $ f( \emptyset ) = 0.$ For Empty Stack $f(S)$ is $0$
  • Then we push each element ($i$)one by one and calculate $f(s)$ for each insertion as given

$$f_{new}(S) = \max( f_{previous}(S)  , 0 ) + i $$ is the function to compute $f(S)$ for each insertions

  1. INSERT $2$ on to Stack
    $f_{previous}(S)  =  0$  [Stack was empty ]
    $i= 2$ (inserting element is i )
    $f_{new}(S) = \max( f_{previous}(S)  , 0 ) + i$
    $f_{new}(S) = \max(0,0) +2 = 2$
  2. INSERT $-3$ on to Stack
    $f_{previous}(S)  =  2$  [Stack was empty ]
    $i= -3$ (inserting element is i )
    $f_{new}(S) = \max( f_{previous}(S)  , 0 ) + i$
    $f_{new}(S) = \max(2,0) +-3 = -1$

Similarly,

  • i: The element to be pushed
  • S: Stack
  • Initially $f(S)=0.$

$$\begin{array}{|c|c|c|c|}\hline f(S)  &  \max(f(S),0) & \text{i}& f_{new}(S)= \max(f(S),0)+i\\\hline \text{0} & \text{0} & \text{2} & \text{2}\\\hline\text{2} & \text{2} & \text{-3} & \text{-1}\\\hline \text{-1} & \text{0} & \text{2} & \text{2}\\\hline \text{2} & \text{2} & \text{-1} & \text{1}\\\hline  \text{1} & \text{1} & \text{2} & \boxed{\text{3} } \\\hline   \end{array}$$ Thus, the answer is Option C.

The value of $f(S)$ after inserting all elements into stack is 3.

edited by
22 votes
22 votes
$2,-3,2,-1,2$

$F(\phi)$ = 0 and $F(push( S,i ))$ = $max(f(s),0) + i$;

initially, Stack is empty and For empty stack, $0$ is given

$push(S,i)$

$F(push(0,2)) = max( f( ∅) , 0) + 2 = max(0,0) + 2 = 2$  so $2$

$F(push(2,-3)) = max( 2 , 0) + (-3) = 2 -3 =  -1$

$F(push(-1,2)) = max( -1 , 0) + 2 = 0 + 2 = 2 ,f(s ) = 2$ now

$F(push(2,-1)) = max( 2 , 0) + (-1) = 2 - 1 = 1 so f(s )= 1$ now

$F(push(1,2)) = max( 1 , 0) + 2 = 1 + 2= 3$

so 3 $Option\space C$ is correct
edited by
Answer:

Related questions

27 votes
27 votes
4 answers
1
64 votes
64 votes
7 answers
3
Ishrat Jahan asked Nov 3, 2014
22,475 views
In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most $2$. If the height of the tree is $h 0$, then the m...
53 votes
53 votes
7 answers
4
Ishrat Jahan asked Nov 3, 2014
13,297 views
The numbers $1, 2, .\dots n$ are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the root contains $p$ nodes. The first number...