Gate 2018
Question 1 
“From where are they bringing their books? __________ bringing __________ books
from __________.”
The words that best fill the blanks in the above sentence are
Their, they’re, there  
They’re, their, there  
There, their, they’re  
They’re, there, there 
Question 1 Explanation:
Question 2 
"A _______ investigation can sometimes yield new facts, but typically organized ones are more successful."
The word that best fills the blank in the above sentence is
meandering  
timely  
consistent  
systematic 
Question 2 Explanation:
Meandering means "Proceeding in a convoluted way (or) undirected fashion".
Question 3 
The area of a square is d. What is the area of the circle which has the diagonal of the square as its diameter?
πd  
πd^{2}  
(1/2)πd^{2}  
(1/2)πd 
Question 3 Explanation:
In general,
Area of a square A = a^{2} (where a is side)
In the question,
Area of a square = d
The side of a square = √d
Diagonal of a square = Diameter of circle
From Pythagoras theorem,
Area of a square A = a^{2} (where a is side)
In the question,
Area of a square = d
The side of a square = √d
Diagonal of a square = Diameter of circle
From Pythagoras theorem,
Question 4 
What is the missing number in the following sequence?
2, 12, 60, 240, 720, 1440, _______, 0
2880  
1440  
720  
0 
Question 4 Explanation:
2×6=12
12×5=60
60×4=240
240×3=720
720×2=1440
1440×0=0
Question 5 
What would be the smallest natural number which when divided either by 20 or by 42 or by 76 leaves a remainder of '7' in each case?
3047  
6047  
7987  
63847 
Question 5 Explanation:
MethodI:
Take the LCM of 20,42,76 i.e., 7980.
⟹ Remainder = 7
⟹ Smallest number divisible by 20 (or) 42 (or) 72 which leaves remainder 7 is = 7980+7 = 7987
Method II:
Option I:
3047 – 7 = 3040
3040 not divisible by 42
Option II:
6040 not divisible by 42
Option III:
7980 divisible by 20, 42, 76
Option IV:
63840 divisible by 20, 42, 76
→ Smallest (7980, 63840) = 7980
→ 7980 + remainder 7 = 7987
Take the LCM of 20,42,76 i.e., 7980.
⟹ Remainder = 7
⟹ Smallest number divisible by 20 (or) 42 (or) 72 which leaves remainder 7 is = 7980+7 = 7987
Method II:
Option I:
3047 – 7 = 3040
3040 not divisible by 42
Option II:
6040 not divisible by 42
Option III:
7980 divisible by 20, 42, 76
Option IV:
63840 divisible by 20, 42, 76
→ Smallest (7980, 63840) = 7980
→ 7980 + remainder 7 = 7987
Question 6 
If pqr≠0and p ^{x}=1/q, q ^{y}=1/r, r ^{z}=1/p, what is the value of the product xyz?
1  
1/pqr  
1  
pqr 
Question 6 Explanation:
pqr≠0
→ p^{x} = 1/q ⟹ 1/p^{x} = 1/q
⟹ q = p^{x}
⟹ log q = log p^{x}
⟹ x log p = log q ⟹ x = log q/ log p → q^{y} = 1/r ⟹ 1/q^{y} = 1/r
⟹ q^{y} = r
⟹ y log q = log r
⟹ y = log r/ log q
→ r^{z} = 1/p ⟹ 1/r^{z} = 1/p
⟹ p = r^{z}
⟹ log r^{z} = log p
⟹ z log r = log p
⟹ z = log p/ log r
XYZ = log q/ log p * log r/ log q * log p/ log r =1
→ p^{x} = 1/q ⟹ 1/p^{x} = 1/q
⟹ q = p^{x}
⟹ log q = log p^{x}
⟹ x log p = log q ⟹ x = log q/ log p → q^{y} = 1/r ⟹ 1/q^{y} = 1/r
⟹ q^{y} = r
⟹ y log q = log r
⟹ y = log r/ log q
→ r^{z} = 1/p ⟹ 1/r^{z} = 1/p
⟹ p = r^{z}
⟹ log r^{z} = log p
⟹ z log r = log p
⟹ z = log p/ log r
XYZ = log q/ log p * log r/ log q * log p/ log r =1
Question 7 
∠BCD∠BAD  
∠BAD+∠BCF
 
∠BAD+∠BCD  
∠CBA+ADC 
Question 7 Explanation:
→ ∠1 = ∠5 + ∠4 ………(i)
According to triangular property:
Angle of exterior = sum of interior angles
→ ∠4 = ∠3 + ∠2 ……….(ii)
By substituting (ii) in (i)
→ ∠1 = ∠5 + ∠3 + ∠2
→ ∠1 = ∠BCD
∠2 = ∠BAD
→ ∠BCD  ∠BAD = ∠1  ∠2
= ∠5 + ∠3 + ∠2  ∠2
= ∠ 5 + ∠3
= ∠DEC + ∠BFC
Question 8 
In a party, 60% of the invited guests are male and 40% are female. If 80% of the invited guests attended the party and if all the invited female guests attended, what would be the ratio of males to females among the attendees in the party?
2:3
 
1:1
 
3:2
 
2:1

Question 8 Explanation:
Let us consider total no. of guests = 100
→ 60% invited guests are males i.e., 60 males
→ 40% invited guests are females i.e., 40 females
→ 80% invited guests are attended i.e., total guests attended to a party = 80
→ All the invited females are attended then remaining people are males = 80 – 40 = 40 males
40 males : 40 females
1 : 1
→ 60% invited guests are males i.e., 60 males
→ 40% invited guests are females i.e., 40 females
→ 80% invited guests are attended i.e., total guests attended to a party = 80
→ All the invited females are attended then remaining people are males = 80 – 40 = 40 males
40 males : 40 females
1 : 1
Question 9 
In appreciation of the social improvements completed in a town, a wealthy philanthropist decided to gift Rs 750 to each male senior citizen in the town and Rs 1000 to each female senior citizen. Altogether, there were 300 senior citizens eligible for this gift. However, only 8/9th of the eligible men and 2/3rd of the eligible women claimed the gift. How much money (in Rupees) did the philanthropist give away in total?
1,50,000
 
2,00,000  
1,75,000  
1,51,000 
Question 9 Explanation:
Male senior citizen’s gift = Rs.750
Female senior citizen’s gift = Rs. 1000
No. of males = a say
No. of females = b say
Altogether no. of persons eligible for gift = 300
i.e., a+b = 300
Total amount be given = (8x/9 × 750) + (2y/3 × 1000)
= (2000x/3) + (2000y/3)
= 2000/3 (x+y)
= 2000/3 (300)
= 2,00,000
Female senior citizen’s gift = Rs. 1000
No. of males = a say
No. of females = b say
Altogether no. of persons eligible for gift = 300
i.e., a+b = 300
Total amount be given = (8x/9 × 750) + (2y/3 × 1000)
= (2000x/3) + (2000y/3)
= 2000/3 (x+y)
= 2000/3 (300)
= 2,00,000
Question 10 
A six sided unbiased die with four green faces and two red faces is rolled seven times. Which of the following combinations is the most likely outcome of the experiment?
Three green faces and four red faces.  
Four green faces and three red faces.  
Five green faces and two red faces.  
Six green faces and one red face. 
Question 10 Explanation:
→ Each side of a unbiased die can have equal probability i.e., = 1/6
→ If we roll a die for six time then we get 4 green faces and 2 red faces.
→ And if we roll for seventh time green face can have more probability to become a outcome.
→ Then most likely outcome is five green faces and two red faces.
→ If we roll a die for six time then we get 4 green faces and 2 red faces.
→ And if we roll for seventh time green face can have more probability to become a outcome.
→ Then most likely outcome is five green faces and two red faces.
Question 11 
3  
4  
5  
6 
Question 11 Explanation:
→ Correction in Explanation:
⇒(1λ)(2λ)2=0
⇒ λ^{2}3λ=0
λ=0, 3
So maximum is 3.
Question 12 
The postorder traversal of a binary tree is 8, 9, 6, 7, 4, 5, 2, 3, 1. The inorder traversal of the same tree is 8, 6, 9, 4, 7, 2, 5, 1, 3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is _______.
1  
2  
3  
4 
Question 12 Explanation:
Post – 8 9 6 7 4 5 2 3 1
In  8 6 9 4 7 2 5 1 3
Post: 8 9 6 7 4 5 2 3①⏟root
In: 8 6 9 4 7 2 5⏟left subtree 13⏟right subtree
Question 13 
Two people, P and Q, decide to independently roll two identical dice, each with 6 faces, numbered 1 to 6. The person with the lower number wins. In case of a tie, they roll the dice repeatedly until there is no tie. Define a trial as a throw of the dice by P and Q. Assume that all 6 numbers on each dice are equiprobable and that all trials are independent. The probability (rounded to 3 decimal places) that one of them wins on the third trial is __________.
0.021  
0.022  
0.023  
0.024 
Question 13 Explanation:
When two identical dice are rolled
⇾A person wins who gets lower number compared to other person.
⇾There could be “tie”, if they get same number. Favorable cases = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)}
Probability (tie) = 6/36 (when two dice are thrown, sample space = 6 × 6 = 36)
= 1/6
“Find the probability that one them coins in the third attempt
⇾Which means, first & second time it should be tie and third time it should not be tie
⇾ P (tie) * P (tie) * P (not tie)
⇒1/6* 1/6 * (1  1/6)
⇒(5/36×6)=0.138/6=0.023
⇾A person wins who gets lower number compared to other person.
⇾There could be “tie”, if they get same number. Favorable cases = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)}
Probability (tie) = 6/36 (when two dice are thrown, sample space = 6 × 6 = 36)
= 1/6
“Find the probability that one them coins in the third attempt
⇾Which means, first & second time it should be tie and third time it should not be tie
⇾ P (tie) * P (tie) * P (not tie)
⇒1/6* 1/6 * (1  1/6)
⇒(5/36×6)=0.138/6=0.023
Question 14 
In an EntityRelationship (ER) model, suppose R is a manytoone relationship from entity set E1 to entity set E2. Assume that E1 and E2 participate totally in R and that the cardinality of E1 is greater than the cardinality of E2.
Which one of the following is true about R?
Every entity in E1 is associated with exactly one entity in E2.
 
Some entity in E1 is associated with more than one entity in E2.
 
Every entity in E2 is associated with exactly one entity in E1.
 
Every entity in E2 is associated with at most one entity in E1.

Question 14 Explanation:
The M:1 relationship holds between two entities E1 and E2, in which each tuple from E2 is in relation with many tuples of E1. One tuple from E1 is in relation with only one tuple of E2. It is given that participation from both the sides is total and the cardinality of E1 is greater than E2.
Therefore, every entity E1 is associated with exactly one entity in E2.
Question 15 
Consider a process executing on an operating system that uses demand paging. The average time for a memory access in the system is M units if the corresponding memory page is available in memory and D units if the memory access causes a page fault. It has been experimentally measured that the average time taken for a memory access in the process is X units.
Which one of the following is the correct expression for the page fault rate experienced by the process?
(DM)/(XM)  
(XM)/(DM)  
(DX)/(DM)  
(XM)/(DX) 
Question 15 Explanation:
Let ‘P’ be page fault rate then, average memory access time
X=(1P)M+D×P
X=M∙PM+DP
(XM)=P(DM)
⇒P=(XM)/(DM)
Question 16 
Consider a longlived TCP session with an endtoend bandwidth of 1 Gbps (= 10^{9} bits/second). The session starts with a sequence number of 1234. The minimum time (in seconds, rounded to the closest integer) before this sequence number can be used again is _________.
33  
34  
35  
36 
Question 16 Explanation:
In TCP, Sequence number field is 32 bit, which means 2^{32} sequence number per byte are possible. Whatever be the starting sequence number the possible number will be 2^{32}bytes
The process of using all the sequence number and repeating a previously used sequence number.
The time taken to wrap around is called wrap around time:
Minimum Time = Wrap around time = Total number of bits in sequence number / Bandwidth = 2^{32}* 8 / 10^{9}= 34.35 == 34 (closest integer)
The process of using all the sequence number and repeating a previously used sequence number.
The time taken to wrap around is called wrap around time:
Minimum Time = Wrap around time = Total number of bits in sequence number / Bandwidth = 2^{32}* 8 / 10^{9}= 34.35 == 34 (closest integer)
Question 17 
A 32bit wide main memory unit with a capacity of 1 GB is built using 256M×4bit DRAM chips. The number of rows of memory cells in the DRAM chip is 214. The time taken to perform one refresh operation is 50 nanoseconds. The refresh period is 2 milliseconds. The percentage (rounded to the closest integer) of the time available for performing the memory read/write operations in the main memory unit is _________.
59%  
60%  
61%  
62% 
Question 17 Explanation:
Time taken to refresh one row = 50 ns
There are 2^14 rows, so time taken to refresh all the rows = 2^14 * 50ns = 0.82 milliseconds
It is given that total refresh period is 2ms. The refresh period contains the time to refresh all the rows and also the time to perform read/write operation.
So % time spent in refresh = (Time taken to refresh all rows / refresh period)*100 = (0.82 ms / 2ms)*100 = 41% So the % of time for read/write operation = 100  41 = 59%
It is given that total refresh period is 2ms. The refresh period contains the time to refresh all the rows and also the time to perform read/write operation.
So % time spent in refresh = (Time taken to refresh all rows / refresh period)*100 = (0.82 ms / 2ms)*100 = 41% So the % of time for read/write operation = 100  41 = 59%
Question 18 
1  
2  
3  
4 
Question 18 Explanation:
Chromatic number of the following graph is “3”
Question 19 
PIII, QIV, RII, SI  
PII, QI, RIV, SIII
 
PIV, QI, RII, SIII  
PIV, QI, RIII, SII 
Question 19 Explanation:
P. UDP Header’s Port Number  16 bits
Q. Ethernet MAC Address  48 bits
R. IPV6 Next Header  8 bits
S. TCP Header’s Sequence Number  32 bits
Q. Ethernet MAC Address  48 bits
R. IPV6 Next Header  8 bits
S. TCP Header’s Sequence Number  32 bits
Question 20 
θ(1), θ(1)  
θ(1), θ(n)  
θ(n), θ(1)  
θ(n), θ(n) 
Question 20 Explanation:
For insertion of node at the beginning of linked list only need manipulation of pointers so θ(1) time.
But if we have pointer to the tail of the list in order to delete it, we need the address of the 2nd last node which can be obtained by traversing the list which takes O(n) time.
But if we have pointer to the tail of the list in order to delete it, we need the address of the 2nd last node which can be obtained by traversing the list which takes O(n) time.
Question 21 
Consider a system with 3 processes that share 4 instances of the same resource type. Each process can request a maximum of K instances. Resource instances can be requested and released only one at a time. The largest value of K that will always avoid deadlock is _________.
2  
3  
4  
5 
Question 21 Explanation:
No. of process = 3
No. of resources = 4
Let’s distribute each process one less than maximum demands i.e., (k1) resources.
So, for three processes, 3(k – 1) resources.
For deadlock avoidance provide an additional resource to any one of the process.
∴ Total resources required to avoid deadlock in any case is 3(k – 1) + 1 = 3k – 2
Now this 3k – 2 should be less than equal to available no. of resources, i.e.,
3k – 2 ≤ 4
k ≤ 2
So maximum value of k = 2
No. of resources = 4
Let’s distribute each process one less than maximum demands i.e., (k1) resources.
So, for three processes, 3(k – 1) resources.
For deadlock avoidance provide an additional resource to any one of the process.
∴ Total resources required to avoid deadlock in any case is 3(k – 1) + 1 = 3k – 2
Now this 3k – 2 should be less than equal to available no. of resources, i.e.,
3k – 2 ≤ 4
k ≤ 2
So maximum value of k = 2
Question 22 
Only (ii) and (iii) are true
 
Only (i) and (iii) are true
 
Only (iv) is true
 
Only (i) and (iv) are true

Question 22 Explanation:
In Slowstart, the value of the Congestion Window will be increased by 1 MSS with each acknowledgement (ACK) received, and effectively doubling the window size each roundtrip time
Initially, TCP starts with cwnd of 1 MSS. On every ack, it increases cwnd by 1 MSS. That is, cwnd doubles every RTT. Initially sends 1 segment. On ack, sends 2 segments. After these 2 acks come back, sends 4 segments etc. TCP rate increases exponentially during slow start. Slow start continues till cwnd reaches threshold. After threshold is reached, cwnd increases more slowly, by one 1 MSS every RTT.
Initially, TCP starts with cwnd of 1 MSS. On every ack, it increases cwnd by 1 MSS. That is, cwnd doubles every RTT. Initially sends 1 segment. On ack, sends 2 segments. After these 2 acks come back, sends 4 segments etc. TCP rate increases exponentially during slow start. Slow start continues till cwnd reaches threshold. After threshold is reached, cwnd increases more slowly, by one 1 MSS every RTT.
Question 23 
Which one of the following statements is FALSE?
Contextfree grammar can be used to specify both lexical and syntax rules.
 
Type checking is done before parsing.  
Highlevel language programs can be translated to different Intermediate Representations.
 
Arguments to a function can be passed using the program stack.

Question 23 Explanation:
Type checking is done in semantic analysis phase after syntax analysis phase (i.e., after parsing)
Question 24 
Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?
k≥2^{n}
 
k≥n
 
k≤n^{2}  
k≤2^{n}

Question 24 Explanation:
The number of states in DFA is always less than equal to 2^{no. of states in NFA}. In other words, if number of states in NFA is “n” then the corresponding DFA have at most 2^{n} states.
Hence k ≤ 2^{n} is necessarily true.
Hence k ≤ 2^{n} is necessarily true.
Question 25 
QPTRS  
PTRSQ  
TRPQS  
QTPRS 
Question 25 Explanation:
The sequence of execution in the case of an interrupt while executing a process L is:
(Q). The processor finishes the execution of the current instruction
(P). The processor pushes the process status of L onto the control stack
(T). The processor loads the new PC value based on the interrupt
(R). The processor executes the interrupt service routine
(S). The processor pops the process status of L from the control stack
This is the sequence because when a process is in the middle of execution if an interrupt comes then that process execution is completed then the interrupt is serviced.
(Q). The processor finishes the execution of the current instruction
(P). The processor pushes the process status of L onto the control stack
(T). The processor loads the new PC value based on the interrupt
(R). The processor executes the interrupt service routine
(S). The processor pops the process status of L from the control stack
This is the sequence because when a process is in the middle of execution if an interrupt comes then that process execution is completed then the interrupt is serviced.
Question 26 
Let ⊕ and ⊙ denote the Exclusive OR and Exclusive NOR operations, respectively. Which one of the following is NOT CORRECT?
Question 26 Explanation:
Question 27 
Let G be a finite group on 84 elements. The size of a largest possible proper subgroup of G is _________.
41  
42  
43  
44 
Question 27 Explanation:
Lagranges Theorem:
For any group ‘G’ with order ‘n’, every subgroup ‘H’ has order ‘k’ such that ‘n’ is divisible by ‘k’.
Solution:
Given order n = 84
Then the order of subgroups = {1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84}
As per the proper subgroup definition, it should be “42”.
Question 28 
Which one of the following is a closed form expression for the generating function of the sequence {a_{n}}, where a_{n}=2n+3 for all n=0,1,2,…?
3/(1x)^{2}  
3x/(1x)^{2}  
2x/(1x)^{2}  
3x/(1x)^{2} 
Question 28 Explanation:
Question 29 
The set of all recursively enumerable languages is
closed under complementation.
 
closed under intersection.
 
a subset of the set of all recursive languages.
 
an uncountable set.

Question 29 Explanation:
Recursive enumerable languages are closed under intersection. Recursive enumerable languages are not closed under Complementation. Recursive enumerable languages are a countable set, as every recursive enumerable language has a corresponding Turing Machine and set of all Turing Machine is countable. Recursive languages are subset of recursive enumerable languages.
Question 30 
2  
3  
4  
5 
Question 30 Explanation:
Let,
Now lets draw characteristic table,
D_{1} = Q_{0}
D_{0} = in
Now lets draw characteristic table,
D_{1} = Q_{0}
D_{0} = in
Question 32 
Query 1
 
Query 2  
Query 3  
Query 4 
Question 32 Explanation:
Given two tables are,
Book (isbn, bname)
Stock(isbn, copies)
isbnis a primary key of Book and isbn is a foreign key of stock referring to Book table.
For example:
Query 1: INNER JOIN keyword selects records that have matching values in both tables (Book and Stock).
So, the result of Query 1 is,
Query 2: The LEFT OUTER JOIN keyword returns all records from the left table (Book) and the matched records from the right table (Stock). The result is NULL from the right side, if there is no match.
So, the result of Query 2 is,
Query 3: The RIGHT OUTER JOIN keyword returns all records from the right table (Stock), and the matched records from the left table(BOOK). The result is NULL from the left side, when there is no match.
Query 4: The FULL OUTER JOIN keyword return all records when there is a match in either left (Book) or right (Stock) table records.
So, the result of Query 4 is,
Therefore, from the result of above four queries, a superset of the outputs of the Query 1, Query 2 and Query 3 is Query 4.
Note: If we take isbn as a primary key in both the tables Book and Stock and foreign key, in one of the tables then also will get option (D) as the answer.
Query 1: INNER JOIN keyword selects records that have matching values in both tables (Book and Stock).
So, the result of Query 1 is,
Query 2: The LEFT OUTER JOIN keyword returns all records from the left table (Book) and the matched records from the right table (Stock). The result is NULL from the right side, if there is no match.
So, the result of Query 2 is,
Query 3: The RIGHT OUTER JOIN keyword returns all records from the right table (Stock), and the matched records from the left table(BOOK). The result is NULL from the left side, when there is no match.
Query 4: The FULL OUTER JOIN keyword return all records when there is a match in either left (Book) or right (Stock) table records.
So, the result of Query 4 is,
Therefore, from the result of above four queries, a superset of the outputs of the Query 1, Query 2 and Query 3 is Query 4.
Note: If we take isbn as a primary key in both the tables Book and Stock and foreign key, in one of the tables then also will get option (D) as the answer.
Question 34 
I and II only  
II and III only  
I and III only  
I, II and III 
Question 34 Explanation:
RISC processor has all the three given characteristics. So option D is the correct answer.
Question 35 
0, c  
0, a+2  
‘0’, ‘a+2’  
‘0’, ‘c’ 
Question 35 Explanation:
char x = ‘a’+2;
The x variable here stores a character ‘c’ in it. Because + 2 will increment ascii value of a from 92 to 95. Hence the structure p contains 3 character values and they are ‘1’, ‘0’, and ‘c’. q is a pointer pointing to structure p. Hence q is pointing to ‘1’, q+1 pointing to ‘0’ and q+2 pointing to ‘c’. Option d cannot be correct, as though they are characters, printf will not print them in single quotes.
The x variable here stores a character ‘c’ in it. Because + 2 will increment ascii value of a from 92 to 95. Hence the structure p contains 3 character values and they are ‘1’, ‘0’, and ‘c’. q is a pointer pointing to structure p. Hence q is pointing to ‘1’, q+1 pointing to ‘0’ and q+2 pointing to ‘c’. Option d cannot be correct, as though they are characters, printf will not print them in single quotes.
Question 36 
The size of the physical address space of a processor is 2^{P} bytes. The word length is 2^{W} bytes. The capacity of cache memory is 2^{N} bytes. The size of each cache block is 2^{M} words. For a Kway setassociative cache memory, the length (in number of bits) of the tag field is
PNlog_{2}K  
PN+log_{2}K
 
PNMWlog_{2}K  
PNMW+log_{2}K 
Question 36 Explanation:
Physical memory is of size 2^{P} bytes.
Each word is of size 2^{W} bytes.
Number of words in physical memory = 2^{(PW)}
So the physical address is PW bits
Cache size is 2^{N} bytes.
Number of words in the cache = 2^{(NW)}
Block size is 2^{M} words
No. of blocks in the cache = 2^{(NWM)}
Since it is kway set associative cache, each set in the cache will have k blocks.
No. of sets = 2^{(NWM )} / k
SET bits = NWMlogk
Block offset = M
TAG bits = PW(NMWlogk)M = PWN+M+W+logkM = P  N + logk
Each word is of size 2^{W} bytes.
Number of words in physical memory = 2^{(PW)}
So the physical address is PW bits
Cache size is 2^{N} bytes.
Number of words in the cache = 2^{(NW)}
Block size is 2^{M} words
No. of blocks in the cache = 2^{(NWM)}
Since it is kway set associative cache, each set in the cache will have k blocks.
No. of sets = 2^{(NWM )} / k
SET bits = NWMlogk
Block offset = M
TAG bits = PW(NMWlogk)M = PWN+M+W+logkM = P  N + logk
Question 37 
Hi Bye Bye Hi  
Hi Bye Hi Bye  
Bye Hi Hi Bye  
Bye Hi Bye Hi 
Question 37 Explanation:
The first call to the function ‘func1(str1, str2);’ is call by value. Hence, any change in the formal parameters are NOT reflected in actual parameters. Hence, str1 points at “hi” and str2 points at “bye”.
The second call to the function ‘func2(&str1, &str2);’ is call by reference. Hence, any change in formal parameters are reflected in actual parameters. Hence, str1 now points at “bye” and str2 points at “hi”.
Hence answer is “hi bye bye hi”.
The second call to the function ‘func2(&str1, &str2);’ is call by reference. Hence, any change in formal parameters are reflected in actual parameters. Hence, str1 now points at “bye” and str2 points at “hi”.
Hence answer is “hi bye bye hi”.
Question 38 
4  
5  
6  
7 
Question 38 Explanation:
Here, X=5 because it is having maximum number of spanning trees. If X=5 then the total number of MWSTs are 4.
If r = 1
If r = 2
If r = 3
If r = 4
If r = 5
If r = 2
If r = 3
If r = 4
If r = 5
Question 39 
A processor has 16 integer registers (R0, R1, …, R15) and 64 floating point registers (F0, F1, …, F63). It uses a 2byte instruction format. There are four categories of instructions: Type1, Type2, Type3 and Type4.Type1 category consists of four instructions, each with 3 integer register operands (3Rs). Type2 category consists of eight instructions, each with 2 floating point register operands (2Fs). Type3 category consists of fourteen instructions, each with one integer register operand and one floating point register operand (1R+1F). Type4 category consists of N instructions, each with a floating point register operand (1F).
The maximum value of N is ________.
32  
33  
34  
35 
Question 39 Explanation:
nstruction size = 2−byte. So, total number of instruction encodings =2^{16}
There are 16 possible integer registers, so no. of bits required for an integer operand = 4
There are 64 possible floating point registers, so no. of bits required for a floating point operand = 6
Type1 instructions:
There are 4 type1 instructions and each takes 3 integer operands.
No. of encodings consumed by type1 = 4 × 2^{4} × 2^{4} × 2^{4} =2^{14}.
Type2 instructions:
There are 8 type2 instructions and each takes 2 floating point operands.
No. of encodings consumed by Type2 instructions = 8× 2^{6} x 2^{6} =2^{15}.
Type3 instructions:
There are 14 type3 instructions and each takes one integer operand and one floating point operand.
No. of encodings consumed by Type3 instructions =14×2^{4} x 2^{6}=14336.
So, no. of encodings left for Type4 = 2^{16}−(2^{14}+2^{15}+14336)=2048.
Since type4 instructions take one floating point register, no. of different instructions of Type4 = 2048 / 64 =32.
There are 16 possible integer registers, so no. of bits required for an integer operand = 4
There are 64 possible floating point registers, so no. of bits required for a floating point operand = 6
Type1 instructions:
There are 4 type1 instructions and each takes 3 integer operands.
No. of encodings consumed by type1 = 4 × 2^{4} × 2^{4} × 2^{4} =2^{14}.
Type2 instructions:
There are 8 type2 instructions and each takes 2 floating point operands.
No. of encodings consumed by Type2 instructions = 8× 2^{6} x 2^{6} =2^{15}.
Type3 instructions:
There are 14 type3 instructions and each takes one integer operand and one floating point operand.
No. of encodings consumed by Type3 instructions =14×2^{4} x 2^{6}=14336.
So, no. of encodings left for Type4 = 2^{16}−(2^{14}+2^{15}+14336)=2048.
Since type4 instructions take one floating point register, no. of different instructions of Type4 = 2048 / 64 =32.
Question 40 
Assume that multiplying a matrix G_{1} of dimension p×q with another matrix G_{2} of dimension q×r requires pqr scalar multiplications. Computing the product of n matrices G_{1}G_{2}G_{3}…G_{n} can be done by parenthesizing in different ways. Define G_{i}G_{i+1} as an explicitly computed pair for a given parenthesization if they are directly multiplied. For example, in the matrix multiplication chain G_{1}G_{2}G_{3}G_{4}G_{5}G_{6} using parenthesization(G_{1}(G_{2}G_{3}))(G_{4}(G_{5}G_{6})), G_{2}G_{3} and G_{5}G_{6} are the only explicitly computed pairs.
Consider a matrix multiplication chain F_{1}F_{2}F_{3}F_{4}F_{5}, where matrices F_{1}, F_{2}, F_{3}, F_{4} and F_{5} are of dimensions 2×25, 25×3, 3×16, 16×1 and 1×1000, respectively. In the parenthesization of F_{1}F_{2}F_{3}F_{4}F_{5} that minimizes the total number of scalar multiplications, the explicitly computed pairs is/ are
F_{1}F_{2} and F_{3}F_{4} only
 
F_{2}F_{3} only
 
F_{3}F_{4} only  
F_{1}F_{2} and F_{4}F_{5} only

Question 40 Explanation:
→ As per above information, the total number of scalar multiplications are 2173.
→ Optimal Parenthesization is: ((F_{1}(F_{2}(F_{3} F_{4})))F_{5})
→ But according to the problem statement we are only considering F_{3}, F_{4} explicitly computed pairs.
→ Optimal Parenthesization is: ((F_{1}(F_{2}(F_{3} F_{4})))F_{5})
→ But according to the problem statement we are only considering F_{3}, F_{4} explicitly computed pairs.
Question 41 
$has higher precedence and is left associative; # is right associative
 
#has higher precedence and is left associative; $ is right associative
 
$has higher precedence and is left associative; # is left associative  
#has higher precedence and is right associative; $ is left associative

Question 41 Explanation:
Since $ will be evaluated before # so $ has higher precedence and the left $ i.e., in b$c$d the left “$” (i.e., b$c) will be evaluated first so it is left associative, whereas # is right associative (as in d#e#f) , the right one (i.e., e#f) will be evaluated first.
Question 42 
P: full, Q: full, R: empty, S: empty
 
P: empty, Q: empty, R: full, S: full
 
P: full, Q: empty, R: empty, S: full
 
P: empty, Q: full, R: full, S: empty

Question 42 Explanation:
P=full, Q=empty, R:empty, S=full
Initial: mutex = 1
empty = 0
full = N
Initial: mutex = 1
empty = 0
full = N
Question 43 
There exists at least one model of φ with universe of size less than or equal to 3.
 
There exists no model of φ with universe of size less than or equal to 3.
 
There exists no model of φ with universe of size greater than 7.  
Every model of φ has a universe of size equal to 7.

Question 43 Explanation:
φ=∃s∃t∃u∀v∀w∀x∀y ψ (s,t,u,v,w,x,y)
"∃"there exists quantifier decides whether a sentence belong to the model or not.
i.e., ~∃ will make it not belong to the model. ①We have ‘7’ elements in the universe, So max. size of universe in a model= ‘7’
②There are three '∃' quantifiers, which makes that a model have atleast “3” elements. So, min. size of universe in model = ‘7’.
(A) is False because: ②
(B) is true
(C) is false because of ①
(D) is false, because these all models with size {3 to 7} not only ‘7’.
i.e., ~∃ will make it not belong to the model. ①We have ‘7’ elements in the universe, So max. size of universe in a model= ‘7’
②There are three '∃' quantifiers, which makes that a model have atleast “3” elements. So, min. size of universe in model = ‘7’.
(A) is False because: ②
(B) is true
(C) is false because of ①
(D) is false, because these all models with size {3 to 7} not only ‘7’.
Question 44 
I only  
II only  
Both I and II  
Neither I nor II 
Question 44 Explanation:
I. Undirected graph do not have cross edges in DFS. But can have cross edges in directed graph. Hence True.
II. Just draw a triangle ABC. Source is A. Vertex B and C are at same level at distance 1. There is an edge between B and C too. So here i  j = 1  1 = 0.
Hence, False.
II. Just draw a triangle ABC. Source is A. Vertex B and C are at same level at distance 1. There is an edge between B and C too. So here i  j = 1  1 = 0.
Hence, False.
Question 45 
4  
5  
6  
40 
Question 45 Explanation:
Since 240 is the input, so first loop will make j=40.
Next for loop will divide j value (which is 40) by 2, each time until j>1.
j loop starts:
j=40 & sum=1
j=20 & sum=2
j=10 & sum=3
j=5 & sum=4
j=2 & sum=5
j=1 & break
So sum = 5.
Next for loop will divide j value (which is 40) by 2, each time until j>1.
j loop starts:
j=40 & sum=1
j=20 & sum=2
j=10 & sum=3
j=5 & sum=4
j=2 & sum=5
j=1 & break
So sum = 5.
Question 46 
85  
86  
87  
88 
Question 46 Explanation:
From the above 36 no. question we are getting →
A storage disk  4 platters(0,1,2 & 3), Cylinder  200 (0,1, …, 199) , 256 sector per track. In the above question the disk requests are given in the form of .
In SSTF (Shortest Seek Time First) Disk Scheduling algo, requests having shortest seek time are executed first. So, the seek time of every request is calculated in advance in queue and then they are scheduled according to their calculated seek time. Head is positioned at 80 and moving towards higher cylinder no.
Head Movement in SSTF = (86 – 80) + (86 – 72) + (134 – 72) + (134 – 16) = 200
P_{1}: Power dissipated by 200 movements = 0.2 * 200 = 40 mW
Power dissipated in reversing Head direction once = 15 mW
No. of times Head changes its direction = 3 P_{2}: Power dissipated in reversing Head direction = 3 * 15 = 45 mW
Total power consumption is P_{1} + P_{2} = 85 mW
In SSTF (Shortest Seek Time First) Disk Scheduling algo, requests having shortest seek time are executed first. So, the seek time of every request is calculated in advance in queue and then they are scheduled according to their calculated seek time. Head is positioned at 80 and moving towards higher cylinder no.
Head Movement in SSTF = (86 – 80) + (86 – 72) + (134 – 72) + (134 – 16) = 200
P_{1}: Power dissipated by 200 movements = 0.2 * 200 = 40 mW
Power dissipated in reversing Head direction once = 15 mW
No. of times Head changes its direction = 3 P_{2}: Power dissipated in reversing Head direction = 3 * 15 = 45 mW
Total power consumption is P_{1} + P_{2} = 85 mW
Question 47 
None of (i), (ii), (iii), (iv) can be exactly represented
 
Only (ii) cannot be exactly represented
 
Only (iii) and (iv) cannot be exactly represented
 
Only (i) and (ii) cannot be exactly represented

Question 47 Explanation:
(i) (31.5)_{10}=(11111.100)_{2}
=2^{4}+2^{3}+2^{2}+2^{1}+2^{0}+2^{1}
=16+8+4+2+1+0.5
=(31.5)_{10}
(ii) (0.875)_{10}=(00000.111)_{2}
=2^{1}+2^{2}+2^{3}
=0.5+0.25+0.125
=(0.875)_{10}
(iii) (12.100)_{10}
It is not possible to represent (12.100)_{10}
(iv)(3.001)_{10} It is not possible to represent (3.001)_{10}
=16+8+4+2+1+0.5
=(31.5)_{10}
(ii) (0.875)_{10}=(00000.111)_{2}
=2^{1}+2^{2}+2^{3}
=0.5+0.25+0.125
=(0.875)_{10}
(iii) (12.100)_{10}
It is not possible to represent (12.100)_{10}
(iv)(3.001)_{10} It is not possible to represent (3.001)_{10}
Question 48 
The system is in safe state.
 
The system is not in safe state, but would be safe if one more instance of E were available.  
The system is not in safe state, but would be safe if one more instance of F were available.
 
The system is not in safe state, but would be safe if one more instance of G were available.

Question 48 Explanation:
〈E,F,G〉=〈3,3,0〉
Safe sequence: 〈P_{0}, P_{2}, P_{1}, P_{3}〉
P_{0}: P_{0}can be allotted 〈3,3,0〉. After completion Available = 〈4,3,1〉
P_{2}: P_{2}can be allotted 〈0,3,0〉. After completion Available = 〈5,3,4〉
P_{1}: P_{1}can be allotted 〈1,0,2〉. After completion Available = 〈6,4,6〉
P_{3}: P_{3}can be allotted 〈3,4,1〉. After completion Available = 〈8,4,6〉
Safe sequence: 〈P_{0}, P_{2}, P_{1}, P_{3}〉
P_{0}: P_{0}can be allotted 〈3,3,0〉. After completion Available = 〈4,3,1〉
P_{2}: P_{2}can be allotted 〈0,3,0〉. After completion Available = 〈5,3,4〉
P_{1}: P_{1}can be allotted 〈1,0,2〉. After completion Available = 〈6,4,6〉
P_{3}: P_{3}can be allotted 〈3,4,1〉. After completion Available = 〈8,4,6〉
Question 49 
Schema I  
Schema II  
Schema III  
Schema IV 
Question 49 Explanation:
Schema I:
Registration (rollno, courses) rollno → courses
For the given schema Registration ‘rollno’ is a primary key.
Leftside of the functional dependency is a superkey so, Registration is in BCNF.
Schema II:
Registrstion (rollno, courseid, email)
rollno, courseid → email
email → rollno
From the given schema the candidate key is (rollno + courseid).
There is no part of the key in the left hand of the FD’s so, it is in 2NF.
In the FD email→rollno, email is nonprime attribute but rollno is a prime attribute. So, it is not a transitive dependency. No transitive dependencies so, the schema is in 3NF.
But in the second FD email→rollno, email is not a superkey. So, it is violating BCNF.
Hence, the schema Registration is in 3NF but not in BCNF.
Schema III:
Registration (rollno, courseid, marks, grade)
rollno, courseid → marks, grade
marks → grade
For the schema the candidate key is (rollno + courseid).
There are no part of the keys are determining nonprime attributes. So, the schema is in 2NF. In the FD marks → grade, both the attributes marks and grade are nonprime. So, it is a transitive dependency. The FD is violating 3NF.
The schema Registration is in 2NF but not in 3NF.
Schema IV:
Registration (rollno, courseid, credit)
rollno, courseid → credit
courseid → credit
The candidate key is (rollno + courseid).
In the FD, courseid → credit, courseid is part of the key (prime attribute) and credit is nonprime. So, it is a partial dependency. The schema is violating 2NF.
Registration (rollno, courses) rollno → courses
For the given schema Registration ‘rollno’ is a primary key.
Leftside of the functional dependency is a superkey so, Registration is in BCNF.
Schema II:
Registrstion (rollno, courseid, email)
rollno, courseid → email
email → rollno
From the given schema the candidate key is (rollno + courseid).
There is no part of the key in the left hand of the FD’s so, it is in 2NF.
In the FD email→rollno, email is nonprime attribute but rollno is a prime attribute. So, it is not a transitive dependency. No transitive dependencies so, the schema is in 3NF.
But in the second FD email→rollno, email is not a superkey. So, it is violating BCNF.
Hence, the schema Registration is in 3NF but not in BCNF.
Schema III:
Registration (rollno, courseid, marks, grade)
rollno, courseid → marks, grade
marks → grade
For the schema the candidate key is (rollno + courseid).
There are no part of the keys are determining nonprime attributes. So, the schema is in 2NF. In the FD marks → grade, both the attributes marks and grade are nonprime. So, it is a transitive dependency. The FD is violating 3NF.
The schema Registration is in 2NF but not in 3NF.
Schema IV:
Registration (rollno, courseid, credit)
rollno, courseid → credit
courseid → credit
The candidate key is (rollno + courseid).
In the FD, courseid → credit, courseid is part of the key (prime attribute) and credit is nonprime. So, it is a partial dependency. The schema is violating 2NF.
Question 50 
2  
3  
4  
5 
Question 50 Explanation:
The regular expression for L_{1} : ϵ + 0 (00)*
Now L_{1}^{0}= ϵ and L_{1}^{1}= ϵ . (ϵ+0 (00)*) = ϵ + 0 (00)* = L_{1}
Now L_{1}^{2}= L_{1}^{1} .
L_{1} = L_{1} .
L_{1} = (ϵ + 0 (00)*) (ϵ + 0 (00)*)
= (ϵ + 0 (00)* + 0(00)* + 0(00)*0(00)*)
= (ϵ + 0 (00)* + 0(00)*0(00)* ) = 0*
As it will contain epsilon + odd number of zero + even number of zero, hence it is 0*
Now L_{1}^{3}= L_{1}^{2} .
L_{1} = 0* (ϵ + 0 (00)*) = 0* + 0*0(00)* = 0*
Hence L_{1}^{2}= L_{1}^{3}
Or L_{1}^{2} = L_{1}^{2+1} ,
hence the smallest k value is 2.
Now L_{1}^{0}= ϵ and L_{1}^{1}= ϵ . (ϵ+0 (00)*) = ϵ + 0 (00)* = L_{1}
Now L_{1}^{2}= L_{1}^{1} .
L_{1} = L_{1} .
L_{1} = (ϵ + 0 (00)*) (ϵ + 0 (00)*)
= (ϵ + 0 (00)* + 0(00)* + 0(00)*0(00)*)
= (ϵ + 0 (00)* + 0(00)*0(00)* ) = 0*
As it will contain epsilon + odd number of zero + even number of zero, hence it is 0*
Now L_{1}^{3}= L_{1}^{2} .
L_{1} = 0* (ϵ + 0 (00)*) = 0* + 0*0(00)* = 0*
Hence L_{1}^{2}= L_{1}^{3}
Or L_{1}^{2} = L_{1}^{2+1} ,
hence the smallest k value is 2.
Question 51 
Consider a simple communication system where multiple nodes are connected by a shared broadcast medium (like Ethernet or wireless). The nodes in the system use the following carriersense based medium access protocol. A node that receives a packet to transmit will carriersense the medium for 5 units of time. If the node does not detect any other transmission in this duration, it starts transmitting its packet in the next time unit. If the node detects another transmission, it waits until this other transmission finishes, and then begins to carriersense for 5 time units again. Once they start to transmit, nodes do not perform any collision detection and continue transmission even if a collision occurs. All transmissions last for 20 units of time. Assume that the transmission signal travels at the speed of 10 meters per unit time in the medium.
Assume that the system has two nodes P and Q, located at a distance d meters from each other. P starts transmitting a packet at time t=0 after successfully completing its carriersense phase. Node Q has a packet to transmit at time t=0 and begins to carriersense the medium.
The maximum distance d (in meters, rounded to the closest integer) that allows Q to successfully avoid a collision between its proposed transmission and P’s ongoing transmission is ___________.
50  
51  
52  
53 
Question 51 Explanation:
Node senses the medium for 5 unit time. it means, any packet which arrives within 5 unit will be sensed and keep the channel busy. Now signal travels at the speed of 10 meters per unit time. Therefore, in 5 unit time, it can travel a maximum distance (d) of 50 m (5*10), which allows the receiver (Q) to sense that the channel is busy.
Question 52 
T_{1}T_{2}T_{3}
 
T_{1}T_{1}T_{3}  
T_{2}T_{1}T_{3}  
T_{3}T_{3} 
Question 52 Explanation:
a? means either 0 or 1 occurrence of “a”, so we can write T_{1}, T_{2} and T_{3} as:
T_{1} : (b+c)*a + a(b+c)*a
T_{2} : (a+c)*b + b(a+c)*b
T_{3} : (b+a)*c + c(b+a)*c
Now the string is: bbaacabc
Please NOTE: Token that matches the longest possible prefix
We can observe that the longest possible prefix in string is : bbaac which can be generated by T_{3}
After prefix we left with “abc” which is again generated by T_{3} (as longest possible prefix)
So answer is T_{3}T_{3}
T_{1} : (b+c)*a + a(b+c)*a
T_{2} : (a+c)*b + b(a+c)*b
T_{3} : (b+a)*c + c(b+a)*c
Now the string is: bbaacabc
Please NOTE: Token that matches the longest possible prefix
We can observe that the longest possible prefix in string is : bbaac which can be generated by T_{3}
After prefix we left with “abc” which is again generated by T_{3} (as longest possible prefix)
So answer is T_{3}T_{3}
Question 53 
0.60  
0.61  
0.62  
0.63 
Question 53 Explanation:
The first entry denotes that if Guwahati has high temperature (H _{G} ) then the probability that Delhi also having a high temperature (H _{D} ) is 0.40.
P (H _{D} / H _{G} )= 0.40 We need to find out the probability that Guwahati has high temperature.
Given that Delhi has high temperature (P(H _{G} / H _{D} )).
P (H _{D} / H_{G} ) = P(H _{G} ∩ H _{D} ) / P(H _{D} )
=0.2×0.4 / 0.2×0.4+0.5×0.1+0.3×0.01
=0.60
Question 54 
10230  
10231  
10232  
10233 
Question 54 Explanation:
#include
int count=0;
Count(x,y){
if(y!=1){
if(x!=1){
printf("*");
count = count +1;
Count(x/2,y);
}
else{
y=y1;
Count(1024,y);
}
}
}
void main()
{
Count(1024,1024);
printf("\n%d\n",count);
}
Count ( ) is called recursively for every (y = 1023) & for every y, Count ( ) is called (x = 10) times = 1023 × 10 = 10230
int count=0;
Count(x,y){
if(y!=1){
if(x!=1){
printf("*");
count = count +1;
Count(x/2,y);
}
else{
y=y1;
Count(1024,y);
}
}
}
void main()
{
Count(1024,1024);
printf("\n%d\n",count);
}
Count ( ) is called recursively for every (y = 1023) & for every y, Count ( ) is called (x = 10) times = 1023 × 10 = 10230
Question 55 
I and IV only  
I and II only
 
II and III only  
II and IV only 
Question 55 Explanation:
i) a^{m} b^{n} c^{p} d^{q}  m+p = n+q,
mn = qp
First we will push a’s in the stack then we will pop a’s after watching b’s. Then some of a’s might left in the stack. Now we will push c’s in the stack and then pop c’s by watching d’s.
And then the remaining a’s will be popped off the stack by watching some more d’s. And if no d’s is remaining and the stack is empty then the language is accepted by CFG.
ii) a^{m} b^{n} c^{p} d^{q}  m=n, p=q
Push a’s in stack. Pop a’s watching b’s. Now push c’s in stack. Pop c’s watching d’s.
So it is context free language.
iii) a^{m} b^{n} c^{p} d^{q}  m=n=p & p≠q
Here three variables are dependent on each other. So not context free.
iv) Not context free because comparison in stack can’t be done through multiplication operation.
First we will push a’s in the stack then we will pop a’s after watching b’s. Then some of a’s might left in the stack. Now we will push c’s in the stack and then pop c’s by watching d’s.
And then the remaining a’s will be popped off the stack by watching some more d’s. And if no d’s is remaining and the stack is empty then the language is accepted by CFG.
ii) a^{m} b^{n} c^{p} d^{q}  m=n, p=q
Push a’s in stack. Pop a’s watching b’s. Now push c’s in stack. Pop c’s watching d’s.
So it is context free language.
iii) a^{m} b^{n} c^{p} d^{q}  m=n=p & p≠q
Here three variables are dependent on each other. So not context free.
iv) Not context free because comparison in stack can’t be done through multiplication operation.
Question 56 
Only I and II are undecidable
 
Only III is undecidable  
Only II and IV are undecidable  
Only I, II and III are undecidable

Question 56 Explanation:
IV is trivial property, as every regular language is CFL also, so a language which has NFA must be regular and for every regular language we can have a deterministic PDA (as every regular language is DCFL).
I, II and III is undecidable.
I, II and III is undecidable.
Question 57 
σ_{B<5}(r ⨝s)
 
σ_{B<5}(r LOJ s)
 
r LOJ (σ_{B<5}(s))
 
σ_{B<5}(r)LOJ s 
Question 57 Explanation:
Consider the following relations r(A, B) and S(B, C), where S.B is a primary key and r.B is a foreign key referencing S.B.
Consider the following tables without NULL values.
Q: r⨝(σ_{B}<5(S))
The result of σ_{B<5}(S) is
The result of σ_{B<5}(S) is
Option (A):
The result of r⨝S is
The result of σ_{B<5}(r⨝S) is
Option (B):
The result of r LOJ S is The result of σ_{B<5}(r LOJ S) is
Option (C):
The result of σ_{B<5}(S) is
Now, the result of r LOJ(σ_{B<5}(S))
Option (D): The result of σ_{B<5}(r) is Now, the result of σ_{B<5}(r) LOJ S is
Therefore, from the output of above four options, the results of options, the results of options (A), (B) and (D) are equivalent to Q.
Consider the following tables without NULL values.
Q: r⨝(σ_{B}<5(S))
The result of σ_{B<5}(S) is
The result of σ_{B<5}(S) is
Option (A):
The result of r⨝S is
The result of σ_{B<5}(r⨝S) is
Option (B):
The result of r LOJ S is The result of σ_{B<5}(r LOJ S) is
Option (C):
The result of σ_{B<5}(S) is
Now, the result of r LOJ(σ_{B<5}(S))
Option (D): The result of σ_{B<5}(r) is Now, the result of σ_{B<5}(r) LOJ S is
Therefore, from the output of above four options, the results of options, the results of options (A), (B) and (D) are equivalent to Q.
Question 58 
Consider an IP packet with a length of 4,500 bytes that includes a 20byte IPv4 header and a 40byte TCP header. The packet is forwarded to an IPv4 router that supports a Maximum Transmission Unit (MTU) of 600 bytes. Assume that the length of the IP header in all the outgoing fragments of this packet is 20 bytes. Assume that the fragmentation offset value stored in the first fragment is 0.
The fragmentation offset value stored in the third fragment is __________.
144  
145  
146  
147 
Question 58 Explanation:
MTU = 600 bytes, IP header = 20 bytes
Therefore Payload = 600  20 = 580 bytes. As we know fragment size should be multiple of 8 but 580 bytes is not a multiple of 8, therefore fragment size is 576 bytes
Offset value of k^{th} fragment = Fragment size *( k^{th}fragment  1) / scaling factor
Offset value of third fragment = 576 * (31) / 8 = 144
Therefore Payload = 600  20 = 580 bytes. As we know fragment size should be multiple of 8 but 580 bytes is not a multiple of 8, therefore fragment size is 576 bytes
Offset value of k^{th} fragment = Fragment size *( k^{th}fragment  1) / scaling factor
Offset value of third fragment = 576 * (31) / 8 = 144
Question 59 
Q and S only  
P and S only  
P and R only  
P, Q and S only

Question 59 Explanation:
Set of rational numbers are countable. It is proved by various methods in literature.
Set of functions from {0,1} to N is countable as it has one to one correspondence to N.
Set of functions from N to {0,1} is uncountable, as it has one to one correspondence to set of real numbers between (0 and 1).
Set of finite subsets of N is countable.
Set of functions from {0,1} to N is countable as it has one to one correspondence to N.
Set of functions from N to {0,1} is uncountable, as it has one to one correspondence to set of real numbers between (0 and 1).
Set of finite subsets of N is countable.
Question 60 
16  
17  
18  
19 
Question 60 Explanation:
First sort value/weight in descending order as per the question:
V_{opt} is clearly = 60
For V_{greedy} use the table (Do not take the fraction as per the question),
Item 4 picked,
Profit = 24
Remaining weight = 11 – 2 = 9
Next item 3 picked (item 1 cannot be picked since its capacity is greater than available capacity),
Profit = 24+20 = 44
Remaining capacity = 9 – 4 = 5
Now no item can be picked with available capacity.
So V_{greedy} = 44
∴ V_{opt} –V_{greedy} = 60 – 44 = 16
V_{opt} is clearly = 60
For V_{greedy} use the table (Do not take the fraction as per the question),
Item 4 picked,
Profit = 24
Remaining weight = 11 – 2 = 9
Next item 3 picked (item 1 cannot be picked since its capacity is greater than available capacity),
Profit = 24+20 = 44
Remaining capacity = 9 – 4 = 5
Now no item can be picked with available capacity.
So V_{greedy} = 44
∴ V_{opt} –V_{greedy} = 60 – 44 = 16
Question 61 
Only I and III are necessarily true
 
Only II is necessarily true  
Only I and II are necessarily true  
Only II and III are necessarily true

Question 61 Explanation:
The eigen vector of ‘p’ are multiple of [1 4 ]
Though the multiple of a vector represents same vector, and each eigen vector has distinct eigen value, we can conclude that ‘p’ has repeated eigen value.
If the unique eigen value corresponds to an eigen vector e, but the repeated eigen value corresponds to an entire plane, then the matrix can be diagonalized, using ‘e’ together with any two vectors that lie in plane. But, if all eigen values are repeated, then the matrix cannot be diagonalized unless it is already diagonal.
So (III) holds correct.
A diagonal matrix can have inverse, So (I) is false.
Then (II), (III) are necessarily True.
Though the multiple of a vector represents same vector, and each eigen vector has distinct eigen value, we can conclude that ‘p’ has repeated eigen value.
If the unique eigen value corresponds to an eigen vector e, but the repeated eigen value corresponds to an entire plane, then the matrix can be diagonalized, using ‘e’ together with any two vectors that lie in plane. But, if all eigen values are repeated, then the matrix cannot be diagonalized unless it is already diagonal.
So (III) holds correct.
A diagonal matrix can have inverse, So (I) is false.
Then (II), (III) are necessarily True.
Question 62 
The number of possible minheaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is ___________.
80  
81  
82  
83 
Question 62 Explanation:
> We have 7 distinct integers {1,2,3,4,5,6,7} and sort it
> After sorting, pick the minimum element and make it the root of the min heap.
> So, there is only 1 way to make the root of the min heap.
> Now we are left with 6 elements.
> Total ways to design a min heap from 6 elements = C(6,3)∗2!∗C(3,3)∗2! = 80
Note:
C(6,3)∗2! : Pick up any 3 elements for the left subtree and each left subtree combination can be permuted in 2! ways by interchanging the children and similarly, for right subtree .
> After sorting, pick the minimum element and make it the root of the min heap.
> So, there is only 1 way to make the root of the min heap.
> Now we are left with 6 elements.
> Total ways to design a min heap from 6 elements = C(6,3)∗2!∗C(3,3)∗2! = 80
Note:
C(6,3)∗2! : Pick up any 3 elements for the left subtree and each left subtree combination can be permuted in 2! ways by interchanging the children and similarly, for right subtree .
Question 63 
Let G be a graph with 100! vertices, with each vertex labeled by a distinct permutation of the numbers 1, 2, …, 100. There is an edge between vertices u and v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G, and z denote the number of connected components in G.
Then, y + 10z = ___________.
109  
110  
111  
112 
Question 63 Explanation:
G is a graph with 100! vertices.
Label of each vertex obtains from distinct permutation of numbers “1, 2, … 100”.
There exists edge between two vertices iff label of ‘u’ is obtained by swapping two adjacent numbers in label of ‘v’.
Example:
12 & 21, 23 & 34
The sets of the swapping numbers be (1, 2) (2, 3) (3, 4) … (99).
The no. of such sets are 99 i.e., no. of edges = 99.
As this is regular, each vertex has ‘99’ edges correspond to it. So degree of each vertex = 99 = y.
As the vertices are connected together, the number of components formed = 1 = z
y + 102 = 99 + 10(1) = 109
There exists edge between two vertices iff label of ‘u’ is obtained by swapping two adjacent numbers in label of ‘v’.
Example:
12 & 21, 23 & 34
The sets of the swapping numbers be (1, 2) (2, 3) (3, 4) … (99).
The no. of such sets are 99 i.e., no. of edges = 99.
As this is regular, each vertex has ‘99’ edges correspond to it. So degree of each vertex = 99 = y.
As the vertices are connected together, the number of components formed = 1 = z
y + 102 = 99 + 10(1) = 109
Question 64 
The instruction pipeline of a RISC processor has the following stages: Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Perform Operation (PO) and Writeback (WB). The IF, ID, OF and WB stages take 1 clock cycle each for every instruction. Consider a sequence of 100 instructions. In the PO stage, 40 instructions take 3 clock cycles each, 35 instructions take 2 clock cycles each, and the remaining 25 instructions take 1 clock cycle each. Assume that there are no data hazards and no control hazards.
The number of clock cycles required for completion of execution of the sequence of instructions is ___________.
219  
220  
221  
222 
Question 64 Explanation:
Total Instruction = 100
Number of stages = 5
We know in a normal pipeline with kstages time taken for ninstructions = k+n1 clock cycles.
So, in normal case total cycles = 100 +5 1 = 104 cycles
But in this question it is given that PO stage of 40 instructions takes 3 cycles, 35 instructions takes 2 cycles and 25 instructions takes 1 cycle. It is also given that all other stages take one clock cycle in all the 100 instructions.
PO stage of 40 instructions takes 3 cycles so these instructions will cause 2 stall cycle each, PO stage of 35 instructions takes 2 cycles so these instructions will cause 1 stall cycle each, But the 25 instruction whose PO stage takes 1 cycle, there are no stall cycles for these.
So, extra stall cycles = 40*2 + 35*1 = 80+35 = 115 cycles. So, total clock cycles = 104 + 115 = 219
Number of stages = 5
We know in a normal pipeline with kstages time taken for ninstructions = k+n1 clock cycles.
So, in normal case total cycles = 100 +5 1 = 104 cycles
But in this question it is given that PO stage of 40 instructions takes 3 cycles, 35 instructions takes 2 cycles and 25 instructions takes 1 cycle. It is also given that all other stages take one clock cycle in all the 100 instructions.
PO stage of 40 instructions takes 3 cycles so these instructions will cause 2 stall cycle each, PO stage of 35 instructions takes 2 cycles so these instructions will cause 1 stall cycle each, But the 25 instruction whose PO stage takes 1 cycle, there are no stall cycles for these.
So, extra stall cycles = 40*2 + 35*1 = 80+35 = 115 cycles. So, total clock cycles = 104 + 115 = 219
Question 65 
3  
4  
5  
6 
Question 65 Explanation:
f=Σ(0,2,5,7,9,11)+d(3,8,10,12,14)
There are 3 prime implicant i.e., P’QS, Q’S’ and PQ’ and all are essential. Because 0 and 2 are correct by only Q’S’, 5 and 7 are covered by only P’QS and 8 and 9 are covered by only PQ’.
There are 3 prime implicant i.e., P’QS, Q’S’ and PQ’ and all are essential. Because 0 and 2 are correct by only Q’S’, 5 and 7 are covered by only P’QS and 8 and 9 are covered by only PQ’.
There are 65 questions to complete.