Monday, 23 March 2015

PROPERTIES OF BINARY TREES

PROPERTIES OF BINARY TREES

There are some basic properties of binary trees. It is better to know all of them and how to apply.For easier understanding I am giving it in a tabular form.

1. Maximum number of nodes on any level i is 2i
2. Maximum number of nodes possible in a binary tree of height h is 2h-1
3. Minimum number of nodes possible in a binary tree of height h is equal to h
4. If a binary tree contains n nodes, then its maximum height possible is n
5. If a binary tree contains n nodes, then its minimum height possible is log2(n+1)
6. In a non empty binary tree, if n is the total number of nodes and e is the total number of edges, then e=n-1
7. In a full binary tree of height k, there are 2k-1 internal nodes
8. A strictly binary tree with n leaf nodes always has 2n - 1 nodes

JUNE 2007 - PAPER II Q.No 3


The maximum number of nodes in a binary tree of depth 10 is :
(A). 1024
(B). 210-1
(C). 1000
(D). None of the above

Ans:- B

Explanation:-
According to property 2, the maximum number of nodes in a binary tree of height or depth h is 2h-1

DECEMBER 2007 - PAPER II Q.No 23


The height of a binary tree with 'n' nodes in the worst case is

(A). 0(log n)
(B). O(n)
(C). Ω(n log n)
(D). Ω(n2)

Ans:- B

Explanation:-
Big omega notation is used for representing the best case. Big oh notation is used for representing the worst case. It is a measure of the longest amount of time it could possibly take for any algorithm to complete. Since we are representing the height of a binary tree, it would be the maximum height possible in a tree with 'n' nodes and it is O(n). So, the correct answer is B.

JUNE 2009 - PAPER II Q.No. 27


In a full binary tree of height k, there are ____________internal nodes.

(A). 2k-1
(B). 2k-1
(C). 2k
(D). 2k+1

Ans:-A

Explanation:-
Refer to the following diagram to understand the explanation. A full binary tree is one which has all the levels have maximum number of nodes in a tree.

DECEMBER 2009 - PAPER II Q.No 21

If the number of leaves in a strictly binary tree is an odd number, then what can you say with full conviction about total number of nodes in the tree?.
(A). It is an odd number.
(B). It is an even number.
(C). It cannot be equal to the number of leaves
(D). It is always greater than twice the number of leaves

Ans:-A

Explanation:-
A binary tree is a strictly binary tree if each node in the tree is either a leaf node or has exactly two children. There is no node with one child. According to its property, a strictly binary tree with n leaf nodes always has 2n-1 nodes. Let us consider n to be an odd number and give it a value of 3. So, the number of nodes in the tree would be 2n - 1 which is 2 X 3 -1 = 5. So that is also an odd number. So, the answer is A.

JUNE 2010 - PAPER II Q.No 23

In a complete binary tree of n nodes, how far are the two most distant nodes?.Assume each edge in the path count as 1.
(A). About log2n
(B). About 2log2n
(C). About nlog2n
(D). About 2n

Ans:-A

Explanation:-
The height h of a complete binary tree with n nodes is at the most O(log2n).

DECEMBER 2011 - PAPER II Q.No. 50

The number of nodes in a complete binary tree of height h (with roots at level 0) is equal to

(A) 20+21+......+2h
(B) 20+21+......+2h-1
(C) 20+21+......+2h+1
(D) 21+......+2h+1

Ans:-A

Explanation:-
Count the number of nodes in each level, starting with the root, assuming that each level has the maximum number of nodes.
n=1+2+4+....2h-1+2h

JUNE 2012 PAPER III Q.No 36

Already discussed in JUNE 2012 PAPER III solution...

Wednesday, 11 March 2015

CONVERSION OF INFIX EXPRESSION TO POSTFIX EXPRESSION

The conventional method of representing an arithmetic expression is known as infix because the operand is placed in between the operands. If the operator is placed before the operands then this notation is called prefix or Polish notation. If the operator is placed after the operand then this notation is called postfix or reverse polish notation. So now we have three ways to represent an arithmetic expression.

Infix:   A+B

Prefix:   +AB

Postfix:   AB+

Now, let us see how to convert an infix expression to postfix expression. The rules of parenthesis and precedence would be followed in the following way. If there are parenthesis in the expression, then the portion inside the parenthesis will be converted first. After this the operations are converted according to their precedence. (* and / first, followed by + and -). If there are operators of equal precedence then the operator which is on the left is converted first. In order to understand this with an example, let us solve an example from June 2014, Paper III, Question No. 41.

JUNE 2014 - PAPER III - Q.No 41

41. The reverse polish notation equivalent to the infix expression

((A + B) * C + D) / (E + F + G)

(A) A B + C * D + E F + G + /

(B) A B + C D * + E F + G + /

(C) A B + C * D + E F G + +/

(D) A B + C * D + E + F G + /

Ans:-A

Explanation:-

First, always the expression given within parenthesis is converted first. Since there are 2 expressions with the parenthesis, I am going with the expression (E + F + G) first, although the order does not matter.

In the expression (E + F + G), there are 3 operands E,F and G and two operators, both being +. Since both the operators are the same, the expression is going to be evaluated from left to right. So E + F is considered first and converted into postfix form which is EF+. So, the expression becomes,

( ( A + B ) * C + D) / ([E F +] + G)

Any expression converted into postfix form is going to be written in square brackets.

( ( A + B ) * C + D) / [ E F + G + ]
. Here EF+ is one operand, G is another operand and + is the operator.

The next expression to be converted into postfix is ( A + B).

( [ A B + ] * C + D) / [ E F + G + ]

Now, the expression which is enclosed in parenthesis is evaluated and so, we get

( [ [ A B + ] C * ] + D) / [ E F + G + ]

[ A B + C * D + ] / [ E F + G + ]

[ A B + C * D + ] [ E F + G + ] /

So, the final postfix expression is A B + C * D + E F + G + /. This answer is available in option A. So option A is the correct answer.

Thursday, 26 February 2015

DECEMBER 2010 - QNo 24 & 25

This post is a request from one of my readers, who has requested for these particular two questions from December 2010 Question paper. Divya, hope I have answered your question.

24. Linear probing suffers from a problem known as

(A) Secondary clustering
(B) Primary clustering
(C) Both (A) and (B)
(D) None of these

Ans:-B
Explanation:-
Linear probing is a term associated with hashing. Linear probing is a collision resolving technique in hashing. It suffers from a problem known as primary clustering. Any chosen hash function should uniformly distribute the records across the given available address space but sometimes clusters appear. If linear probing is used, it might spend a lot of time probing within the cluster instead of searching in the subsequent available space. One more collision resolving technique is Quadratic probing. Again we might come across the same topic depending on the nature of question encountered in future.

25. Which of the following can be the sequence of nodes examined in binary search tree while searching for key 88 ?

(A) 90, 40, 65, 50, 88
(B) 90, 110, 80, 85, 88
(C) 190, 60, 90, 85, 88
(D) 65, 140, 80, 70, 88

Ans:-C
Explanation:-
In order to find a solution for a question like above, given the data draw a binary search tree for each one of the options. The first item is the root. Any value less than the root will form the left side of the tree and any value greater than the root will form the right side of the tree. When you draw such a tree, if you find no node has a left and right child then such a sequence would be valid. If you find that the tree has a left and right child for any node then that sequence is invalid. If you draw the tree for all the 4 options given in the question you will find that only option C does not have left and right child for any node. So option C is correct.

Monday, 26 January 2015

KNAPSACK PROBLEM

KNAPSACK PROBLEM

JUNE 2014 - PAPER III Q.No 62

62. Consider the fractional knapsack instance n=4, (p1,p2,p3,p4) = (10,10,12,18)
(w1,w2,w3,w4)=(2,4,6,9) and M=15. The maximum profit is given by,
(Assume p and w denotes profit and weights of objects respectively).
(A)40
(B)38
(C)32
(D)30

Ans:-B

Explanation:-
Knapsack problem can be solved either using Greedy approach or through Dynamic programming. I am going to be explaining using the former. It has been proved that for the knapsack problem using greedy method we always get the optimal solution provided the objects are arranged in decreasing order of pi/wi. So, before solving the problem, let us arrange all the objects in decreasing order of pi/wi.
Capacity of the knapsack M = 15
Number of objects = 4
Profits(p1,p2,p3,p4)=(10,10,12,18)
Weights(w1,w2,w3,w4)=(2,4,6,9)
To get the solution arrange objects in decreasing order of profit/weights as shown below.
p1/w1=10/2 =5

p2/w2=10/4=2.5

p3/w3=12/6=2

p4/w4=18/9=2

Arrange in decreasing order of pi/wi, we get

Object Weight Profit Pi/wi
1 2 10 5
2 4 10 2.5
3 6 12 2
4 9 18 2

The fractions of the objects selected and the profit we get can be computed as shown below:

Remaining Capacity Object selected Weight of the object Fraction of the object selected
15 1 2 1 full unit
15-2=13 2 4 1 full unit
13-4=9 3 6 1 full unit
9-6=3 4 9 3/9 or 1/3 fraction of unit


So, the solution vector will be=(1,1,1,1/3)
Profits=1 X 10 + 1 X 10 + 1 X 12 + 1/3 X 18
Profits=10+10+12+6
Profits=20+18
=38
So the correct answer will be 38. The maximum profit is given by option (B) which is 38.

Solve the following problem and see.

I. Obtain the optimal solution for the knapsack problem given the following: M=40,n=3, (p1,p2,p3)=(30,40,35) and (w1,w2,w3)=(20,25,10).

. The answer for the above problem is 82.5
Check it by working out.

Wednesday, 14 January 2015

TYPES OF GRAMMAR

TYPES OF GRAMMAR

A grammar G is 4-tuple or quadruple G=(V,T,P,S) where
V is set of variables or non-terminals.
T is set of terminals.
P is set of productions.
S is the start symbol.
Each production is of the form α -> β where α is a non empty string of terminals and/or non-terminals and β is string of terminals and/or non-terminals including the null string. This grammar is also called as phase-structure grammar.

CHOMSKY HIERARCHY

Phase-structure grammars may be classified according to their productions. The following table would help you understand with the classifications.

S.no TYPE NAME PRODUCTION RULE RESTRICTION LANGUAGE GENERATED MACHINE WHICH RECOGNISES
1 Type 0 grammar Unrestricted grammar α -> β No restriction on length of α and β.α cannot be epsilon type o language or recursively enumerable language Turing machine
2 Type 1 grammar Context sensitive grammar α -> β Length of β must be atleast as much as the length of α Type 1 language or context sensitive language Linear Bounded automata
3 Type 2 grammar Context free grammar A->α The symbol epsilon can appear on the right side of any production. type 2 language or context free language Pushdown automaton
4 Type 3 grammar Regular grammar A->wB and/or A->w Regular language Finite state automaton

Following are the questions from previous NET exams on the above topic.

DECEMBER 2006
JUNE 2005
JUNE 2010
32. Which of the following is the most general phase-structure grammar?
A)Regular B)Context-sensitive
C)Context free
D)Syntax tree or D) None of these
Ans:-B
Explanation:- The above question has appeared in more than 3 previous papers. The right answer is Context-sensitive grammar.

DECEMBER 2007
3) A context free grammar is :
A)type 0
B)type 1
C)type 2
Ans:- C

DECEMBER 2009
34). Context free grammar(CFG) can be recognised by
A)Finite state automaton
B)2-way linear bounded automata
C)Push down automata
D)Both B & C
Ans:- C

JUNE 2013 - PAPER III - QNo. 39
Match the following :
a. Context sensitive language     i. Deterministic finite automation
b. Regular grammar      ii. Recursive enumerable
c. Context free grammar     iii. Recursive language
d. Unrestricted grammar     iv. Pushdown automation

Ans:-

Unrestricted grammar is Recursive enumerable which is also type 0.
Context free grammar is recognised by pushdown automation
Regular grammar is recognised by Deterministic finite automation
Context sensitive language would be recursive language which is also type 1 grammar.
Choose the appropriate option by looking at the answer.

Wednesday, 7 January 2015

HOW TO KNOW THE DAY GIVEN ANY DATE

HOW TO KNOW THE DAY GIVEN ANY DATE

This will be useful for Paper I - General Aptitude. These kind of questions are common in many competitive exams. Given a date, we are asked to give the day corresponding to that date. The following steps have to be followed for doing it. Before that, we should remember some values. They are,

CENTURY CODE

  • 1700 - 4
  • 1800 - 2
  • 1900 - 0
  • 2000 - 6
  • 2100 - 4
  • 2200 - 2
  • 2300 - 0

MONTH CODE

  • JANUARY - 1
  • FEBRUARY - 4
  • MARCH - 4
  • APRIL - 0
  • MAY - 2
  • JUNE - 5
  • JULY - 0
  • AUGUST - 3
  • SEPTEMBER - 6
  • OCTOBER - 1
  • NOVEMBER - 4
  • DECEMBER - 6

DAY CODE

  • SUNDAY - 1
  • MONDAY - 2
  • TUESDAY - 3
  • WEDNESDAY - 4
  • THURSDAY - 5
  • FRIDAY - 6
  • SATURDAY - 0

Let us take an example. The date considered is January 27,2008.
1. Take the last two digits of the year and divide the number by 4, drop the remainder.

     8 / 4 = 2

2. Add the day of the month to that number.

     27 + 2 = 29

3. Add month code to the answer. Refer above for the month code.

     29 + 1 = 30

4. Add century code to it. Refer above for the century code.

     30 + 6 = 36

5. Take the result. Add last 2 digits of the year.

     36 + 8 = 44

6. Divide the number by 7. Take only the remainder.

     44 / 7 = Quotient is 6, Remainder is 2

7. Refer to the day code above. Since the remainder is 2, the day is MONDAY

So, JANUARY 27,2008 is a MONDAY.

Check it with any date of your choice!!!!!.

Tuesday, 6 January 2015

OPERATION ON FUZZY SETS

FUNDAMENTALS OF OPERATIONS ON FUZZY SETS

There have been quite a few questions on operations on fuzzy sets in every exam of NET(in PAPER III). So I have explained the theory behind them and how to solve it. Hope it is useful.

1. How to denote a fuzzy set?
IF X is the universe of discourse and x is a particular element of X, then a fuzzy set A defined on X may be written as a collection of ordered pairs:
A={(x,µA(A))}, x belongs to X
The pair (x, µA(A)) is called a singleton.
In crisp sets, a singleton is simply the element x by itself.
In fuzzysets, a singleton is composed of two terms: x and µA(x).
A singleton is also written as µA(x)/x. That is by putting the membership function first followed by the ‘/’symbol and is used to separate the function from x.
Singletons whose membership to a fuzzy set is 0 may be omitted.

2. Union of two fuzzy sets
µAUB(x) = µA(x) V µB(x) = max(µA(x), µB(x))

3. Intersection of two fuzzy sets
µA Intersection B(x) = µA(x) ^ µB(x) = min(µA(x), µB(x))

4. Complement of a fuzzy set
The complement of a fuzzy set A is a new fuzzy set A Complement, containing all the elements which are in the universe of discourse but not in A, with the membership function
Complement of µA(x) = 1 - µA(x)

5. Height of a fuzzy set
The height of a fuzzy set is the highest membership value of the membership function:
Height(A) = max µA(xi)
A fuzzy set with height 1 is called a normal fuzzy set.
In contrast, a fuzzy set whose height is less than 1 is called a subnormal fuzzy set.

6. α-cut of a fuzzy set
α-cut of a fuzzy set A denoted as Aα, is the crisp set comprised of the elements x of a universe of discourse X for which the membership function of A is greater than or equal to α.

Solved problems from various NET papers.

JUNE 2012 – PAPER III Q.No 6

6. If two fuzzy sets A and B are given with membership functions μA(x) = {0.2, 0.4, 0.8, 0.5, 0.1} μB(x) = {0.1, 0.3, 0.6, 0.3, 0.2} Then the value of μ ––– will be A∩B
(A) {0.9, 0.7, 0.4, 0.8, 0.9}
(B) {0.2, 0.4, 0.8, 0.5, 0.2}
(C) {0.1, 0.3, 0.6, 0.3, 0.1}
(D) {0.7, 0.3, 0.4, 0.2, 0.7}
Ans:-A
Explanation:- 
The fuzzy intersection of two fuzzy sets A and B on universe of discourse X: μA∩B(x) = min [μA(x), μB(x)] , where x∈X
But here in the question, they are asking for complement of A intersection B and so the answer would be 1-min[A(x),B(x)].
The minimum of 0.2 and 0.1 will be 0.1, and 1-0.1 will be 0.9
The second value is min(0.4,0.3)=0.3 and 1-0.3=0.7

The third value is min(0.8,0.6)=0.6 and 1-0.6=0.4

The fourth value is min(0.5,0.3)=0.3 and 1-0.3=0.7

The last value is min(0.1,0.2)=0.1 and 1-0.1=0.9

The only option which has got the values 0.9,0.7,0.4,0.7 and 0.9, although the fourth value is given as 0.8 instead of 0.7 is option A.
So the answer is option A.

DECEMBER 2012 – PAPER III Q.No 13

13. Consider a fuzzy set A defined on the interval x=[0,10] of integers by the membership function.
µA(x) = x / x+ 2
α cut corresponding to α = 0.5 will be
(A) { 0,1,2,3,4,5,6,7,8,9,10}
(B) {1,2,3,4,5,6,7,8,9,10}
(C) {2,3,4,5,6,7,8,9,10}
(D) { }
Ans:- C
Explanation:-
In the fundamentals, refer to the answer given for question no. 6 regarding α-cut.
α-cut of a fuzzy set A denoted as Aα, is the crisp set comprised of the elements x of a universe of discourse X for which the membership function of A is greater than or equal to α.
Given, x = In the range [0,10]
Membership function = x/x+2
Calculate the value of membership function for the interval from 0 to 10, substituting in the formula x/x+2.
µA(0) = 0 / 0+ 2 = 0

µA(1) = 1 / 1+ 2 = 0.33

µA(2) = 2 / 2+ 2 = 0.5

µA(3) = 3 / 3+ 2 = 0.6

µA(4) = 4 / 4+ 2 = 0.66

µA(5) = 5 / 5+ 2 = 0.71

µA(6) = 6 / 6+ 2 = 0.75

µA(7) = 7 / 7+ 2 = 0.77

µA(8) = 8 / 8+ 2 = 0.8

µA(9) = 9 / 9+ 2 = 0.81

µA(10) = 10 / 10+ 2 = 0.83

α= 0.5. We have to find the corresponding α-cut,

That will be a crisp set, having those values of x, for which the membership function is returning a value of 0.5 or above.

µA(2) = 0.5 and all the values of x above 2 is getting a value greater than 0.5. So the crisp set will contain the following values.

{ 2,3,4,5,6,7,8,9,10}.

So the correct answer is C.

DECEMBER 2013 – PAPER III Q.No 28

28. If A and B are two fuzzy sets with membership functions μA(x) = {0.2, 0.5, 0.6, 0.1, 0.9} μB(x) = {0.1, 0.5, 0.2, 0.7, 0.8} Then the value of μA ∩B

will be

(A) {0.2, 0.5, 0.6, 0.7, 0.9}

(B) {0.2, 0.5, 0.2, 0.1, 0.8}

(C) {0.1, 0.5, 0.6, 0.1, 0.8}

(D) {0.1, 0.5, 0.2, 0.1, 0.8}

Ans:-D

Explanation:-

Intersection of two fuzzy sets

µA ∩B (x) = µA(x) ^ µB(x) = min(µA(x), µB(x))

μA(x) = {0.2, 0.5, 0.6, 0.1, 0.9}

μB(x) = {0.1, 0.5, 0.2, 0.7, 0.8}

μA ∩B={0.1,0.5,0.2,0.1,0.8}

So, the correct answer is D.

29. The height h(A) of a fuzzy set A is defined as h(A) =sup A(x) where x belongs to A. Then the fuzzy set A is called normal when

(A)h(A)=0

(B)h(A)<0

(C)h(A)=1

(D)h(A)<1

Ans:- C

Explanation:-

Explanation:- The height of a fuzzy set is the highest membership value of the membership function: Height(A) = max µA(xi)

A fuzzy set with height 1 is called a normal fuzzy set.

In contrast, a fuzzy set whose height is less than 1 is called a subnormal fuzzy set. So, according to the above rule, the fuzzy set A is called normal when h(A)=1.

So, the correct answer is 1.

JUNE 2013 – PAPER III Q.No 74

74. If A and B are two fuzzy sets with membership functions μA(x) = {0.6, 0.5, 0.1, 0.7, 0.8} μB(x) = {0.9, 0.2, 0.6, 0.8, 0.5}

Then the value of μ Complement A∪B(x) will be

(A) {0.9, 0.5, 0.6, 0.8, 0.8}

(B) {0.6, 0.2, 0.1, 0.7, 0.5}

(C) {0.1, 0.5, 0.4, 0.2, 0.2}

(D){0.1,0.5,0.4,0.2,0.3}

Ans:- C

Union of two fuzzy sets

µAUB(x) = µA(x) V µB(x) = max(µA(x), µB(x))

μA(x) = {0.6, 0.5, 0.1, 0.7, 0.8}

μB(x) = {0.9, 0.2, 0.6, 0.8, 0.5}

µAUB(x) = {0.9,0.5,0.6,0.8,0.8}

Complement of µAUB(x)={0.1,0.5,0.4,0.2,0.2}

So, the correct answer is C.

JUNE 2014 – PAPER III Q.No 7,8 7. Given U = {1, 2, 3, 4, 5, 6, 7} A = {(3, 0.7), (5, 1), (6, 0.8)} then

~ A will be : (where ~ →complement)

(A) {(4, 0.7), (2, 1), (1, 0.8)}

(B) {(4, 0.3), (5, 0), (6, 0.2) }

(C) {(1, 1), (2, 1), (3, 0.3), (4, 1), (6, 0.2), (7, 1)}

(D) {(3, 0.3), (6.0.2)}

Ans:- C

Explanation:-

Complement of a fuzzy set

The complement of a fuzzy set A is a new fuzzy set A Complement, containing all the elements which are in the universe of discourse but not in A, with the membership function

Complement of µA(x) = 1 - µA(x)

Complement of a fuzzy set A is a new fuzzy set A complement. Since it is a fuzzy set, there will be two members in a singleton. The first member will be all the elements which are in the universe of discourse but not in A. The membership function will be 1- µA(x).

So, the complement of A will be

{(1,1),(2,1),(3,0.3),(4,1),(6,0.2),(7,1)}

The first is (1,1). The first 1 is in U but not in A, so it should be added in the complement. The second 1 is because the membership function is 1- µA(x). 1-0=1.

The same reason why you get (2,1).

The third one (3,0.3) because it is (3,1-0.7)=(3,0.3).

Same reason why you have (4,1) and (7,1).

(6,1-0.8)=(6,0.2).

The member (5,0) is not included because , a singleton whose membership to a fuzzy set is 0, can be excluded .

8. Consider a fuzzy set old as defined below

old={(20,0),(30,0.2),(40,0.4),(50,0.6),(60,0.8),(70,1),(80,1)}. Then the alpha-cut for alpha=0.4 for the set old will be (A){(40,0.3)}

(B){50,60,70,80}

(C){(20,0.1),(30,0.2)}

(D){(20,0),(30,0),(40,1),(50,1),(60,1),(70,1),(80,1)}

Ans:-D

Explanation:-

alpha-cut of a fuzzy set A will contain those elements where the membership function value is equal to or greater than alpha.

Here, alpha is given a value 0.4. Starting from (40,0.4) all the members have membership function equal or greater than 0.4. so, except

(20,0) and (30,0.2) all the menbers are included in the alpha-cut of the fuzzy set. The only option which has 40,50,60,70, and 80 included is option D. It has

(20,0) and (30,0) too. But it is already noted that any singleton where the membership function is 0 can be considered not included. So basically these two members are not part of the alpha-cut of the fuzzy set A. So the correct option is D.

DOWNLOAD THE ABOVE POST IN THIS LINK...

OPERATIONS ON FUZZY SETS