DSA Subjective question for competitive exam(1)

Q1.Design an algorithm to compute a power n where n is positive integer using divide and conquer technique.

if you want to compute an the algorithm is simple 

Log power(int a, int b)
{
long product=1,i;
for(i=1;i<=n;i++)
product=product*a;
return prod;
}

But the above function will take o(n) time.write divide and conquer which takes o(log(n)) time to compute a power n.
Divide and conquer approach
if we use divide and conquer approach the time complexity can be reduced to o(lo(n)).The divide and conquer approach square a each time rather than multiplying with a itself.

Log power(int a, int n)
{
if(n==0)
return 1;
if(n%2==0)
power(a,n/2)*power(a,n/2);
else
return a*power(a,n/2)*power(a,n/2);
}

Q2.give postfix expression (9-5)+7

Add left and right parenthese in the expression
((9-5)+7)

Symbol               Stack               Postfix Expression
(                     (
(                     ( (
9                      ((                   9
-                      ((-                  9
5                      ((-                  95
)                     (                     95-
+                       (+                  95-
7                      (+                   95-7
)                                           95-7+


Stack is empty so Postfix expression is 95-7+
Rule to convert infix expression to postfix
First add parentheses left and right of the expression.
if parenthese and operator occured push in stack.
If operand occure add in postfix expression.
if right parenthesis occured pop all the element from the stack and add in postfix expression.
             

Q3.Consider array of 10 integer 5,3,8,9,1,7,0,2,6,4 using quick sort algorithm using 5 as pivot value write down the resulting array after 1st iteration possible.

5    3    8  9  1  7  0   2  6   4
from left hand side pointer p that point to element that is greater than pivot which is p=8 and from right hand side q that point the element that is less that pivot q=4
interchange p and q then array element are
5   3   4   9   1    7   0    2    6   8 

now p=9(which is greater than pivot from left side)   and q=2(which is less than pivot from right side)
Interchange p and q then array element are

5   3   4   2   1   7    0   9    6    8 
Now p=7 and q=0 interchange

5   3    4   2    1   0   7     9   6    8 
now p=7 and q=0
p and q cross each other so q is replaced with pivot

0     3     4   2    1    5     7    9    6    8    


now left side element which is less than pivot that is 5 and right side element that is greater than pivot.

Q4.Determine running time of linear search in average and worst case.

Searching is the process of finding some particular element in the list.If the element is present in the list then the process is called successful and the process returns the location of that element otherwise the seach is unsuccessful.
Time complexity of linear search
Best case complexity
In linear search best case occurs when the element we are finding is at the first position at the array.The besr case time complexity of linear search is o(1).
Average case complexity
Average case complexity of linear search is o(n).
Worst case
When the element we are looking is present at the end of the array.The worst case in linear search could be when the target element is not present in the given array and we have to traverse the entire array.The worst case time complexity of linear search is o(n).  

Q5.Evaluate expression (2+3)*(5+4)

Add left and right parenthese in the expression
((2+3)*(5+4))

Symbol               Stack               Postfix Expression
(                      (                 
(                     ((
2                      ((                   2
+                      ((+                   2
3                      ((-                  23
)                     (                     23+
*                       (*                  23+
(                       (*(                 23+
5                       (*(                 23+5
+                       (*(+                23+5
4                       (*(+                 23+54
)                       (*                   23+54+
)                                            23+54+*                   

Stack is empty so Postfix expression is 23+54+*
Rule to convert infix expression to postfix
First add parentheses left and right of the expression.
if parenthese and operator occured push in stack.
If operand occure add in postfix expression.
if right parenthesis occured pop all the element from the stack and add in postfix expression.

Now solve postfix expression
postfix expression 23+54+*)

Scanned symbol                    Stack

2                                 2
3                                 23
+                                 5
5                                 55
4                                 554
+                                 59
*                                 45
)                                 45

result=45
Rule to solve postfix expression
add right parentheses end of the expression.
if operand occure push in stack.
if operator occure pop two operand from the stack and apply operation.               
if right parenthesis occure than end of expression.