CS and IT Gate 2016 Set-1 Questions with Answer

Given:
Load L₁ = 80 units, cycles to failure N₁ = 100
When load is halved, L₂ = 40 units, cycles to failure N₂ = 10000
Target cycles to failure N₃ = 5000
To find:
Load L₃ for which failure happens in 5000 cycles.
Solution:
The number of cycles decreases exponentially with load, so I can write the relationship as:
N = A × e^-kL
Taking natural logarithm on both sides gives:
ln(N) = ln(A) - kL
Now, writing this for the first two data points:
ln(100) = ln(A) - 80k ... (Equation 1)
ln(10000) = ln(A) - 40k ... (Equation 2)
Subtracting Equation 1 from Equation 2 to eliminate ln(A):
ln(10000) - ln(100) = 40k
So we get:
ln(10000 / 100) = 40k
ln(100) = 40k
Therefore, k is:
k = ln(100) / 40
Now let me set up the relation for N₃ = 5000:
ln(10000) - ln(5000) = k(L₃ - 40)
Simplifying the left-hand side:
ln(2) = k(L₃ - 40)
Now substituting the value of k from above:
ln(2) = [ln(100) / 40] × (L₃ - 40)
Rearranging to solve for (L₃ - 40):
L₃ - 40 = 40 × [ln(2) / ln(100)]
Since ln(100) = 2 × ln(10), this simplifies to:
L₃ - 40 = 40 × [ln(2) / (2 × ln(10))] = 20 × log₁₀(2)
Putting log₁₀(2) ≈ 0.30103:
L₃ - 40 = 20 × 0.30103 = 6.02
Hence, the load is:
L₃ = 40 + 6.02 = 46.02 units
Answer:
(B) 46.02

Given:
I. P always beats Q.
II. R always beats S.
III. S loses to P only sometimes.
IV. R always loses to Q.
To find:
Which of the given statements (i) or (ii) can be logically inferred.
Solution:
Let me analyze the relationships given between the players.
From statement I, P always beats Q: P > Q.
From statement IV, Q always beats R: Q > R.
From statement II, R always beats S: R > S.
Combining these three, the chain looks like: P > Q > R > S.
Now let me look at statement III: "S loses to P only sometimes".
This means P beats S only occasionally, so most of the time S wins against P (or at least S does not consistently lose to P).
This creates a non-transitive cycle, like rock-paper-scissors.
Now let me evaluate statement (i): "P is likely to beat all the three other players".
P beats Q and R consistently. But against S, P only wins sometimes. That means P is not likely to beat S. So statement (i) cannot be inferred.
Next, let me check statement (ii): "S is the absolute worst player in the set".
Even though S loses to R, S actually beats P more often than not (since S loses to P only sometimes). Because S wins against P, who is one of the top players, S cannot be called the absolute worst player. So statement (ii) cannot be inferred either.
Therefore, neither (i) nor (ii) can be inferred.
Answer:
D) neither (i) nor (ii)

Given:
Two statements:
1. Indian currency notes show the denomination indicated in at least seventeen languages.
2. "If this is not an indication of the nation’s diversity, nothing else is."
To find:
The correct logical inference from the given statements among the options.
Solution:
Let me read each statement carefully and check the options one by one.
First, the text says the denomination is in "at least seventeen languages". This means there could be more than seventeen languages. So option (A), which claims India has "exactly seventeen languages", is clearly incorrect.
Now looking at the second sentence: "If this is not an indication of the nation's diversity, nothing else is."
This is a standard rhetorical expression used to emphasize that something is an extremely strong example or proof of a fact. It does not literally mean that no other indicators exist in the entire world, so option (B) is too extreme and incorrect.
There is also no mention anywhere about whether currency notes have enough physical space for all Indian languages, which rules out option (C).
Therefore, the sentence directly implies that having multiple languages (linguistic pluralism) on currency notes serves as very strong evidence of the country's diversity.
This matches option (D).
Answer:
(D)

Given:
Number of unit cubic blocks = 64
Side length of each unit block = 1 unit
One unit block is removed from each corner of the cube.
To find:
The resulting surface area of the body after removing the corner blocks.
Solution:
First, let me find the side length of the original cube.
Since it is made of 64 unit blocks, the side length is:
s = (64)^1/3 = 4 units.
Now, let me calculate the original total surface area of this 4 × 4 × 4 cube.
Original surface area = 6 × s²
Original surface area = 6 × 4² = 6 × 16 = 96 square units.
Now, let's see what happens when a corner block is removed.
A cube has 8 corners, so 8 unit blocks are removed.
For any corner block, 3 of its faces were exposed to the outside.
When this block is taken out, those 3 exposed faces are gone.
At the same time, removing it uncovers 3 new internal faces inside the cutout cavity.
So, the surface area lost per corner = 3 × (1 × 1) = 3 square units.
The surface area gained per corner = 3 × (1 × 1) = 3 square units.
Net change in surface area for each corner = -3 + 3 = 0.
Since the change is zero for every corner, removing the 8 corner blocks does not change the total surface area at all.
So, the resulting surface area is simply the original surface area.
Resulting surface area = 96 square units.
Answer:
(D) 96

Given:
‘relftaga’ = carefree
‘otaga’ = careful
‘fertaga’ = careless
To find:
The code for ‘aftercare’ from the given options.
Solution:
Let me break down the common parts in the given words.
All three English words contain ‘care’, and all three given code words end with ‘taga’.
So clearly, ‘taga’ corresponds to ‘care’.
Now let me check the prefixes and suffixes:
In ‘relftaga’, ‘relf’ corresponds to ‘free’.
In ‘otaga’, ‘o’ corresponds to ‘ful’.
In ‘fertaga’, ‘fer’ corresponds to ‘less’.
Notice the pattern of word formation:
English has ‘care’ at the beginning (care-free, care-ful, care-less).
In the code, ‘taga’ is placed at the end (relf-taga, o-taga, fer-taga).
So the order of the components is reversed in the code language.
Now for the word ‘aftercare’:
Here, ‘care’ is at the end in English (after + care).
Reversing the order means the code must start with ‘taga’ (taga + code for ‘after’).
Looking at the options, only (B) and (C) start with ‘taga’.
We already know ‘fer’ means ‘less’, so (B) cannot mean ‘aftercare’.
That leaves ‘tagazen’, where ‘zen’ is a new component representing ‘after’.
Answer:
(C) tagazen

Given:
The statement: "Give me a lever long enough and a fulcrum on which to place it, and I will move the world."
To find:
The type of statement represented by the quote from the given options.
Solution:
Let me read the quote carefully.
Archimedes talks about moving the entire Earth using an extraordinarily long lever and a fulcrum.
Obviously, one cannot literally stand in space with a physical lever and move the planet.
He is using exaggeration, or hyperbole, to illustrate the immense mechanical advantage provided by a lever.
Since it represents an idea metaphorically rather than in an actual, physical sense, it cannot be literal.
Looking at the other options, "collateral" relates to security for a loan or secondary effects, and "figurine" is a small statue, so neither makes any sense here.
Therefore, the statement is used in a non-literal, metaphorical way, which means it is figurative.
Answer: (A) figurative

Given:
A phrase defining: "A rewording of something written or spoken".
To find:
The correct term from the given options that matches this definition.
Solution:
Let me check the meaning of each option one by one.
First, "paraphrase" means expressing the meaning of something written or spoken using different words, which is literally rewording.
Second, a "paradox" is a self-contradictory statement that might actually be true.
Third, a "paradigm" is a standard model, pattern, or typical example of something.
Fourth, "paraffin" is a type of wax or liquid fuel used in lamps and heaters.
So clearly, rewording something written or spoken is called a paraphrase.
Hence, option (A) is the correct choice.
Answer:
(A) paraphrase

Given:
Four sentence choices involving the conjunction 'until' and subject-verb agreement.
To find:
The most suitable sentence with respect to grammar and usage.
Solution:
Let me analyze the grammar rules tested here.
First, the word 'until' already has a negative meaning built into it, which means 'up to the time when'.
Because of this, I should not use a negative word like 'does not' or 'doesn’t' in the clause introduced by 'until', as that makes a double negative.
So this immediately rules out options (A) and (B).
Now I am left with options (C) and (D).
Let me check the subject-verb agreement in the subordinate clause.
The subject here is 'the minister', which is a third-person singular noun.
Therefore, the verb must also be in the third-person singular form, which is 'meets' and not 'meet'.
Option (C) uses 'meet', which is incorrect subject-verb agreement.
Option (D) correctly uses 'meets' without any double negative.
So option (D) is the grammatically correct sentence.
Answer: (D) I will not leave the place until the minister meets me.

Given:
Language X is recursive (REC).
Language Y is recursively enumerable but not recursive (RE but not REC).
Y ≤_m W and Z ≤_m X.
To find:
The correct statement among the given options.
Solution:
First, let me recall the standard properties of many-one reduction (A ≤_m B):
1. If B is recursive, then A must also be recursive.
2. If B is recursively enumerable, then A must also be recursively enumerable.
Taking the contrapositive:
3. If A is not recursive, then B cannot be recursive.
4. If A is not RE, then B cannot be RE.
Now let's analyze Z ≤_m X:
We are given that X is recursive.
Since Z reduces to a recursive language X, Z must be recursive.
So, Z is definitely recursive.
Now let's analyze Y ≤_m W:
We know Y is not recursive.
By property 3, W cannot be recursive (if W were recursive, Y would be recursive, which is a contradiction).
Can W be recursively enumerable? Yes, because if we pick W = Y, then Y ≤_m Y holds, and W is RE.
W can also be not RE (for example, reducing to a non-RE language).
Therefore, W can be recursively enumerable.
Combining both results, W can be recursively enumerable and Z is recursive.
Answer:
(A) W can be recursively enumerable and Z is recursive.

Given:
Context-free grammars:
G1: S → aS | B, B → b | bB
G2: S → aA | bB, A → aA | B | ε, B → bB | ε
To find:
The languages generated by G1 and G2.
Solution:
First, let me analyze grammar G1.
Looking at the non-terminal B:
B → b | bB
This means B produces at least one 'b', so B generates b⁺, or bⁿ where n ≥ 1 (that is, n > 0).
Now looking at the start symbol S:
S → aS | B
S can produce zero or more 'a's before switching to B.
So S generates a*B, which gives a^mbⁿ where m ≥ 0 and n > 0.
Therefore, L(G1) = {a^mbⁿ | m ≥ 0 and n > 0}.
Now let me analyze grammar G2.
First, look at B:
B → bB | ε, which means B generates b* (zero or more 'b's).
Next, look at A:
A → aA | B | ε, which generates a*B = a*b*.
Now, look at the productions for start symbol S:
S → aA | bB
Case 1: S → aA
Since A generates a*b*, aA produces strings with at least one 'a' followed by any number of 'b's (including zero 'b's).
So this case gives a^mbⁿ where m ≥ 1 and n ≥ 0.
Case 2: S → bB
Since B generates b*, bB produces strings with zero 'a's and at least one 'b'.
So this case gives a^mbⁿ where m = 0 and n ≥ 1.
Combining both cases from S, the grammar generates all strings of the form a^mbⁿ except the empty string (m = 0, n = 0).
So at least one of m or n must be strictly positive.
This gives the condition: m > 0 or n > 0.
Therefore, L(G2) = {a^mbⁿ | m > 0 or n > 0}.
Comparing with the given choices, this matches Option D.
Answer:
(D)

Given:
Language: Set of all binary strings containing both two consecutive 0s and two consecutive 1s.
Alphabet: Σ = {0, 1}.
To find:
The correct regular expression for this language.
Solution:
The condition states that every string in the language must contain the substring "00" AND the substring "11".
Since "00" and "11" share no common characters, they cannot overlap at all.
This means in any valid string, either "00" comes before "11", or "11" comes before "00".
Let me write the regular expression for the first case, where "00" appears before "11":
(0+1)*00(0+1)*11(0+1)*
Now for the second case, where "11" appears before "00":
(0+1)*11(0+1)*00(0+1)*
Combining both cases using union (+), I get:
(0+1)*00(0+1)*11(0+1)* + (0+1)*11(0+1)*00(0+1)*
Now I can factor out (0+1)* from the left and right sides:
(0+1)*(00(0+1)*11 + 11(0+1)*00)(0+1)*
Let me check the other options just to be completely sure.
Option A requires "00" and "11" to be immediately adjacent to each other, so it misses strings like "001011".
Option C uses union between the two conditions, which represents strings with "00" OR "11", not AND.
Option D forces the string to start with "00" or "11" and end with "11" or "00", so it misses strings like "100110".
So only option B correctly captures the required language.
Answer:
(B) (0+1)* (00(0+1) *11+11(0+1)*00)(0+1)*

Given:
Four decision problems:
I. For NFAs N₁ and N₂, is L(N₁) ∩ L(N₂) = Φ?
II. For a CFG G and a string x, does x ∈ L(G)?
III. For CFGs G₁ and G₂, is L(G₁) = L(G₂)?
IV. For a TM M, is L(M) = Φ?
To find:
Which of these decision problems are undecidable.
Solution:
Let me check each problem one by one.
First, looking at problem I:
Regular languages are closed under intersection, so L(N₁) ∩ L(N₂) is also regular.
Emptiness for regular languages is decidable by checking reachability of a final state from the start state.
So, problem I is decidable.
Now, looking at problem II:
This is the membership problem for Context-Free Grammars.
We can use the CYK algorithm to decide if x ∈ L(G) in polynomial time.
So, problem II is decidable.
Next, looking at problem III:
This is the equivalence problem for Context-Free Grammars.
Equivalence of two CFGs is a standard undecidable problem (it can be reduced from the Post Correspondence Problem).
So, problem III is undecidable.
Finally, looking at problem IV:
This is the emptiness problem for Turing Machines.
Emptiness is a non-trivial property of the language of a TM, so by Rice's theorem, it is undecidable.
So, problem IV is undecidable.
Therefore, the undecidable problems are III and IV.
Answer: (C) III and IV only

Given:
Grammar production rules: S → aS | bS | ε.
To find:
The language generated by the given grammar.
Solution:
Let me look at the productions given for the start symbol S.
S can expand to aS, meaning it can generate an 'a' and continue generating.
S can also expand to bS, meaning it can generate a 'b' and continue generating.
And finally, S can expand to ε, which terminates the derivation.
Let me test a few strings to see what can be formed.
If I just choose S → ε, I get the empty string ε.
If I choose S → aS → aε = a, I get string "a".
If I choose S → bS → bε = b, I get string "b".
If I want an arbitrary string like "baab":
S → bS → baS → baaS → baabS → baabε = baab.
So clearly, at any position, I can choose either 'a' or 'b' freely without any restriction on order or count.
Once I am done, I can just replace S with ε to stop.
This means the grammar can generate any sequence of 'a's and 'b's of any length, including length 0.
Therefore, the regular expression for this language is (a + b)*.
In set notation, this is equal to {a, b}*.
Looking at the options, this directly matches option D.
Answer: (D) {a,b}*