## ISRO-2017 December

Please wait while the activity loads.

If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

Question 1 |

Suppose A is a finite set with n elements. The number of elements and the rank of the largest equivalence relation on A is

{n,1} | |

{n, n} | |

{n ^{2}, 1} | |

{1, n ^{2}} |

Question 1 Explanation:

Let us assume a set with 4 elements

S={1,2,3,4}

→ If a set is said to be equivalence, then the set must be

i) Reflexive

ii) Symmetric

iii) Transitive

i) Reflexive Relation: A relation ‘R’ on a set ‘A’ is said to be reflexive if (xRx)∀x∈A.

A = {1,2,3}

R = {(1,1), (2,2), (3,3)}

R = {(1,1), (2,2)} It is false.

R = {(1,1), (2,2), (3,3), (1,2)}

ii) Symmetric Relation: A relation on a set A is said to be symmetric if (xRy). Then (yRx)∀x,y∈A i.e., if ordered pair (x,y)∈R. Then (y,x)∈R ∀x,y∈A.

A={1,2,3}

R1={(1,2), (2,1)}

R2={(1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2)}

Transitive Relation:

A relation ‘R’ on a set ‘A’ is said to be transitive if (xRy) and (yRz), then (xRz)∀(x,y,z∈A).

A={1,2,3}

R1={ }

R2={(1,1)}

R3={(1,2), (3,1)}

R4={(1,2), (2,1), (1,1)}

⇾ A={1,2,3,4}

Largest ordered set is

S×S={(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4),(4,1),(4,2),(4,3),(4,4)}

⇒ Total = 16 = 42 = n2

Smallest ordered set = {(1,1),(2,2),(3,3),(4,4)}

⇒ Total=4=n

Note: In question, they are clearly mentioned that Rank of an Equivalence relation is equal to the number of induced Equivalence classes. Since we have maximum number of ordered pairs(which are reflexive, symmetric and transitive ) in largest Equivalence relation, its rank is always 1.

S={1,2,3,4}

→ If a set is said to be equivalence, then the set must be

i) Reflexive

ii) Symmetric

iii) Transitive

i) Reflexive Relation: A relation ‘R’ on a set ‘A’ is said to be reflexive if (xRx)∀x∈A.

A = {1,2,3}

R = {(1,1), (2,2), (3,3)}

R = {(1,1), (2,2)} It is false.

R = {(1,1), (2,2), (3,3), (1,2)}

ii) Symmetric Relation: A relation on a set A is said to be symmetric if (xRy). Then (yRx)∀x,y∈A i.e., if ordered pair (x,y)∈R. Then (y,x)∈R ∀x,y∈A.

A={1,2,3}

R1={(1,2), (2,1)}

R2={(1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2)}

Transitive Relation:

A relation ‘R’ on a set ‘A’ is said to be transitive if (xRy) and (yRz), then (xRz)∀(x,y,z∈A).

A={1,2,3}

R1={ }

R2={(1,1)}

R3={(1,2), (3,1)}

R4={(1,2), (2,1), (1,1)}

⇾ A={1,2,3,4}

Largest ordered set is

S×S={(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4),(4,1),(4,2),(4,3),(4,4)}

⇒ Total = 16 = 42 = n2

Smallest ordered set = {(1,1),(2,2),(3,3),(4,4)}

⇒ Total=4=n

Note: In question, they are clearly mentioned that Rank of an Equivalence relation is equal to the number of induced Equivalence classes. Since we have maximum number of ordered pairs(which are reflexive, symmetric and transitive ) in largest Equivalence relation, its rank is always 1.

Question 2 |

Consider the set of integers I. Let D denote “divides with an integer quotient” (e.g. 4D8 but 4D7). Then D is

Reflexive, not symmetric, transitive | |

Not reflexive, not antisymmetric, transitive | |

Reflexive, antisymmetric, transitive | |

Not reflexive, not antisymmetric, not transitive |

Question 2 Explanation:

**Reflexive Relation:**

A relation ‘R’ on a set ‘A’ is said to be reflexive if (xRx)∀x∈A.

Example: 4 D 8, 4 D 12, 4 D16, 4 D20…….(Here, D means divide)

8 D 16, 8 D 24……….

In this example, we didn’t get 4D4. So, it is not reflexive.

**AntiSymmetric Relation:**

For all x ∈ I, R(x,y) and R(y,x) then x=y is antisymmetric. We can easily make a violation as R(-2,2) and R(2,-2) are not antisymmetric.

It is violating. So, not antisymmetric relation.

**Transitive relation:**

A relation ‘R’ on a set ‘A’ is said to be transitive if (xRy) and (yRz), then (xRz)∀(x,y,z∈A).

Example: 4D8, 4D12, 4D16, 4D20…….(Here, D means divide)

8D16, 8D24……….

{ 4D8, 8D16, 1D16}. So, it is satisfied.

Question 3 |

A bag contains 19 red balls and 19 black balls. Two balls are removed at a time repeatedly and discarded if they are of the same colour, but if they are different, black ball is discarded and red ball is returned to the bag. The probability that this process will terminate with one red ball is

1 | |

1/21 | |

0 | |

0.5 |

Question 3 Explanation:

Given data,

Step-1: Bag contains 19 Red(R) and 19 Blue(B) balls.

BB (or) RR happen we are discarded.

If we get BR (or) RB then B is discarded and R is returned.

Step-2: There are some conditions that,

→ If black balls will either come with black then both black balls are discarder.

→ If it will come with red then only black balls will be discarded.

→ Suppose 2 red balls will come together means we are discarding both red balls.

Step-3: As per the above constraints, total 19 Red balls it means odd number.

→ Among 19 only 18 will be discarded.

Step-3: Final content of bag at second last trail will be either R,B (or) R,R,R and finally in last

trail bag will left with one red ball in both the cases.

Step-1: Bag contains 19 Red(R) and 19 Blue(B) balls.

BB (or) RR happen we are discarded.

If we get BR (or) RB then B is discarded and R is returned.

Step-2: There are some conditions that,

→ If black balls will either come with black then both black balls are discarder.

→ If it will come with red then only black balls will be discarded.

→ Suppose 2 red balls will come together means we are discarding both red balls.

Step-3: As per the above constraints, total 19 Red balls it means odd number.

→ Among 19 only 18 will be discarded.

Step-3: Final content of bag at second last trail will be either R,B (or) R,R,R and finally in last

trail bag will left with one red ball in both the cases.

Question 4 |

If x = -1 and x = 2 are extreme points of f(x) = α log |x| + βx2 + x then

α = -6, β = -1/2 | |

α = 2, β = -1/2 | |

α = 2, β = 1/2 | |

α = -6, β =1/2 |

Question 4 Explanation:

Given data,

Step-1: x= -1 and x=2

f(x) = α log |x| + β x2 + x

f'(x)= α/x + 2βx + 1 = 0

Step-2: for extreme points f'(x)=0

α/x + 2βx + 1=0

Step-3: For x= -1 then we will get α+2β= 1 → (i)

For x= 2: then we will get α+8β= 2 → (ii)

from (i) and (ii) we can get the value of α=2 and β= -1/2

Step-1: x= -1 and x=2

f(x) = α log |x| + β x2 + x

f'(x)= α/x + 2βx + 1 = 0

Step-2: for extreme points f'(x)=0

α/x + 2βx + 1=0

Step-3: For x= -1 then we will get α+2β= 1 → (i)

For x= 2: then we will get α+8β= 2 → (ii)

from (i) and (ii) we can get the value of α=2 and β= -1/2

Question 5 |

Let f(x) = log|x| and g(x) = sin x . If A is the range of f(g(x)) and B is the range of g(f(x)) then A ∩ B is

[-1, 0] | |

[-1, 0) | |

[-∞, 0] | |

[-∞,1] |

Question 5 Explanation:

Given data,

Step-1: f(x) = log|x| and given range is [-∞ to +∞]

g(x) = sin(x) and given range is [-1,1]

Step-2: Given 2 variables are A and B

A= f(g(x))

= log|g(x)|

= log|sin(x)|

So, we will get A range is [-∞ ,0]

Step-3: B= g(f(x))

= sin(f(x))

= sin(log|x|)

So, we will get B range is [-1, 1]

Step-4: Common in both A and B is A∩B

A∩B = [-1, 0]

Key point: Ranges [ -1 ≤ sin(x) ≤ 1 and -∞ ≤ log|x| ≤ ∞ ]

Step-1: f(x) = log|x| and given range is [-∞ to +∞]

g(x) = sin(x) and given range is [-1,1]

Step-2: Given 2 variables are A and B

A= f(g(x))

= log|g(x)|

= log|sin(x)|

So, we will get A range is [-∞ ,0]

Step-3: B= g(f(x))

= sin(f(x))

= sin(log|x|)

So, we will get B range is [-1, 1]

Step-4: Common in both A and B is A∩B

A∩B = [-1, 0]

Key point: Ranges [ -1 ≤ sin(x) ≤ 1 and -∞ ≤ log|x| ≤ ∞ ]

Question 6 |

The proposition (P⇒Q)⋀(Q⇒P) is a

tautology | |

contradiction | |

contingency | |

absurdity |

Question 6 Explanation:

A proposition that is neither a tautology nor a contradiction is called a contingency.

Question 7 |

If T(x) denotes x is a trigonometric function, P(x) denotes x is a periodic function and C(x) denotes x is a continuous function then the statement “It is not the case that some trigonometric functions are not periodic” can be logically represented as

¬∃(x) [ T(x) ⋀ ¬P(x) ] | |

¬∃(x) [ T(x) ⋁ ¬P(x) ] | |

¬∃(x) [ ¬T(x) ⋀ ¬P(x) ] | |

¬∃(x) [ T(x) ⋀ P(x) ] |

Question 7 Explanation:

Option A implies "It is not the case that some trigonometric functions are not periodic”.

Hence it is correct .

Option B implies "It is not the case that some are trigonometric functions or they are not periodic”.

Option C implies "It is not the case that some of not trigonometric functions are not periodic”.

Option D implies "It is not the case that some trigonometric functions are periodic”.

Hence it is correct .

Option B implies "It is not the case that some are trigonometric functions or they are not periodic”.

Option C implies "It is not the case that some of not trigonometric functions are not periodic”.

Option D implies "It is not the case that some trigonometric functions are periodic”.

Question 8 |

The number of elements in the power set of { {1,2}, {2,1,1}, {2,1,1,2} } is

3 | |

8 | |

4 | |

2 |

Question 8 Explanation:

Given data,

Step-1: Total number of elements in power set of given set with ‘n’ elements = 2

Example: {1,2}

{{∅},{1},{2},{1,2}} → Total 4 possibilities.

Step-2: The given set in question contains 3 elements({1,2},{2,1,1}, {2,1,1,2} }. So, number of elements in power set of given set is 2

Step-3: The power set is {{∅},{X}} or {{∅},{1,2}}.

Step-1: Total number of elements in power set of given set with ‘n’ elements = 2

^{n}Example: {1,2}

{{∅},{1},{2},{1,2}} → Total 4 possibilities.

Step-2: The given set in question contains 3 elements({1,2},{2,1,1}, {2,1,1,2} }. So, number of elements in power set of given set is 2

^{3}=8.Step-3: The power set is {{∅},{X}} or {{∅},{1,2}}.

Question 9 |

The function f: [0,3]→[1,29] defined by f(x) = 2x3 – 15x2 + 36x + 1 is

injective and surjective | |

surjective but not injective | |

injective but not surjective | |

neither injective nor surjective |

Question 9 Explanation:

Question 10 |

2/5 | |

2 | |

3 | |

5/2 |

Question 10 Explanation:

Given data,

Step-1: It is clearly showing that two vectors are perpendicular. If two vectors are perpendicular

we are using dot product is zero. a.b =0

Step-2: Calculating dot product is “i is multiplied with i” and “j is multiplied with coefficient of j”

Step-3: we can write like this,

= (2i+λj+k).(i-2j+3k)=0

= 2-2λ+3 =0

-2λ = -5

λ=5/2

Step-1: It is clearly showing that two vectors are perpendicular. If two vectors are perpendicular

we are using dot product is zero. a.b =0

Step-2: Calculating dot product is “i is multiplied with i” and “j is multiplied with coefficient of j”

Step-3: we can write like this,

= (2i+λj+k).(i-2j+3k)=0

= 2-2λ+3 =0

-2λ = -5

λ=5/2

Question 11 |

Consider the schema

Sailors(sid, sname, rating, age) with the following data

For the query

SELECT S.rating, AVG(S.age) AS average FROM Sailors S

Where S.age >= 18

GROUP BY S.rating

HAVING 1 < (SELECT COUNT(*) FROM Sailors S2 where S.rating = S2.rating)

The number of rows returned is

Sailors(sid, sname, rating, age) with the following data

For the query

SELECT S.rating, AVG(S.age) AS average FROM Sailors S

Where S.age >= 18

GROUP BY S.rating

HAVING 1 < (SELECT COUNT(*) FROM Sailors S2 where S.rating = S2.rating)

The number of rows returned is

6 | |

5 | |

4 | |

3 |

Question 11 Explanation:

Question 12 |

Consider a table that describes the customers :
Customers(custid, name, gender, rating)
The rating value is an integer in the range 1 to 5 and only two values (male and female) are recorded for gender. Consider the query “how many male customers have a rating of 5”? The best indexing mechanism appropriate for the query is

Linear hashing | |

Extendible hashing | |

B+ Tree | |

Bit-mapped hashing |

Question 12 Explanation:

→ A bitmap index is a special kind of database index that uses bitmaps.

→ Bitmap indexes have traditionally been considered to work well for low-cardinality columns, which have a modest number of distinct values, either absolutely, or relative to the number of records that contain the data.

→ The extreme case of low cardinality is Boolean data (e.g., does a resident in a city have internet access?), which has two values, True and False.

→ Bitmap indexes use bit arrays (commonly called bitmaps) and Solution queries by performing bitwise logical operations on these bitmaps. Bitmap indexes have a significant space and performance advantage over other structures for query of such data.

→ Their drawback is they are less efficient than the traditional B-tree indexes for columns whose data is frequently updated: consequently, they are more often employed in read-only systems that are specialized for fast query - e.g., data warehouses, and generally unsuitable for online transaction processing applications.

→ Bitmap indexes have traditionally been considered to work well for low-cardinality columns, which have a modest number of distinct values, either absolutely, or relative to the number of records that contain the data.

→ The extreme case of low cardinality is Boolean data (e.g., does a resident in a city have internet access?), which has two values, True and False.

→ Bitmap indexes use bit arrays (commonly called bitmaps) and Solution queries by performing bitwise logical operations on these bitmaps. Bitmap indexes have a significant space and performance advantage over other structures for query of such data.

→ Their drawback is they are less efficient than the traditional B-tree indexes for columns whose data is frequently updated: consequently, they are more often employed in read-only systems that are specialized for fast query - e.g., data warehouses, and generally unsuitable for online transaction processing applications.

Question 13 |

Type 4 JDBC driver is a driver

which is written in C++ | |

which requires an intermediate layer | |

which communicates through Java sockets | |

which translates JDBC function calls into API not native to DBMS |

Question 13 Explanation:

The JDBC type 4 driver, also known as the Direct to Database Pure Java Driver, is a database driver implementation that converts JDBC calls directly into a vendor-specific database protocol.

Written completely in Java, type 4 drivers are thus platform independent. They install inside the Java Virtual Machine of the client. This provides better performance than the type 1 and type 2 drivers as it does not have the overhead of conversion of calls into ODBC or database API calls. Unlike the type 3 drivers, it does not need associated software to work.

As the database protocol is vendor specific, the JDBC client requires separate drivers, usually vendor supplied, to connect to different types of databases.

These drivers don't translate the requests into an intermediary format (such as ODBC).

The client application connects directly to the database server. No translation or middleware layers are used, improving performance.

The JVM can manage all aspects of the application-to-database connection; this can facilitate debugging.

Type-1 driver (or) JDBC-ODBC bridge driver

Type-2 driver (or) Native-API driver

Type-3 driver (or) Network Protocol driver

Type-4 driver (or) Thin driver

Written completely in Java, type 4 drivers are thus platform independent. They install inside the Java Virtual Machine of the client. This provides better performance than the type 1 and type 2 drivers as it does not have the overhead of conversion of calls into ODBC or database API calls. Unlike the type 3 drivers, it does not need associated software to work.

As the database protocol is vendor specific, the JDBC client requires separate drivers, usually vendor supplied, to connect to different types of databases.

**Advantages**Completely implemented in Java to achieve platform independence.These drivers don't translate the requests into an intermediary format (such as ODBC).

The client application connects directly to the database server. No translation or middleware layers are used, improving performance.

The JVM can manage all aspects of the application-to-database connection; this can facilitate debugging.

**Disadvantages**Drivers are database specific, as different database vendors use widely different (and usually proprietary) network protocols.Type-1 driver (or) JDBC-ODBC bridge driver

Type-2 driver (or) Native-API driver

Type-3 driver (or) Network Protocol driver

Type-4 driver (or) Thin driver

Question 14 |

Consider the recurrence equation

T(n) = 2T(n-1), if n>0

= 1, otherwise

Then T(n) is (in big O order)

T(n) = 2T(n-1), if n>0

= 1, otherwise

Then T(n) is (in big O order)

O(n) | |

O(2 | |

O(1) | |

O(log n) |

Question 14 Explanation:

Question 15 |

The complexity of the program is

O(log n) | |

O(n ^{2}) | |

O(n ^{2} log n) | |

O(n log n) |

Question 15 Explanation:

Question 16 |

Match the following and choose the correct Solution for the order A, B, C, D

r, s, p, q | |

r, p, s, q | |

q, s, p, r | |

s, p, q, r |

Question 16 Explanation:

Strassen matrix multiplication→ Divide and conquer

Insertion sort→ Decrease and Conquer

Gaussian Elimination→ Transform and Conquer

Floyd Shortest path algorithm→ Dynamic programming

Insertion sort→ Decrease and Conquer

Gaussian Elimination→ Transform and Conquer

Floyd Shortest path algorithm→ Dynamic programming

Question 17 |

For Σ={a,b} the regular expression r = (aa)*(bb)*b denotes

Set of strings with 2 a’s and 2 b’s | |

Set of strings with 2 a’s 2 b’s followed by b | |

Set of strings with 2 a’s followed by b’s which is a multiple of 3 | |

Set of strings with even number of a’s followed by odd number of b’s |

Question 17 Explanation:

→ Given expression denotes language that accepts set of all strings with even number of a’s followed by the odd number of b’s.

→ Because (aa)* implies even number of a's and (bb)*b implies even number of b's followed by one b , it implies the odd number of b's.

→ Because (aa)* implies even number of a's and (bb)*b implies even number of b's followed by one b , it implies the odd number of b's.

Question 18 |

Consider the grammar with productions
S → aSb | SS | ϵ
This grammar is

not context-free, not linear | |

not context-free, linear | |

context-free, not linear | |

context-free, linear |

Question 18 Explanation:

Linear grammar means regular grammar which is in the form of A→ Ba | b (or) A→ aB|b

and Context free grammar is in the form of A→ ɑ where ɑ = (V⋃T)^*

V → set of terminals and T → set of non-terminals

It is clearly seen that given grammar is not linear but context-free.

and Context free grammar is in the form of A→ ɑ where ɑ = (V⋃T)^*

V → set of terminals and T → set of non-terminals

It is clearly seen that given grammar is not linear but context-free.

Question 19 |

Identify the language generated by the following grammar

S -> AB

A -> aAb|ϵ

B -> bB| b

S -> AB

A -> aAb|ϵ

B -> bB| b

{a ^{m}b^{n} | n>=m, m>0} | |

{a ^{m}b^{n} | n>=m, m>=0} | |

{a ^{m}b^{n} | n>m, m>0} | |

{a ^{m}b^{n} | n>m, m>=0} |

Question 19 Explanation:

The language generated by given grammar is - L={b,bb,abb,abbb,ababb}

Hence it is a

Hence it is a

^{m}b^{n}| n>m, m>=0Question 20 |

Let L

_{1}be regular language, L_{2}be a deterministic context free language and L_{3}a recursively enumerable language, but not recursive. Which one of the following statements is false?L _{1} ∩ L_{2} is context-free | |

L _{3} ∩ L_{1} is recursive | |

L _{1} ∪ L_{2} is context-free | |

L _{1} ∩ L_{2} ∩ L_{3} is recursively enumerable |

Question 20 Explanation:

→ Option A is true, as by closure property (R is a regular language and L is any language)

L ∩ R = L ( i.e. L Intersection R is same type as L )

So L

→ Option B is false, as L

→ Option C is true, as by closure property (R is a regular language and L is any language)

L U R = L ( i.e. L UNION R is same type as L )

So, L

→ Option D is true, as L

As every DCFL is recursive enumerable, so it is equivalent to Recursive enumerable ∩ Recursive enumerable. And recursive enumerable are closed under INTERSECTION so it will be recursive enumerable.

L ∩ R = L ( i.e. L Intersection R is same type as L )

So L

_{1}∩ L_{2}is a deterministic CFL.→ Option B is false, as L

_{3}is recursive enumerable but not recursive, so intersection with L1 must be recursive enumerable, but may or may not be recursive.→ Option C is true, as by closure property (R is a regular language and L is any language)

L U R = L ( i.e. L UNION R is same type as L )

So, L

_{1}∪ L_{2}is deterministic context free, hence it is also context free.→ Option D is true, as L

_{1}∩ L_{2}is DCFL and DCFL ∩ L_{3}is equivalent to DCFL ∩ Recursive enumerable.As every DCFL is recursive enumerable, so it is equivalent to Recursive enumerable ∩ Recursive enumerable. And recursive enumerable are closed under INTERSECTION so it will be recursive enumerable.

Question 21 |

Let L = {a

Then which of the following is true?

^{p}| p is a prime}.Then which of the following is true?

It is not accepted by a Turing Machine | |

It is regular but not context-free | |

It is context-free but not regular | |

It is neither regular nor context-free but accepted by a Turing Machine |

Question 21 Explanation:

L = {a

L can only be accepted by a Turing machine

^{p}| p is a prime}L can only be accepted by a Turing machine

There are 21 questions to complete.