ISRO-2017 December

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
A
{n,1}
B
{n, n}
C
{n2, 1}
D
{1, n2}
       Engineering-Mathematics       Sets-And Relation
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.
Question 2
Consider the set of integers I. Let D denote “divides with an integer quotient” (e.g. 4D8 but 4D7). Then D is
A
Reflexive, not symmetric, transitive
B
Not reflexive, not antisymmetric, transitive
C
Reflexive, antisymmetric, transitive
D
Not reflexive, not antisymmetric, not transitive
       Engineering-Mathematics       Set-Theory
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
A
1
B
1/21
C
0
D
0.5
       Engineering-Mathematics       Probability
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.
Question 4
If x = -1 and x = 2 are extreme points of f(x) = α log |x| + βx2 + x then
A
α = -6, β = -1/2
B
α = 2, β = -1/2
C
α = 2, β = 1/2
D
α = -6, β =1/2
       Engineering-Mathematics       Calculus
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
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
A
[-1, 0]
B
[-1, 0)
C
[-∞, 0]
D
[-∞,1]
       Engineering-Mathematics       Set-Theory
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| ≤ ∞ ]
Question 6
The proposition (P⇒Q)⋀(Q⇒P) is a
A
tautology
B
contradiction
C
contingency
D
absurdity
       Engineering-Mathematics       Propositional-Logic
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
A
¬∃(x) [ T(x) ⋀ ¬P(x) ]
B
¬∃(x) [ T(x) ⋁ ¬P(x) ]
C
¬∃(x) [ ¬T(x) ⋀ ¬P(x) ]
D
¬∃(x) [ T(x) ⋀ P(x) ]
       Engineering-Mathematics       Calculus
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”.
Question 8
The number of elements in the power set of { {1,2}, {2,1,1}, {2,1,1,2} } is
A
3
B
8
C
4
D
2
       Engineering-Mathematics       Set-Theory
Question 8 Explanation: 
Given data,
Step-1: Total number of elements in power set of given set with ‘n’ elements = 2n
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 23 =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
A
injective and surjective
B
surjective but not injective
C
injective but not surjective
D
neither injective nor surjective
       Engineering-Mathematics       Calculus
Question 9 Explanation: 
Question 10
A
2/5
B
2
C
3
D
5/2
       Engineering-Mathematics       Vectors
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
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
A
6
B
5
C
4
D
3
       Database-Management-System       SQL
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
A
Linear hashing
B
Extendible hashing
C
B+ Tree
D
Bit-mapped hashing
       Database-Management-System       B-and-B+-Trees
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.
Question 13
Type 4 JDBC driver is a driver
A
which is written in C++
B
which requires an intermediate layer
C
which communicates through Java sockets
D
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.

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)
A
O(n)
B
O(2n)
C
O(1)
D
O(log n)
       Algorithms       Time-Complexity
Question 14 Explanation: 
Question 15

The complexity of the program is
A
O(log n)
B
O(n2)
C
O(n2 log n)
D
O(n log n)
       Programming       Control Flow
Question 15 Explanation: 
Question 16
Match the following and choose the correct Solution for the order A, B, C, D
A
r, s, p, q
B
r, p, s, q
C
q, s, p, r
D
s, p, q, r
       Algorithms       Dynamic-Programming-and-Sorting
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
Question 17
For Σ={a,b} the regular expression r = (aa)*(bb)*b denotes
A
Set of strings with 2 a’s and 2 b’s
B
Set of strings with 2 a’s 2 b’s followed by b
C
Set of strings with 2 a’s followed by b’s which is a multiple of 3
D
Set of strings with even number of a’s followed by odd number of b’s
       Theory-of-Computation       Regular-Expression
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.
Question 18
Consider the grammar with productions S → aSb | SS | ϵ This grammar is
A
not context-free, not linear
B
not context-free, linear
C
context-free, not linear
D
context-free, linear
       Theory-of-Computation       Context-Free-Language
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.
Question 19
Identify the language generated by the following grammar
S -> AB
A -> aAb|ϵ
B -> bB| b
A
{ambn | n>=m, m>0}
B
{ambn | n>=m, m>=0}
C
{ambn | n>m, m>0}
D
{ambn | n>m, m>=0}
       Theory-of-Computation       Languages-and-Grammars
Question 19 Explanation: 
The language generated by given grammar is - L={b,bb,abb,abbb,ababb}
Hence it is ambn | n>m, m>=0
Question 20
Let L1 be regular language, L2 be a deterministic context free language and L3 a recursively enumerable language, but not recursive. Which one of the following statements is false?
A
L1 ∩ L2 is context-free
B
L3 ∩ L1 is recursive
C
L1 ∪ L2 is context-free
D
L1 ∩ L2 ∩ L3 is recursively enumerable
       Theory-of-Computation       Recursive-and-Recursively-Enumerable-Language
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 L1 ∩ L2 is a deterministic CFL.
→ Option B is false, as L3 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, L1 ∪ L2 is deterministic context free, hence it is also context free.
→ Option D is true, as L1 ∩ L2 is DCFL and DCFL ∩ L3 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 = {ap| p is a prime}.
Then which of the following is true?
A
It is not accepted by a Turing Machine
B
It is regular but not context-free
C
It is context-free but not regular
D
It is neither regular nor context-free but accepted by a Turing Machine
       Theory-of-Computation       Context-Free-Language
Question 21 Explanation: 
L = {ap | p is a prime}
L can only be accepted by a Turing machine
There are 21 questions to complete.