GATE CS 2014 Official Paper: Shift 1 (Previous Year Paper)

The phrasal verb ‘cope with’ means to ‘adjust to’. The best meaning of the phrase is captured by ‘adapt to’.

The context of the sentence requires a word that will express the contradiction in the speaker’s mind. Since he did not think the performance to be impressive, that is why he could not understand the reason for her getting the first prize. Thus, the words ‘superb’ and ‘exhilarating’ can be ignored. Between ‘medium’ and ‘mediocre’, the latter is a better fit to describe a performance.

The meaning of the phrase ‘the buck stops here’ means that the minister would be responsible for all his decisions and with him lies the final power of decision making and thus option C is the correct meaning of the phrase.

Calculation:

\(\begin{array}{l} {\left( {z + \frac{1}{z}} \right)^2} = 98\ {Z^2} + \frac{1}{{{z^2}}} + 2 \times z \times \frac{1}{z} = 98\ {Z^2} + \frac{1}{{{z^2}}} = 98 - 2 = 96 \end{array}\)

Given the quadratic equations,

\(\begin{array}{l} a{x^2}; + bx + c = 0\ a{x^2} + b\left| x \right| + c = 0 \end{array}\)

\(\left| x \right|\) has two values \(+ x;and; - x\) . So, it may be resolved into two equations

\(a{x^2}; + bx + c = 0\)  with 2 roots

And \(a{x^2} - bx + c = 0\) with 2 roots

Hence, there are total 4 real roots.

The inference that can be drawn from the passage is that the low lying terrain of the gap is responsible for the weather patterns in Tamil Nadu and Kerala. We do not know the reasons of formation of the gap or the nature of the regions near the Palghat Gap thus eliminating options A and B. No correlation between temperatures and rainfall can be inferred from the passage, thus option D is not the correct inference.

Since the genetic roots are being confirmed for psychiatric illnesses, the assumption that can be made is that these diseases have a genetic basis. Thus option B is the correct assumption.

Total round trip fare for group of 5 tourist without discount

\(= 5 \times 200 = Rs.1000\)

(i) Discount for round trip = 10%of total fare \(= \frac{{10}}{{100}} \times 1000 = Rs.;100\)

 (ii) Discount for having a group of 5 tourist = 10%of total fare \(= \frac{5}{{100}} \times 100 = Rs.;500\)

Total discount = Discount for round + Discount for having a group of 5 tourist.

\(= 100 + 50 = Rs.150\)

Thus, the net round trip fare for group of 5 tourist after discount is

Net fare = total fare-total discount

\(\begin{array}{l} = Rs.1000 - Rs.150\ = Rs.;850 \end{array}\)

Total respondents = 300 (150 men + 150 women)

Total number of men who owns car = 100

Total number of men who owns scooter = 90

Total number of men who do not own a scooter = 40(Car) + 20(Nothing) = 60

Total number of women who owns car = 80

Total number of women who owns scooter = 66

Total number of women who do not own a scooter = 34(Car) + 50(Nothing) = 84

Percentage of respondents who do not own a scooter \(= \frac{{60 + 84}}{{300}} \times 100 = 48%\)

We draw a tetrahedron structure ABCD as

Now, P is a point inside the tetrahedron.

The point P is connected to each corners A, B, C and D of the tetrahedron.

So, we have the internal planes as ABP, APC, BPC, DPC, DPB and DPA.

I.e. the total number of internal planes = 6.

Concept:

¬ ∀x (P(x)) ≡ ∃ x ¬ P(x)

p → q ≡ ¬ p ∨ q

¬ (p ∨ q) ≡ ¬ p ∧ ¬ q

Explanation:

“All that glitters is gold” is expressed as

∀x (glitters (x) ⇒ gold (x))

“Not All that glitters is gold”

¬ ∀ x (glitters (x) ⇒ gold (x))

∃ x ¬ (glitters (x) ⇒ gold (x))

∃ x ¬ (¬ glitters (x) ∨ gold (x))

∃ x (glitters (x) ∧ ¬ gold (x))

Therefore option 4 is correct.

Important Point:

"Not all that glitters is gold" means "There exist a glitter and it is not gold" which can be expressed as

∃ x (glitters (x) ∧ ¬ gold (x))

Stick length = 1 unit

Let the stick break at the distance x.

Since expected length of the shorter stick is needed x ϵ [0, 0.5]

For uniform distribution,

Probability density function = p(x) = \(\frac{1}{{b - a}} = \frac{1}{{0.5 - 0}} = 2\)

Expected length = E(x)

\(E\left( x \right) = \mathop \smallint \limits_0^{0.5} xp\left( x \right)dx\)

\(E\left( x \right) = \mathop \smallint \limits_0^{0.5} x2dx = 2{\left( {\frac{{{x^2}}}{2}} \right)_0}^{0.5} = 0.25\)

the expected length of the shorter stick is 0.25

Important Point:

Official GATE CS answer range is 0.24 to 0.27

In a directed graph G Strongly connected will have a path from each vertex to every other vertex.

If the direction of the edges is reverse, then also graph is strongly connected components as G

Option 2: G₂ = (V, E₂) where E₂ = {(u, v)|(v, u) ∈ E}

In this option G₂, edges are reversed and hence it is a strongly connected components as similar to G

So, changing the direction of all the edges, won't change the SCC**.**

Concept:

The number of solutions can be determined by finding out the rank of the Augmented matrix and the rank of the Coefficient matrix.

• If rank(Augmented matrix) = rank(Coefficient matrix) = no. of variables then no of solutions = 1.
• If rank(Augmented matrix)  ≠ rank(Coefficient matrix) then no of solutions = 0.
• If rank(Augmented matrix) = rank(Coefficient matrix) < no. of variables, no of solutions = infinite.

Explanation:

Adding first two equations, we get the set equations as,

7x + 2y + 7z = 2

x + y + z = 3

x – 2y + 7z = 0

Augmented matrix will look like,

\(\begin{array}{*{20}{c}} 7&2&7\ 1&1&1\ 1&{ - 2}&7 \end{array};\left| {;;\begin{array}{*{20}{c}} 2\ 3\ 0 \end{array};} \right|\)

R₁ → R₁ – 7R₂

\(\begin{array}{*{20}{c}} 0&{ - 5}&0\ 1&1&1\ 1&{ - 2}&7 \end{array};\left| {;;\begin{array}{*{20}{c}} { - 19}\ 3\ 0 \end{array};} \right|\)

R₃ → R₃ – R₂

\(\begin{array}{*{20}{c}} 0&{ - 5}&0\ 1&1&1\ 0&{ - 3}&6 \end{array};\left| {;;\begin{array}{*{20}{c}} { - 19}\ 3\ { - 3} \end{array};} \right|\)

R₃ → 5R₃ – 3R₁

\(\begin{array}{*{20}{c}} 0&{ - 5}&0\ 1&1&1\ 0&0&{30} \end{array};\left| {;;\begin{array}{*{20}{c}} { - 19}\ 3\ {42} \end{array};} \right|\)

No further reductions are going to be useful.

Hence, Rank of Augmented matrix = Rank of Coefficient matrix = Number of variables = 3.

No of solutions = 1.

Alternate Method:

\(\left| {\begin{array}{*{20}{c}} 7&2&7\ 1&1&1\ 1&{ - 2}&7 \end{array}} \right| = 30 \ne 0\)

There Rank of Augmented matrix = Rank of Coefficient matrix = 3 and hence it has unique solution

Concept:

According to the details, let λ₁ and λ₂ be the two distinct eigenvalues of a 4-by-4 symmetric positive definite matrix A. Now, u and v be the corresponding eigenvectors respectively.

I every case of a symmetric positive definite matrix A, u and v will be orthogonal to each other. Hence, their dot product will be 0.

Explanation:

Au = λ₁u      _____ (1)

Av = λ₂v      ­_____ (2)

On multiplying equation (1) with v^T, we get

v^TAu = v^Tλ₁u

(v^TA)u = v^Tλ₁u

(A^Tv)^Tu = v^Tλ₁u

 (Av)^Tu = v^Tλ₁u (since A is a symmetric matrix, we can write A^T = A)

Using equation 2,

Av = λ₂v

(λ₂v)^Tu = v^Tλ₁u

λ₂v^Tu = v^Tλ₁u

λ₂v^Tu = λ₁v^Tu (as λ₁ is a constant, we can write v^Tλ₁ = λ₁v^T)

λ₂v^Tu − λ₁v^Tu = 0

(λ₂−λ₁)v^Tu = 0

∴ either (λ₂ − λ₁) = 0 or v^Tu = 0

But since λ₂ ≠ λ₁, v^Tu must be 0

v^Tu is nothing but the dot product of the eigenvectors u and v.

Rolle's theorem.

To apply Rolle's theorem following 3 conditions should be satisfied:

f(x) should be continuous in interval [a, b],

f(x) should be differentiable in interval (a, b), and

f(a)=f(b)

If these 3 conditions are satisfied simultaneously then, there exists at least one ′x′ such that f′(x)=0

Explanation:

Statement I: There exists \(\theta \in \left( {\frac{\pi }{6},\frac{\pi }{3}} \right)\) such that f’(θ) = 0

For the given question, it satisfies all the three conditions, therefore there exists at least one θ that gives f′(θ)=0

Therefore, statement II is true

Statement II: There exists \(\theta \in \left( {\frac{\pi }{6},\frac{\pi }{3}} \right)\) such that f’(θ) ≠ 0  

The given function is also not a constant function therefore for some θ, f′(θ) ≠ 0

Therefore, statement II is true

F(P, Q, R, S) = PQ + P̅QR + P̅QR̅S

F(P, Q, R, S) = PQ(R + R̅)(S + S̅) + P̅QR(S + S̅) + P̅QR̅S  

F(P, Q, R, S) = PQRS + PQRS̅ + PQR̅S + PQR̅S̅ + P̅QRS + P̅QRS̅ + P̅QR̅S

F(P, Q, R, S) = ∑ (15 + 14 + 13 + 12 + 7 + 6 + 5)  

K-Map:

F(P, Q, R, S) = PQ + QR + QS

Let the base of system be b.

\(\frac{{{{\left( {312} \right)}_b}}}{{{{\left( {20} \right)}_b}}} = {\left( {13.1} \right)_b}\)

\(\frac{{3 \times {b^2} + 1 \times {b^1} + 2 \times {b^0}}}{{2 \times b + 0 \times {b^0}}} = {\left( {1 \times {b^1} + 3 \times {b^0} + 1 \times {b^{ - 1}}} \right)_{}}\)

\(\frac{{3{b^2} + b + 2}}{{2b}} = b + 3 + \frac{1}{b}\)

\(\frac{{3{b^2} + b + 2}}{{2b}} = \frac{{{b^2} + 3b + 1}}{b}\)

\(3{b^2} + b + 2 = 2{b^2} + 6b + 2\)

b² – 5b = 0

b(b – 5) = 0

b = 0 OR b = 5

\(From;\frac{{{{\left( {312} \right)}_b}}}{{{{\left( {20} \right)}_b}}} = {\left( {13.1} \right)_b},;b > 3\)

Therefore, the base (or radix) of the number system such that the following equation holds is 5.

Data:

Each instruction = 32 bit

Number of instructions which are supported = 45

Number of registers = 64

Formula:

The maximum value of unsigned immediate operand = 2ⁿ – 1

where n is the number of bits in immediate operand field

Opcode + R + R + Immediate Operand = 32 bits

Calculation

Number of bits needed for opcode = ⌈ log₂(45)⌉ = 6 bits

Number of bits needed for registers = ⌈ log₂(64)⌉ = 6 bits

6 + 6 + 6 + Immediate Operand = 32

Immediate Operand = (32 – 18) bits = 14 bits

The maximum value of unsigned immediate operand = 2¹⁴ – 1 = 16383

scanf(“%d”,pi); \let the input be 10

Therefore, on execution, the value printed is 5 more than the integer value entered.

Code:

main()

{

int i; \ declare integer i

int *pi = &i; \ integer pointer store address of i

scanf(“%d”,pi); \ input is stored in integer i

printf(“%d\n”, i+5); \ value printed is 5 more than the integer value entered

}

Therefore option 4 is correct.

Concept

In adjacency matrix representation, graph is represented as an “n x n” matrix.

Graph:

Then, its adjacency matrix will be

Explanation:

For performing DFS on the above graph or any adjacency matrix of a graph G, we traverse the row corresponding to that vertex. This way, we find all the adjacent vertices.

Hence, the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix is Θ (n²).

Concept:

Using bottom up parsing, the subtrees with exactly 4 nodes can be found.

1. For parsing from bottom to top, it takes O(n).
2. Check whether the node has 4 nodes by level up parsing. It takes O(1).

Explanation:

Following steps can be used

1. Coming to the topmost level with a tree of n nodes, it takes O(n) time.
2. For every subtree with 4 nodes, we increment the counter by 1. This can be done in O(1) time.

Therefore, T(n) = O(n^a log^b n) = O(n)

Comparing with T(n) = n^a log^b n

a = 1, b = 0;

a + 10b = 1

Concept:

This graph doesn’t have any cycle, hence there must exist a topological ordering.

R has an indegree from P and S. Q has indegree from P, R and S. Hence,

1. P and S must appear R in the topological ordering.
2. P, S, R must appear before Q in the topological ordering.
3. Sequence of P and S has no indegree can be interchanged.

Therefore, the valid topological orders are PSRQ and SPRQ.

Explanation:

For topological ordering, the starting vertex must have 0 indegree. Hence, any one from P or S can be chosen.

If we choose P, then we need to choose the next vertex with indegree only from P. Hence, S is chosen.

After P and S, we choose a vertex with indegree only from P and S. Hence. R then Q.

Same could be performed with S instead of P.

Concept:

If the array is sorting is increasing or non-increasing order, choosing either first or last element given the worst-case time complexity in Quick Sort.

Explanation

In every step of quick sort, numbers are divided as per the following recurrence.

T(n) = T(n-1) + O(n)

Average case time complexity (t2) = O(logn)

Worst case time complexity (t1) = O(n²)

Since t1 has the worst case ∴ t1 > t2

Important Point:

Number of comparisons will vary based on implementation

Always in ascending or descending array (worst case) number of comparisons is higher

Concept:

Regular languages do not support unbounded storage or memory property.

Option 1: FALSE

L = {aⁿbⁿ | ≥ 1} is accepted by Pushdown automata and hence it is context free grammar.

{aⁿbⁿ | ≥ 1} is not accepted by Finite automata. So, this language is non-regular.

Option 2: FALSE

\({ {a^n}|n;is;prime} \) is accepted by linear bounded automaton therefore it is a context sensitive language. It is not accepted by finite automata and hence it is not regular.

Option 3: TRUE

\(L = { w|w;has;3k + 1;b's\)

Regular Expression:  ab(ababab)⁺a*

It is regular

Option 4: FALSE

The language L = {ww|w ∈ ∑* with ∑ = {0, 1}} is context sensitive language.

NFA

Therefore, q_o is reachable.

Therefore, q₁ is reachable.

Therefore, q₂ is reachable.

The set of reachable states for the input string 0011is \(\left{ {{q_0},;{q_1},;{q_2}} \right}\)

Option 1: True

Since, there are jump statements or branching possible in a basic block, it is a sequence of instructions where control follows in a linear fashion entering from beginning and exiting from end.

Option2: True

Common Subexpression Elimination is an optimization that searches for instances of identical expressions, and replaces them with a single variable holding the computed value. Hence, available expression analysis can be used for common subexpression elimination.

Option_3: – True

Dead code elimination is a compiler optimization to remove code which does not affect the program results. Live variable analysis is a classic data-flow analysis to calculate the variables that are live at each point in the program. Hence, is efficient for Dead code elimination.

Option 4: False

Common subexpression elimination (CSE) refers to compiler optimization replaces identical expressions (i.e., they all evaluate to the same value) with a single variable holding the computed value when it is worthwhile to do so.

Waterfall Model:

Moving forward compulsorily, it is impossible to go back to previous project phase in waterfall model. Hence, this method is inflexible.

Evolutionary:

The model keeps changing with time and according to requirements. Hence, it is incremental in nature.

Component based:

This model relies on reuse-based approach to defining, implementing and composing loosely coupled independent components into systems.

Spiral:

This model is the most advanced. It includes four phases - Planning, Risk Analysis, Engineering and Evaluation.

Disk scheduling Algorithm: shortest seek time first

Disk arm is at 100

Disk queue request: 30, 85, 90, 100, 105, 110, 135 and 145.

**Diagram:**Service: 100 cylinder, 105 cylinder, 110 cylinder than 90 cylinder

Therefore, the request for cylinder 90 is serviced after servicing 3 requests.

Important Point:

Disk arm is at cylinder 100, it was not serviced, hence 100 cylinder is the first serviced cylinder.

Concept:

• Multiple threads of the same process share other resources of process except register and stack pointer.
• In particular, a process is generally considered to consist of a set of threads sharing an address space, heap, static data, code segments and file descriptors.

Thread:

Option 4: FALSE

Kernel level threads can share the code segment

Option 1: TRUE

User level threads are scheduled by the thread library and kernel do not know about it. Therefore, User level threads are not scheduled by the kernel.

Option 2: TRUE

When a user level thread is blocked, all other threads of its process are blocked.

Option 3: TRUE

Context switching between user level threads is faster than context switching between kernel

level threads because in user level thread, context switching nothing is saved and restored while for kernel level thread, registers, program counter and stack pointer must be saved and restored.

Function Dependencies:

{(E, F} → {G}, {F} → {I, J}, {E, H} → {K, L}, {K} → {M}, {L} → {N}}

Option 1: {E, F}

{E, F}⁺ = {E, F, G, I, J}

Since K, L, M and N is missing in RHS ∴ it is not a key

Also, {E} cannot be a key because {E} is subset of {E, F}

Option 2: {E, F, H}

{E, F, H}⁺ = {E, F, H, G, I, J, K, L, M, N}

∴ it is a key

Key for R is {E, F, H}.

Important Points:

In relation algebra, key is primary key or candidate key.

{E, F, H, K, L} is super key.

Concept:

A foreign key in one table should uniquely identify an entire row of another table correctly. Check insertion do not always ensure sufficient-ness for replacing the foreign key.

Explanation:

S1 is false, as in our case foreign key declaration may have cascade delete which is not possible to ensure by just using check insertion.

S2 is false because in above table definition, table S has a foreign key that refers to field a of R. The field a is table S does not uniquely identify a row in table R.

Statement 1: TRUE

The computational overhead in link state protocols is higher than in distance vector protocols because LSR is based upon global knowledge whereas DVR is based upon Local information.

Statement 2: FALSE

Persistent looping can be avoided with the help of split horizon in DVR but there is no concept of persistent looping in LSR, in LSR only temporary loop exist and can automatically solved by system or router.

Statement 3: TRUE

After a topology change, a link state protocol will converge faster than a distance vector protocol.

Therefore option 4 is correct.

Important Point:

LSR → Link State Routing

DVR → Distance Vector Routing

SHA 1 and MD5 both generate the message digest.

1. SHA 1 –SHA 1 is a cryptographic hash function that produces a 160 bit (20 byte) hash value (message digest).
2. MD5 –MD5 is a widely used cryptographic hash function that produces a 128 bit hash value (message digest).

Therefore option 3 is correct.

Important Point:

RSA and DES both are encryption algorithms.

• RSA is also used to decrypt the encrypted message by same RSA algorithm.
• Data encryption standard (DES) is a block cipher that encrypts data in blocks of size 64 bits each. That is 64 bits of plain text goes input to the DES which produces 64 bit of cipher text. Key length is 56 bits.
• RSA and DES do not allow generating message digests.

The correct order in which the following actions take place in an interaction between a web browser and a web server

Step 1:

The web browser first needs to figure out IP address of site from URL using DNS. This is typically called domain name resolution.

Step 2:

TCP connection is established mostly at port 80.

Step 3:

Once the TCP connection is established, the browser sends an HTTP request using GET method.

Step 4:

Finally, web server responds with HTTP response that is, the page we requested.

Hence, the correct sequence of actions is 4, 2, 1, 3

Data:

Propagation speed of the signal = 2 x 10⁸ m/s

Token holding time = 2 μ sec

Token ring network length = 2 Km

Concept:

Minimum waiting time = Prorogation delay or Ring latency + Token holding time for every station

Minimum waiting time = T_p + n xTHT

Calculation:

\({{\rm{T}}_{\rm{P}}} = \frac{{{\rm{Length}}}}{{{\rm{Speed}}}} = \frac{{2 \times {{10}^3}}}{{2 \times {{10}^8}}} = {10^{ - 5}}{\rm{;}}\frac{{10}}{{10}} = 10{\rm{;\mu ;sec;}}\) (1 μ sec = 10^-6 sec )

Minimum waiting time = 10 + 10 x 2 = 30 μ sec              

Note: 

28 μ sec is also possible answer because suppose station 1 is holding token then after releasing it only 9 station will hold the token for 2 μ sec to get back to station 1 or token is to lost so for waiting time for a station 1 is only 18 μ sec + ring latency = 28 μ sec

Data:

Maximum Segment Size (MSS) = 2 KB

Round trip time (RTT) = 100 ms

Congestion window Size (CWS) = 32 KB

Formula:

\({\rm{Threshold}} = \frac{{{\rm{CWS}}}}{{{\rm{MSS}}}}\)

Calculation

\({\rm{Threshold}} = \frac{{{\rm{CWS}}}}{{{\rm{MSS}}}} = \frac{{32}}{2} = 16;KB\)

Number of round trips = 12 – 1 = 11

Total time taken = 11 × 100 ms = 1100

The time taken (in msec) by the TCP connection to get back to 32 KB congestion window is 1100 ms.

Data:

Frame Size = 1 KB = 8 Kb = 8 × 10³ b

Bandwidth = 1.5 Mbps = 1.5 × 10⁶ bps

Propagation delay = 50 ms

Link Utilization = 60% = 0.6

Formula:

\({\rm{Transmission;delay}} = \frac{{{\rm{Frame;size}}}}{{{\rm{Bandwidth}}}}\)

2a = (2 × propagation delay) ÷ Transmission delay

\({\rm{link;Utilization}} = \frac{{{\rm{Window;Size}}\left( {\rm{N}} \right)}}{{1 + 2{\rm{a}}}}\)

Calculation:

\({\rm{Transmission;delay}} = \frac{{8 \times {{10}^3}}}{{1.5 \times {{10}^6}}} = \frac{{16}}{3}{\rm{;ms}}\)

\(2a = \frac{{2; \times ;50}}{{\frac{{16}}{3}}} = 18.75\)

\(0.6 = \frac{{\rm{N}}}{{1; + ;18.75}}\)

Window size = N = 11.85

Minimum sequence number = 2 × N = 23.7

Bits required r = ⌈ log₂(23.7) ⌉  = 5

Concept:

A schedule is called conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations.

For a schedule to be conflict serializable, there should be no cycle present in its precedence graph.

Explanation: 

Option_1 – Not conflict serializable

• Cycle between T1 and T2.
• Cycle between T1->T3->T2

Option_2 – Not conflict serializable

• Cycle between T1 and T2.
• Cycle between T1->T2->T3

Option-3 - Not conflict serializable

• Cycle between T1 and T2.

Option-4 - Conflict serializable

• No cycle

Hence, Option_4 is a conflict serializable schedule

Statement 1: TRUE

BCNF (Boyce Codd Normal Form):

• A relation R is in BCNF whenever a non – trivial functional dependency X → A holds in R, where X is the super-key of R.
• A binary relation is always in BCNF. A binary relation contains only two attributes.
• Functional dependency that is possible from a binary relation is one.

Example:

Consider R(A, B), in this only one functional dependency is possible either A → B or B → A

In both the cases, left hand side will be the super key. In this way R(A, B) is always in BCNF.

If a relation is in BCNF then it is in 1NF, 2 NF and 3 NF

Statement 2: FALSE

Set 1 = {AB → C, D → E, AB → E, E→ C}

Set 2 = {AB → C, D → E, E → C}

Set 2 cannot derive   AB → E since in set 2 (AB)⁺ = {A, B, C}

The two sets of functional dependencies are not the same and hence one cannot be minimal of other.

Concept:

Using banker’s algorithm, we will find the Need matrix and with the available resources, we will try to come up a feasible sequence of process completion.

Explanation:

REQ1 asks X = 0, Y = 0, Z = 2 for P0

Now, if the request REQ1 is permitted, the state would become:

Notice that in table P0’s allocated Z becomes 3 from 1 and Available resources of Z reduce to 0 from 2.

With the above table, we can use available resources to service P1. 

With 0 instances of Z being available, no requests of P0 or P2 can be fulfilled, hence the system is in deadlock.

Therefore, REQ1 cannot be permitted.

REQ2 asks X = 2, Y = 0, Z = 0 for P1

Now, if the request REQ2 is permitted, the state would become:

Notice that in table P1’s allocated X becomes 5 from 3 and Available resources of X reduce to 1 from 3.

With the above table, we can use available resources to service P1. (P2 can also be serviced)

With the above available instances, P2 can be services and then P0.

Final table will look like, 

Therefore, REQ1 can be permitted.

Scheduling Algorithm: Shortest Remaining Time First (Pre-emptive)

Gantt chart:

0       3        5        8       12      15      21

Formula:

Turnaround time = Completion time – Arrival time.

Process Table:

Average turnaround time = \(\frac{{\left( {8; + ;2; + ;7; + ;14; + ;5} \right)}}{5} = 7.2;msec\)

Important Points:

TAT = CT - AT

Page reference: 1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6

Page replacement algorithm: optimal replacement policy

Optimal = 7 miss = 7 page faults

Important Point:

M → miss

H → Hit

Concept –

In the given grammar, the symbol < is not present hence, with respect to <, there will neither be a shift-reduce conflict nor reduce-reduce conflict.

However, with respect to symbol >, there will be a shift-reduce conflict.

Explanation:

If we consider the grammar to be LR(0) there would be S-R conflict in the given canonical form.

Suppose that the present state is I₀ and on transition on > it goes to I₁ state.

S -> L. > R -- production number 1

Q -> R. -- production number 2

In LR(0) reduced move will be placed in entire row.(under terminal columns)

Hence, on the symbol >, there will be an SR conflict$.

• If L is recursive language, then L̅ is also recursive. Every recursive is recursively enumerable (r.e.)
• L is recursively enumerable language (r.e.) but not recursive and it means L is r.e. but L̅ is not r.e.

Option 1: Neither L nor L̅ is recursively enumerable

It is possible that L is not recursively enumerable and L̅ is also not recursively enumerable. Hence it is viable.

Option 2: One of L and \(\vec L\) is r.e. but not recursive; the other is not r.e.

Recursively enumerable Language is not closed under complementation. If L is RE and not recursive then L̅ is not recursive and hence it is viable.

Option 3: Both L and \(\vec L\) are r.e. but not recursive.

Recursive is closed under complementation.  If  L and L̅ is RE and it is definitely recursive and hence it is not possible that both L and \(\vec L\) are r.e. but not recursive.

Option 4: Both L and \(\vec L\) are recursive.

Recursive is closed under complementation.  If L is recursive then and L̅ is also recursive therefore it is viable

The above DFA accepts all the string ending with 1

R = (1 + 0)^*1

L = {1,01,11,001,011, 101, 111 …}

Statement I: 01(1+001)*

Step 1:

Step 2:

F1_Raju_Madhu_07.07.20_D 2

Step 3:

Hence, Statement I is true

Statement II: 011+1101

String: 11011

Statement II is false because string accepted by DFA but not accepted by given regular expression.

Statement III: (0+1)*1

L = {1,01,11,001,011, 101, 111 …}

It is also true because given DFA accept all string ending with 1.

A is the number of coins of 10 gm and B is the number of coins of 11 gm.

A x 10 + B x 11 = 323

A + B = 31(Sum of all coins) multiply this equation with 10 and subtract from above equation we get

B = 13 and A = 18

B = 13 (only one combination: 8 4 1)

8 coins picked from bag labelled by 4.

4 coins picked from bag labelled by 3.

1 coin picked from bag labelled by 1.

Multiplication of all labels = 4 × 3 × 1 = 12

Hence 12 is the correct answer.

Clique is in NPC.

By definition of NPC, all NP problems can be reduced to Clique in polynomial time.

So, if clique can be solved in polynomial time, any NP problem can also be solved in polynomial time making P=NP and hence P=NP=NPC.

Data:

n = 100

Formula:

minimum number of comparisons = \(\frac{{3n}}{2} - 2\)

Calculation:

minimum number of comparisons = \(\frac{{3; \times ;100}}{2} - 2 = 148\)

Important Points:

Divide and conquer is used to achieve minimum comparison

Tournament Method Technique

1. To find the smallest element in the array will take n−1 comparisons = 100 – 1 = 99.
2. To find the largest element -

After the first round of Tournament, there will be exactly n/2 numbers = 50 that will lose the round.

So, the biggest looser (the largest number) should be among these 50 looser.

To find the largest number will take \(\frac{n}{2} - 1\) comparisons = 49.

Total 99 + 49 = 148.

Concept:

Keys: 5, 28, 19, 15, 20, 33, 12, 17,

ℎ(k) = k mod 9

Chaining

Maximum chain length = 3 (28 -> 19 -> 10)

Minimum chain length = 0 (0, 4, 7 slot doesn’t have any element)

\({\rm{Average;chain;length;}} = \frac{{0 + 3 + 1 + 1 + 0 + 1 + 2 + 0 + 1}}{9} = \frac{9}{9} = 1\)

Hence option 1 is the correct answer.

Concept:

Let’s take a small example

Array E, Size =4

Y = Sum of all elements = 10

After running outer loop one time we can observe here that every time it is calculating total sum of every sub array or maximum sum of that sub array then compare with Y. here you might confused with option 3. Option 3 is saying that in all sub array we are finding sum of maximum element (here maximum element word is important). 

In program we are not finding maximum element in any sub array so option 3 is wrong option 1 is the correct answer.

Method 1:

All loops can be written as:

\(N = \mathop \sum \limits_{i = 1}^n \mathop \sum \limits_{j = i}^n \mathop \sum \limits_{k = j + 1}^n ;1\) 

\(N = \mathop \sum \limits_{i = 1}^n \mathop \sum \limits_{j = i}^n \left( {n - j} \right)\) 

\(N = \mathop \sum \limits_{i = 1}^n \mathop \sum \limits_{j = 0}^{n - i} ;j\) 

\(N = \mathop \sum \limits_{i = 1}^n \frac{{\left( {n - i} \right)\left( {n - i; + ;1} \right)}}{2}\) 

\(N = \frac{1}{2}\mathop \sum \limits_{i = 0}^{n - 1} {i^2} + i\) 

\(N = \frac{1}{2}\left( {;\frac{{n\left( {n - 1} \right)\left( {2n - 1} \right)}}{6} + \frac{{n\left( {n - 1} \right)}}{2};} \right)\) 

\(N = \frac{{n\left( {n - 1} \right)\left( {n + 1} \right)}}{6}\) 

Method 2: By putting value if n = 3

Inner most loop will run total four times then multiplication will happen 4 times, now check which option satisfy 4 after putting value n = 3 three consecutive integers multiplication can be 1 x 2 x 3 or

2 x 3 x 4 or 3 x 4 x 5 so here 2 x 3 x 4 divides with 6 we get 4 so option 3 is the correct answer.

Data:

Instruction pipeline = 6 stage

25% of the instructions incur 2 pipeline stall cycles

Formula:

Speed up = \(\frac{{Execution;time\left( {non;pipeline} \right)}}{{Execution;time;\left( {pipeline} \right)}}\)

Time with pipeline  =1+ stall freqency×stall cycle

Calculation:

Time without pipeline = 6 stages=6 cycles

Time with pipeline = =1+.25 × 2 =1.5

Speed up = \(\frac{{6}}{{1.5}} = 4\)

Concept:

If u focus on this line of question cache of associativity A ≥ k then you can find out that it is saying that there will not be capacity miss only compulsory miss will be there.

Example:

n={ 4,5,6,7} N={4,5,6,7,4,5,6,7} k=3 assume A=4  then in this case A=4 means each set is containing 4 lines and we have only four unique block address ( Worst case : Assuming they all are in same set ), there will be no capacity miss only compulsory miss are there, so miss rate will be

\(\frac{4}{8}\) this is nothing but \(\frac{n}{N}\)

Hence option 1 is the correct answer.

F = P̅.Q̅0+ P̅.Q.1 + P.Q̅.R  + P.Q.R̅. 

F = P̅.Q + P.Q̅.R + P.Q.R̅

F = P̅.Q(R̅ + R ) + P.Q̅.R + P.Q.R̅

F = P̅.Q.R̅ + P̅.Q.R + P.Q̅.R + P.Q.R̅

F = ∑ (2, 3, 5, 6)

K – Map:

F = P̅ Q + Q R̅ + P Q̅ R

Concept:

\(\frac{d}{{dx}}\left( {f\left( x \right).g\left( x \right)} \right) = f\left( x \right)g'\left( x \right) + f'\left( x \right)g\left( x \right)\)

Calculation:

f(x) = x sin x   (1)

f'(x) = xcosx + sinx

f''(x) = -xsinx + cosx + cosx = 

∴ f''(x) = -xsinx + 2cosx  (2)

f’’(x) + f(x) + t cos x = 0

Substituting the value from (1) and (2)

\(\left( { - {\rm{x;sinx}} + 2{\rm{;cosx}}} \right) + \left( {{\rm{x;sinx}}} \right) + {\rm{t;cosx}} = 0\)

2 cosx + t cosx = 0

cosx(2 + t) = 0

∴ cos x = 0 OR 2 + t = 0

\(\cos {\rm{x}} = \left( {2{\rm{n}} + 1} \right)\left( {\frac{{\rm{\pi }}}{2}} \right){\rm{;where;n}} = 1,{\rm{;}}2,3,4 \ldots {\rm{;}}\)

t = -2

Since value of t is asked

Therefore, value of t is -2

Let’s define a new function t : t(y) = f(y) –  f(y+1)

We know that f is continuous in [ 0 , 2 ], t will also be continuous in [ 0 , 1 ].

In question it is given that f(0)= - 1 , f(2) = -1 and f(1) = 1, putting into above function  we get  t(0) and t(1)

t(0) = f(0) - f(1) = -1 - 1 = - 2 and t(1) = f(1)- f(2) = 1+1 = 2

so we get  t(0)=-2  and  t(1) = 2 since function is changing its value from -2 negative to +2 positive, it means function t is a increasing function and there exists a point where t will be 0 in (0,1)

t=0 then f(y)= f(y+1)

Hence option 1 is the correct answer.

Same logic can be applied to option d:

h(y) = f(y) + f(y+2)

We know that function f is continuous in [0,2], function h will also be continuous in [0,1].

In question it is given that f(0)=-1, f(2)=-1 and f(1)=1, putting into above function.

h(0) = f(0) - f(1) = -1 - 1 = - 2 and h(1) = f(1)- f(2) = 1+1 = 2

So we get h(0)=-2  and  h(1) = 2, since function is changing its value from -2 to +2. It means function h is a increasing function and there exists a point where h would be 0 in (0,1)

h=0 then f(y) = -f(y+2)

Hence option 1 and 4 both are correct answer.

Data:

Four fair six-sided dice are rolled

\({\rm{Probability}} = \frac{{\rm{X}}}{{1296}}\)

Formula:

\({\rm{Probability}} = \frac{{{\rm{Number;of;favourable;outcomes}}}}{{{\rm{Total;outcomes}}}}\)

Calculation:

Since 4 dice are rolled

Total outcomes = 6 × 6 × 6 × 6 = 1296

Sum of the results is 22 = Number of Favourable outcomes

Case 1: Three 6’s and one 4, for example: 6,6,6,4 (sum is 22)

Number of Favourable outcomes = 4

{(6,6,6,4), (6,6,4,6), (6,4,6,6), (4,6,6,6)}

Case 2: Two 6’s and two 5’s for example: 6,6,5,5 (sum is 22)

Number of Favourable outcomes = 6

 {(6,6,5,5) (6,5,5,6) (5,5,6,6) (5,6,6,5) (6,5,6,5), (5,6,5,6) }

Total Number of Favourable outcomes = 10

Therefore, the value of X is 10.

10-pennant is a sequence of numbers with sum equal to 10 and that sequence can contains only 1’s and 2’s. questions how many total 10-pennant sequence is possible ?

Case 1 : ( 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ) ,Sum =10 and \({\rm{Total;possible;combination;}} = \frac{{10!}}{{10!}} = 1\)

Case 2 : ( 1, 1, 1, 1, 1, 1, 1, 1, 2 ), Sum = 10 and \({\rm{Total;possible;combination;}} = \frac{{9!}}{{8! \times 1!}} = 9\)

Case 3 : ( 1, 1, 1, 1, 1, 1, 2, 2), Sum = 10 and\(;{\rm{Total;possible;combination;}} = \frac{{8!}}{{6! \times 2!}} = 28\)

Case 4 : ( 1, 1, 1, 1, 2, 2, 2 ), Sum = 10 and\(;{\rm{Total;possible;combination;}} = \frac{{7!}}{{4! \times 3!}} = 35\)

Case 5 : ( 1, 1, 2, 2, 2, 2 ), Sum = 10 and \({\rm{Total;possible;combination;}} = \frac{{6!}}{{2! \times 4!}} = 15\)

Case 6 : ( 2, 2, 2, 2, 2 ), Sum = 10 and\({\rm{;Total;possible;combination;}} = \frac{{5!}}{{5!}} = 1\)

Total possible combination = 1 + 9 + 28 + 35 + 15 + 1 = 89

Hence 89 is the correct answer.

Concept:

Let A and B are two sets having m and n elements respectively.

In f : A → B, total number of functions will be n^m.

Explanation:

S -> f : 2⁴ → 2 gives total number of functions to be 2^{2^4} = 2¹⁶

N is defined by f : S-> {0,1}.

Therefore, total number of functions will be 2^S

Hence, log₂ log₂ N

= log₂ log₂ 2^S

= log₂ log₂ 2^{2^16}

= log₂2¹⁶

= 16

Let’s understand with small graph with vertices of 3

Matrix of graph of 3 vertices :  \(\begin{array}{*{20}{c}} {\left( {1,1} \right)}&{\left( {1,2} \right)}&{\left( {1,3} \right)}\ {\left( {2,1} \right)}&{\left( {2,2} \right)}&{\left( {2,3} \right)}\ {\left( {3,1} \right)}&{\left( {3,2} \right)}&{\left( {3,3} \right)} \end{array}\) 

Here we can see that 3 types of degree are possible 3, 5 and 8.

Degree 3 is possible by corner vertex like (1,1) ,(1,3),(2,1),(3,3) because these vertex are following property given in question.

Example: vertex (1, 1) has distance less than or equal to 1 with vertex (1,2), ( 2,1),(2,2)so corner vertex has degree 3

Degree 5 is possible by all vertices between corner vertices which is following the property

Example: All vertex between (1,1) to ( 1,3) , (1,1) to (3,1) ,(3,1) to (3,3) ,(1,3) to (3,3) and (3,1) to ( 3,3) so total 4 vertices are there ( (1,2) , (2,1) , (3,2) , (2,3) )all are having degree 5.

Example: vertex(1,2) has distance less than or equal to 1 with vertex ( 1,1),(1,3),(2,1),(2,3),(2,2)

Degree 8 is possible with all remaining vertex like in this case (2,2).

Example: vertex (2, 2) has distance less than or equal to 1 with all other 8 vertices.

Total vertices here are 3 × 3 = 9

Let’s come to question here total vertex is 12

Total corner vertex 4, each having degree 3.

Vertex between two corner is 40 ( (1,2) to (1,11), (2,1) to (11,1), (2,12) to (11,12) and (12,2) to (12,12) ) each vertex is having degree 5

Remaining 100 vertex each having degree 8.

Using handshake theorem:

2|E|= Sum of the degrees

2|E|= 4×3 + 40 × 5 + 100 × 8 = 1012, |E|=506

Hence 506 is the correct answer.

Concept:

Using Havel-Hakimi algorithm we can find out simple graph exits or not for a given degree sequence.

Havel-Hakimi algorithm:

Step 1: Sort the sequence in non increasing order.

Step 2: Delete the first degree or element ( Say x )then subtract 1 from the next x elements.

Step 3: Repeat step 1 and step 2 until all the elements remaining are equal to 0 then only simple graph exits. If negative degree encounter after subtraction then No simple graph exists. If not enough elements remaining for subtraction then No simple graph exists.

Calculation:

Option 1: (1, 1, 1, 1, 1 ,1)

Step 1 and 2: remove 1 we get ( 0 , 1 , 1 , 1 , 1) reorder : ( 1, 1 , 1 , 1 ,0 )

 Step 1 and 2 : remove 1 we get ( 0 , 1 , 1 , 0) reorder :  ( 1 , 1 , 0 , 0)

Step 1 and 2: remove 1 we get (0, 0, 0) so simple graph exists

Option 2: (2, 2, 2, 2, 2, 2)

Step 1 and Step 2 : Remove 2 we get  ( 1,1,2,2,2) Reorder : ( 2,2,2,1,1)

Step 1 and Step 2: Remove 2 we get (1,1,1,1)

Step 1 and Step 2 : Remove 1 we get ( 0,1,1) Reorder : (1,1,0)

Step 1 and Step 2 : Remove 1 we get ( 0,0), so simple graph exists.

Option 3: (3, 3, 3, 1, 0, 0)

Step 1 and Step 2: Remove 3 we get (2,2,0,0,0)

Step 1 and Step 2: Remove 2 we get (1,-1,0,0)

Since negative value is present so simple graph does not exist.

Option 4: (3, 2, 1, 1, 1, 0)

Step 1 and Step 2: Remove 3 we get (1,0,0,1,0) Reorder (1,1,0,0,0)

Step 1 and Step 2: Remove 1 we get (0,0,0,0) so simple graph exists.

Hence option 3 is the correct answer.

Truth table: P → Q

Truth table: P ↔ Q

Option 1

\(\left( {\left( {{\rm{p}} \leftrightarrow {\rm{q}}} \right) \wedge {\rm{r}}} \right) \vee \left( {{\rm{p}} \wedge {\rm{q}} \wedge \sim {\rm{r}}} \right)\)

\({\rm{Taking;p}} = {\rm{T;and;q}} = {\rm{T}},{\rm{;;}}\left( {\left( {{\rm{T}} \leftrightarrow {\rm{T}}} \right) \wedge {\rm{r}}} \right) \vee \left( {{\rm{T}} \wedge {\rm{T}} \wedge \sim {\rm{r}}} \right)\)

\( = \left( {\left( {\rm{T}} \right) \wedge {\rm{r}}} \right) \vee \left( {{\rm{T}} \wedge \sim {\rm{r}}} \right)\)

\(= \left( {\rm{r}} \right) \vee \left( { \sim {\rm{r}}} \right)\)

\(= {\rm{T}}\)

The truth evaluation of Option_1 doesn’t depend on the value of r. If the value of r is True (T), then also this function will evaluate to T. Hence, it becomes the condition of AT LEAST TWO an fails for the condition of Exactly Two.

Option_2

\(\left( {\sim \left( {p \leftrightarrow q} \right) \wedge r} \right) \vee \left( {p \wedge q \wedge \sim r} \right)\)

 \(= taking;p = T;and;q = T,;;\left( {\sim \left( {T \leftrightarrow T} \right) \wedge r} \right) \vee \left( {T \wedge T \wedge \sim r} \right)\)

\(= \left( {\sim \left( T \right) \wedge r} \right) \vee \left( {T \wedge \sim r} \right)\)

\(= \left( {\sim\left( T \right) \wedge r} \right) \vee \left( {T \wedge \sim r} \right)\)

\( = \left( {F \wedge r} \right) \vee \left( {T \wedge \sim r} \right)\)

\(= \left( F \right) \vee \left( { \sim r} \right)\)

\(= \sim r\)

If r = F, then the output = T

else output = F.

Hence, Option_2 evaluates to T only when exactly p and q are True and r is necessarily False.

The same can be tried with keeping p and r as T OR q and r as T initially.

Option_3

\(\left( {\left( {p \to q} \right) \wedge r} \right) \vee \left( {p \wedge q \wedge \sim r} \right)\)

\(= taking;p = T;and;q = T,;;\left( {\left( {T \to T} \right) \wedge r} \right) \vee \left( {T \wedge T \wedge \sim r} \right)\)

\(= \left( {\left( T \right) \wedge r} \right) \vee \left( {T \wedge \sim r} \right)\)

\(= \left( r \right) \vee \left( { \sim r} \right)\)

\(= T\)

The evaluation of final output does not depend on the value of r. Hence, the condition of EXACTLY TWO variables as T fails.

Option_4

\(\left( { \sim \left( {p \leftrightarrow q} \right) \wedge r} \right) \wedge \left( {p \wedge q \wedge \sim r} \right)\)

\(= taking;p = T;and;q = T,;;\left( {\sim\left( {T \leftrightarrow T} \right) \wedge r} \right) \wedge \left( {T \wedge T \wedge \sim r} \right)\)

\(= \left( {\sim \left( T \right) \wedge r} \right) \wedge \left( {T \wedge \sim r} \right)\)

\(= \left( {F \wedge r} \right) \wedge \left( {T \wedge \sim r} \right)\)

\(= \left( F \right) \wedge \left( { \sim r} \right)\)

\(= F\)

The expression evaluates to F with r = T and also with r = F. Hence, with at least two variables as T, this evaluates to F.

Concept:

In inner query and outer query are correct and following all properties:

• GROUP BY clause is used with the select statement.
• GROUP BY clause is placed after the where clause.
• Whatever attribute is present in GROUP BY clause remaining all attribute should be associated with aggregate functions in select statement.
• Two value can be compared simultaneously using IN  but any and some cannot.
• To join two table we should have one common attribute . ( here dept-id is common )

Hence this query executes and gives correct answer; hence option 2 is the correct answer

Concept:

In both the cases number of Instructions will be same

\({\rm{Number;of;instructions}} = {\rm{;}}\frac{{{\rm{Total;time}}}}{{{\rm{CPI*Clock;time}}}}\) 

\({\rm{Clock;frequency;}}\left( {{\rm{;f;}}} \right) = \frac{1}{{{\rm{Clock;time}}}}\) 

\({\rm{Number;of;instructions}} = {\rm{;}}\frac{{{\rm{Total;time}}}}{{{\rm{CPI}}}} \times {\rm{Clock;frequency}}\)

Calculation:

Total time ratio: P1: P2 = 100: 75 = 4:3

CPI ratio: CPI1: CPI2 = 100: 120 = 5:6

\(\frac{{{\rm{P}}1}}{{{\rm{CPI}}1}} \times {\rm{f}}1 = \frac{{{\rm{P}}2}}{{{\rm{CPI}}2}} \times {\rm{f}}2 = \frac{4}{5} \times 1 = \frac{3}{6} \times {\rm{f}}2,{\rm{;;f}}2 = \frac{8}{5} = 1.6{\rm{;GHz}}\)