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

Sunday 4 January 2015

CYCLOMATIC COMPLEXITY - SOLVED PROBLEMS

Cyclomatic complexity is a software metric. It provides a quantitative measure of the logical complexity of a program.Cyclomatic complexity provides us with an upper bound for the number of tests that must be conducted to ensure that all statements have been executed at least once.

Cyclomatic complexity has a foundation in graph theory and is computed in one of three ways.
1. The number of regions correspond to the cyclomatic complexity.
2. Cyclomatic complexity V(G) for a flow graph G, is defined as,
V(G)=E-N+2

where E=Number of flow graph edges
N=Number of flow graph nodes
3.Cyclomatic complexity,V(G) for a flow graph G, is defined as,
V(G)=P+1
where P=Number of predicate nodes contained in flow graph G.

The above three formulas are very important and there are a lot of NET questions based on this topic. I am solving a few of them here.
DECEMBER 2013 - PAPER III Q.NO 4
4. Given a flow graph with 10 nodes, 13 edges and one connected components, the number of regions and the number of predicate(decision) nodes in the flow graph will be
A)4,5
B)5,4
C)3,1
D)13,8
Ans:-B
Explanation:-
N=10,E=13
V(G)=E-N+2
V(G)=13-10+2
=3+2=5
Therefore, No of regions = 5. (According to rule 1.)
According to rule 3, V(G)=P+1
V(G) refers to the cyclomatic complexity which is equal to the no of regions.
5=P+1
P=5-1=4
So, the number of predicate nodes in the flow graph is 4.
So, the number of regions and the number of predicate nodes in the flow graph will be 5,4
Therefore, the correct answer is B.

JUNE 2013 - PAPER II Q.No 5
5. Cyclomatic complexity of a flow graph G with n vertices and e edges is
A)V(G)=e+n-2
B)V(G)=e-n+2
C)V(G)=e+n+2
D)V(G)=e-n-2
Ans:-B
Explanation:-
According to rule 2, the formula for Cyclomatic Complexity V(G)=e-n+2 where e is no of edges, n is no of vertices.

JUNE 2012 - PAPER III Q.No 33
33. Which one of the following statements is incorrect ?
(A) The number of regions corresponds to the cyclomatic complexity.
(B) Cyclometric complexity for a flow graph G is V(G) = N – E + 2, where E is the number of edges and N is the number of nodes in the flow graph.
(C) Cyclometric complexity for a flow graph G is V(G) = E – N + 2, where E is the number of edges & N is the number of nodes in the flow graph.
(D) Cyclometric complexity for a flow graph G is V(G) = P + 1, where P is the number of predicate nodes contained in the flow graph G.
Ans:- B
Explanation:-
According to the formulas given in (1),(2) and (3), option B is incorrect, because V(G)=E-N+2 and not N-E+2.

DECEMBER 2011 - PAPER II Q.No 15
15. McCabe's cyclomatic metric V(G) of a graph with n vertices, e edges and p connected component is
A)e
B)n
C)e-n+p
D)e-n+2p
Ans:-C
Explanation:-
According to McCabe's cyclomatic metric of a graph V(G)=E-N+P where P refers to connected components.

JUNE 2006 - PAPER II Q.No 42
42. In Software Metrics, McCABE􏰂's cyclomatic number is given by following formula :
(A) c=e-n+2p
(B) c=e-n-2p
(C) c=e+n+2p
(D) c=e-n*2p
Ans:-A


I hope all of you can solve problems based on cyclomatic complexity of a graph, with confidence and ease, after going through the above article.

REFER TO MY OTHER POSTS ON SOFTWARE ENGINEERING

SOFTWARE ENGINEERING

SOFTWARE ENGINEERING - SOLVED PROBLEMS

Saturday 3 January 2015

SOFTWARE ENGINEERING - SOLVED PROBLEMS

SOFTWARE ENGINEERING PROBLEMS


JUNE 2014 – PAPER III

17. Assume that a program will experience 200 failures in infinite time. It has now experienced 100 failures. The initial failure intensity was 20 failures/CPU hr. Then the current failure intensity will be
(A) 5 failures/CPU hr
(B) 10 failures/CPU hr.
(C) 20 failures/CPU hr
(D) 40 failures /CPU hr

Ans:- B
Explanation:- The formula for Current Failure Intensity =
Initial Failure intensity X [ 1 – Experienced failures/Failures in infinite time ]
= 20 X [ 1 – 100/200 ]
=20 X (100/200)
=10 failures /CPU hr


18. Consider a project with the following functional units :
Number of user inputs = 50
Number of user outputs = 40
Number of user enquiries = 35
Number of user files = 06
Number of external interfaces = 04
Assuming all complexity adjustment factors and weighing factors as average, the function points for the project will be
(A)135
(B)722
(C)675
(D)672

Ans:-
Explanation:-

Measurement parameter Count Weighting Factor(Average) Total
Number of user inputs 50 4 =200
Number of user outputs 40 5 =200
Number of user enquiries 35 4 =140
Number of user files 6 10 =60
Number of external interfaces 4 7 =28

Functon point (FP) = count total X (0.65 + 0.01 X S(fi))
= 628 X (0.65 + .01 X 30)
= 596.6
There is no option like that given. So I am not choosing anything.


The weighting factors of Simple project are 3,4,3,7,5

The weighting factors of Complex project are 6,7,6,15,10

Formula for Function point (FP for Simple project)= count total X (0.65+0.01 X 22)

Formula for Function point (FP for Complex project)= count total X (0.65+0.01 X 44)



TRY OUT THE FOLLOWING PROBLEMS

1. Compute the function point value for a project with the following information domain characteristics
Number of user inputs : 23
Number of user output : 60
Number of user enquiries : 24
Number of files : 10
Number of external interface : 05
Assume that all complexity adjustment values are average.
Ans : - 591.85

2. Compute the function point value for a project with the following information domain characteristics.
Number of user inputs : 28
Number of user outputs : 50
Number of user enquiries : 42
Number of files : 07
Number of external interface : 03
Assume that all complexity adjustment values are simple.
Ans:- 412.38

Problems are taken from the book on Software Engineering by Bharat Bhushan Agarwal and Sumit Prakash Tayal

Friday 2 January 2015

ALL ABOUT NET

NET stands for National Eligibility Test. This is a test conducted by National Educational Testing Bureau of University Grants Commission to establish a minimum standard for Lecturers and Junior Research Fellowships for pursuing research. I think most of you know all about it. Why am I writing about all these basics now?. Because I want to ensure that all of you know how important this exam is. I know many success stories of people having passed this exam. There is no looking back for any one of them.

The first success story is that of my brother, who cleared his JRF way back in the 1990's. He not only went on to complete his Phd from IIT Madras, but he is also in a very senior position in a well known fortune 500 company. Not only that, many of the others, whom I know,who have cleared this test are in either government jobs or good positions, even if it is a private job. I feel it is easy to pass this exam if you write it immediately after finishing your masters. The theories and problems are easy to understand and apply, while you are fresh from all your studies. But still with little discipline, and some smart reading it is possible to crack this exam. This site will help you all in the smart reading part. Passing this exam is a prestige which no one can deny. Any one who has cleared NET is looked up in the work environment, and the opportunities they have are in abundance. Again why am I stressing about all this now is that, however the December 2014 exam was, everyone should look forward to the next one and try to crack it, the next time.

But, for that preparations have to start from right now. Not around April, May or June. I read in the paper, that this time, Paper I was quite tricky and tough. Normally the candidates writing NET do not focus much on cracking Paper I. They take it for granted. So I have decided to include tips for Paper I as well from now onwards. This place will be a one point reference for all information and guidance related to NET. I started this blog with the sole aim of reaching out to people who want to crack this exam. I found that there was no help online for understanding the solution in detail. That is why all the questions will have a detailed explanation as far as possible in this site. I aim to write, as regularly as I can. When I read your comments, on how useful a particular post or information was, that actually makes my day. So, ALL THE BEST to all of you out there. Do not rest, till you clear the test!!!.

For all other information, related to NET, click here...

About NET



SYLLABUS FOR NET



OLD QUESTION PAPERS



SCOPE OF NET/SLET