GATE CS 2015 Official Paper: Shift 3 (Previous Year Paper)

Extraneous - meaning irrelevant/ unconnected / unrelated to the requirements of the exam. It is the right answer because a students desire to focus on aceing their tests makes them avoid anything unrelated to their exams.

Related - means connected

Outside - means a place on the exterior

Useful - is something that will help - this is incorrect to the context because if something is useful no student would avoid it or ‘close their minds’ so to say.

A child is treated from birth till the age of youth by mostly the same Pediatrician or a child specialist; similarly

A female is treated for practically all her ailments specially child bearing period by mostly the same Gynecologist., who is also called a women’s doctor, just like a Pediatrician is called a children’s doctor. So this is the right answer.

‘Orthopedist ‘ treats bone injuries and an adult will go to be treated by him for a very short time, that too in case of such an injury

‘Nephrologist’ treats diseases related to kidneys.

Dermatologist- a specialist in dermatology, especially a doctor who specializes in the treatment of diseases of the skin

First blank - The definite article‘The’ as a particular film is named

Second blank - ‘Last week’ refers to a past tense as also does the word ‘cleared’ so the auxiliary ‘was’ is appropriate.

Third blank - To agree with the past tense in the first part this blank also needs the same so ‘found’ is appropriate.

Fourth blank - ‘On’ is appropriate here as a particular day is named.

So ‘C’ is the right answer

Each letter is replaced by the letter that comes three places after it in alphabetical order.

R + 3 = U,

O + 3 = R,

A + 3 = D,

D + 3 = G

Therefore, SWAN will become,

S + 3 = V,

W + 3 = Z,

A + 3 = D,

N + 3 = Q

Therefore, the required word is VZDQ.

Given, function f(x) is linear

Let the linear function be f(x) = ax + b, where a and b are constants

Now, f(x) has a value of 29 at x = – 2 and 39 at x = 3

∴ -2a + b = 29 and 3a + b = 39

Solving the above two equations we get, a = 2 and b = 33

f(x) = 2x + 33

Now value of f(x) at x = 5

f(5) = 2 × 5 + 33 = 43

Explanation:

'A' ‘Turned his attention’ means that since Persia was conquered now he felt the desire to conquer some other territory. So ‘A’ is valid and can be inferred from the above sentence.

‘B’ is ambiguous and can’t really be validated

‘C’ too seems not very clear, because being a king who had already marched against many kingdoms, he definitely must have had control of his army, though if history is read further his army had revolted after his fight with the Indian king Porus.

‘D’ This too is not logically valid as it may or may not have been the reason as Persia did not extend to the Indian borders if history is to be believed.

Explanation:

The statements that are logically valid and can be inferred from the above passage are ii and iii 

Because in the given lines we are told that though ‘he had all the technical skills required to be a batsman of the highest order, he had thrown away his wicket several times, due to lack of requisite temperament’ telling us very clearly that he could become a great batsman and had lost out many times after ‘working hard to lay a strong foundation’ due to his ‘temperament’ hence both (ii and iii) are valid and can be inferred from the above passage.

Concept:

Combined imports and exports in the year 2000 = 50 + 40 = 90 crores

Combined imports and exports in the year 2001 = 60 + 50 = 110 crores

Combined imports and exports in the year 2002 = 70 + 60 = 130 crores

Combined imports and exports in the year 2003 = 60 + 70 = 130 crores

Combined imports and exports in the year 2004 = 70 + 80 = 150 crores

Combined imports and exports in the year 2005 = 70 + 90 = 160 crores

Combined imports and exports in the year 2006 = 100 + 120 = 220 crores

Combined imports and exports in the year 2007 = 110 + 120 = 230 crores

% increase in combined imports and exports in the year 2001 \(= \frac{{110 - 90}}{{90}} \times 100% = 22.22% \)

% increase in combined imports and exports in the year 2002 \(= \frac{{130 - 110}}{{110}} \times 100% = 18.18% \)

There is no increase in 2003.

% increase in combined imports and exports in the year 2004 \(= \frac{{150 - 130}}{{130}} \times 100% = 15.38% \)

% increase in combined imports and exports in the year 2005 \(= \frac{{160 - 150}}{{150}} \times 100% = 6.67%\)

% increase in combined imports and exports in the year 2006 \(= \frac{{220 - 160}}{{160}} \times 100% = 37.5%\)

% increase in combined imports and exports in the year 2007 \(= \frac{{230 - 220}}{{220}} \times 100% = 4.54% \)

Thus % increase in combined imports and exports in the year 2006 is highest.

For all values of y > 0, x = 0                        ------- (1)

The line below the x axis passes through origin (0, 0) and (2, -1)

Equation of line is given by

x/2 – y/1 = 0

∴ x = 2y for y < 0

|x| = x for both x > 0 and x < 0

Now from equation (1)

x = 0 for y > 0

∴ x = y – y for y > 0

Also x = y + y for y < 0

∴ x = |y| - y for all y.

The above equation can also be written as follows

x = -(y - |y|)

Let us check each option,

a) R has received a portfolio (Power) that is neither home nor finance, therefore this does not fulfil the given conditions.

b) R has received Home, S and Q have power and telecom, and P and T both have portfolios while U does not, thereby satisfying all conditions.

c) S and U both have portfolios, therefore making this impossible.

d) R has received a portfolio that is neither home nor finance, therefore this does not fulfil the given conditions.

Therefore, b is the correct distribution.

Where \0 is a null character 

After *p = '0';   \s1[2] = '0'

100  101 102 103  104

printf(“%s”, s1) will print all starting from address location 100 until the null character.

Output: 1204

\(X\text\Y=X\cap Y'\)

\(Y'\text\X'=Y'\cap (X')'= Y'\cap X\)

Hence, \(X\text\Y=Y'\text\X'\)

Concept:

The closure of F, denoted as F+, is the set of all regular FD, that can be derived from.

For trivial functional dependency,

Let A and be two sets consists of attributes of a relation

A → B

A \(\supseteq\) B 

Explanation:

Option 1: 

{P, R} → {S, T}

{P, R} \(\nsupseteq\) {S, T}

Not a trivial functional dependency

Option 2: 

{P, R} → {R, T}

{P, R} \(\nsupseteq\) {R, T}

Not a trivial functional dependency

Option 3: 

{P, S} → {S}

{P, S} \(\supseteq\) {S}

It is a trivial functional dependency

Option 4: 

{P, S, U} → {Q}

{P, S, U} \(\nsupseteq\) {Q}

Not a trivial functional dependency

NOTE:

\(\supseteq\) → superset

\(\nsupseteq\) → not superset

Important Points

The size of the ready queue doesn’t depend on the number of processes. A single processor system may have a large number of processes waiting in ready queue  

Additional Information   

Transition Diagram:

Important Points:

n CPUs → maximum n process in running state

Power: LR(0) < SLR(1) < LALR(1) < CLR(1)

Implementation complexity:

LR(0) < SLR(1) < LALR(1) < CLR(1)

Hence out of given options, SLR is

Easiest to implement and CLR is most powerful.

\(\left( {P \ne Q} \right) \ne R = \overline {\left( {\bar P + \bar Q} \right)} + \bar R = PQ + \bar R\)

\(\ P \ne \left( {Q \ne R} \right) = \bar P + \overline {\left( {\bar Q + \bar R} \right)} = \bar P + Q\bar R \)

∴ S1 is FALSE

But

\(Q \ne R = \bar Q + \bar R = \bar R + \bar Q = R \ne Q\)

∴ S2 is TRUE

Important Points 

𝑋 \(\ne\) 𝑌 = 𝑋′ + 𝑌′ = *(*𝑋.𝑌)'  

It is a NAND operation and NAND is commutative but not associative

Concept:

Function point metrics provide a standardized method for measuring the various functions of a software application

Formula:

The value of function point metric = UPF × VAF

Calculation:

UPF = 4 × 30 + 60 × 5 + 23 × 4 + 8 × 10 + 7 × 2 = 606

VAF = TDI × 0.01 + 0.65

TDI = 3 × 4 + 0 × 4 + 4 × 6 = 36

VAF = (TDI × 0.01) + 0.65

= 36 × 0.01 + 0.65

= 0.36 + 0.65

= 1.01

FP = UPF × VAF

= 1.01 × 606

= 612.06

Important Point:

TDI: Total Degree of Influence

UPF: Unadjusted Function Point (UFP) count

VAF: Value Adjustment Factor

Option 2: correct

The tag specifies the base URL/target for all relative URLs in a document. There can be at maximum one element in a document, and it must be inside the element

Transmission Control Protocol (TCP):

• TCP is a reliable connection-oriented protocol that can be used in any application where reliability is important.
• TCP explicitly defines to provide a connection establishment, data transfer, and connection teardown phases to provide a connection-oriented service.
• TCP connections are full-duplex
• TCP uses GBN and SR protocols to attain reliability. Therefore it has selective acknowledgment.
• It provides end-to-end communication due to the port number of source and destination.
• TCP connections are byte streams.

Hence statement I is correct

Answer: Option 3

Explanation:

\(\begin{array}{l} \mathop \sum \limits_{i = 0}^n {i^3} = \frac{{{n^2}{{\left( {n + 1} \right)}^2}}}{4}\ \frac{{{n^2}{{\left( {n + 1} \right)}^2}}}{4} = O\left( {{n^4}} \right)\ \frac{{{n^2}{{\left( {n + 1} \right)}^2}}}{4} = O\left( {{n^5}} \right)\ \frac{{{n^2}{{\left( {n + 1} \right)}^2}}}{4} = {\rm{\Omega }}\left( {{n^3}} \right) \end{array}\)

\(\frac{n^2(n+1)^2}{4} = \theta(n^4)\)

\(\frac{n^2(n+1)^2}{4} \ne \theta(n^5)\)

Therefore option 3 is correct

Types of nodes in a Binary Tree:

Interval (i):

(i) Root node (single node), degree = 2

(ii) Node with 1 child, degree = 2

(iii) Non root node with 2 children, degree = 3

Load (l):

Degree = 1

Total nodes = n = i + l

Also \(\mathop \sum \limits_{i = l}^n {d_i} = 2\left( {n - 1} \right)\)

\(2 + {i_1} \times 2 + {i_2} \times 3 + l \times 1 = 2\left( {n - 1} \right)\)

Also, \(n = 1 + {i_1} + {i_2} + l\)

\(\begin{array}{l} {i_1} = n - l - {i_2} - 1\ \therefore 2 + \left( {n - l - {i_2} - 1} \right) \times 2 + {i_2} \times 3 + l \times 1 \end{array}\)

= 2n – 2

\(\begin{array}{l} {i_2} - l = - 2\ {i_2} = l - 2 \end{array}\)

Also, Total number of interval nodes with

2 children = i₂ + 1(root)

\(= l-2 + 1 = l-1\)

= 200 - 1 = 199

Data:

number of slots = 25

number of elements = 2000

Formula:

\({\rm{Load;factor}}\left( {\rm{\alpha }} \right) = \frac{{{\rm{number;of;elements}}}}{{{\rm{number;of;slots}}}}{\rm{;}}\)

Calculation:

\({\rm{Load;factor}}\left( {\rm{\alpha }} \right) = \frac{{2000}}{{25}} = 80{\rm{;}}\)

For a given matrix A if V is the eigen vector corresponding to the eigen value λ, then:

AV = λV

\(\left[ {\begin{array}{*{20}{c}} 1&{ - 1}&2\ 0&1&0\ 1&2&1 \end{array}} \right]\left[ {\begin{array}{*{20}{c}} { - 4\alpha }\ {2\alpha }\ {1\alpha } \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} { - 4\alpha }\ {2\alpha }\ {1\alpha } \end{array}} \right] = 1.\left[ {\begin{array}{*{20}{c}} { - 4\alpha }\ {2\alpha }\ {1\alpha } \end{array}} \right]\)

\(\therefore \left{ {\left. {\alpha \left( { - 4,;2,;1} \right)} \right|\alpha ; \ne ;0,;\alpha \epsilon R} \right}\) are the corresponding eigenvectors.

\(Let; L =\mathop {\lim }\limits_{x \to \infty } \left( {1 + {x^2}} \right)^{e^{ - x}}\)

Taking log_a on both sides where a is positive integer

\()\(log_aL =\mathop {\lim }\limits_{x \to \infty } log_a\left( {1 + {x^2}} \right)^{e^{ - x}}\)

\(log_a L =\mathop {\lim }\limits_{x \to \infty } e^{ - x}log_a\left( {1 + {x^2}} \right)^{}\)

\(log_aL =\mathop {\lim }\limits_{x \to \infty } \frac{log_a\left( {1 + {x^2}} \right)^{}}{e^{ x}}\)

\(It; is; of; \frac{\infty}{\infty}; form\)

Using L’hopital rule

log_aL = 0

∴ L = a⁰

∴ L = 1

Starting with digit  3:

3333

Starting with digit  2:

2222, 2223, 2233, 2333

Starting with digit  1:

1111, 1112, 1113, 1122, 1123

1133, 1222, 1223, 1233, 1333

The number of 4 digit numbers having their digits in non – decreasing order = 1 + 4 + 10 = 5

Alternate Method:

Dynamic Programming Approach:

The number of 4 digit numbers having their digits in non – decreasing order = 1 + 4 + 10 = 5

H: Result is head.

T: Result is tail.

T1: Teller is type 1.

T2: Teller is type 2.

P = “Result is head if and only if I am in type 1”

P = HʘT1

CASE 1: P = FALSE (i.e Teller is type 2)

\(\begin{array}{l} \bar H.\overline {T1} + H.T1 = FALSE\ T.T2 + H.T1 = FALSE\ T.T2 + H.T1 = FALSE \end{array}\) 

T = FALSE

\(\therefore \bar T = TRUE\), thus result is Head.

CASE 2: P = TRUE (i.e. teller is type 1)

\(\begin{array}{l} \bar H.\overline {T1} + H.T1 = TRUE\ T.T2 + HT1 = TRUE\ T.O + H = TRUE \end{array}\) 

∴ H = TRUE

Hence output is Head in both cases.

In a BST, inorder traversal is always sorted.

Hence 67 is at lowest level.

Calculation:

Postfix expression 10 5 + 60 6 / * 8 −

PUSH: 10 and 5(TOS)

Add: 10 + 5 = 15

PUSH: 15 60 6 (TOS)

Divide: 60/6 = 10

PUSH: 10

Multiply: 15 × 10 = 150

PUSH: 150 and 8

Subtract: 150 - 8 = 142

Diagram:

Evaluate Infix notation:

(((10 + 5) * (60 / 6)) - 8)  = ((15 * 10) - 8) = 150 - 8 = 142

SELECT P1.address

FROM Cinema P1

WHERE P1. Capacity > = All (select P2. Capacity from Cinema P2)

The above query will find the addresses of theatres with maximum capacity.

Hence 3 interchanges will be required.

As both processes can enter in critical section at the same time, mutual exclusion is not satisfied.

Number of states in DFAs accepting L and L̅ is always equal.

DFA accepting (0+1) * 0011 (0+1)* is:

Hence DFA accepting L̅ will be

It has 5 states.

As both real and artificial faults have the same distribution, they will be detected in same proportions.

≠ A.F. = 100

≠ R.F. = x

A fraction of faults detected

\(= \frac{{75}}{{100}} = \frac{3}{4}\)

∴ Detected real faults \(= \frac{3}{4}x = 159 - 75 = 84\)

number of real faults = \(\frac{84\times 100}{75}\) = 112

Therefore, undetected real faults = 112- 84 = 28

Hence Tag and line no. are E and 201 respectively.

B = 10⁸ bits/sec

d = 1 km

Round trip distance = 2 km

To detect a collision, the sender must be transmitting when it receives the collision signal so that it can transmit again.

\(\begin{array}{l} \therefore \frac{{1250 \times 8}}{{{{10}^8}}} = \frac{2}{{speed}}\ \therefore speed = \frac{{2 \times {{10}^8}}}{{{{10}^4}}} = 2 \times {10^4 } \end{array}\)

Concept:

Simpson’s method is a method for numerical integration, the numerical approximation of definite integrals which is given as:

\(\mathop \smallint \nolimits_a^b f\left( x \right)dx = ;\frac{{\Delta x}}{3}\left( {f\left( {{x_0}} \right) + 4f\left( {{x_1}} \right) + 2f\left( {{x_2}} \right) + 4f\left( {{x_3}} \right) + \ldots + 4f\left( {{x_{n - 1}}} \right) + f\left( {{x_n}} \right)} \right)\)

Where,

\(\Delta x = \frac{{b - a}}{n}\)

Data:

Motion starts at t= 0 and ends at t = 20. So, speed function will be integrated in the range of t = 0 to t = 20. So, b = 20, a= 0, n = 10

Calculation:

\(Distance = ;;\frac{{;b - a}}{{3n}}\left[ {f\left( 0 \right) + 4f\left( 2 \right) + 2f\left( 4 \right) + 4f\left( 6 \right) + 2f\left( 8 \right) + 4f\left( {10} \right) + 2f\left( {12} \right) + 4f\left( {14} \right) + 2f\left( {16} \right) + 4f\left( {18} \right) + 2f\left( {20} \right)} \right]\)

\( = \frac{2}{3}\left[ {f\left( 0 \right) + 4\left{ {f\left( 2 \right) + f\left( 6 \right) + f\left( {10} \right) + f\left( {14} \right) + f\left( {18} \right)} \right} + 2\left{ {f\left( 4 \right) + f\left( 8 \right) + f\left( {12} \right) + f\left( {16} \right) + f\left( {20} \right)} \right}} \right]\)

\( = ;\frac{2}{3}\left[ {0 + 4\left( {10 + 25 + 32 + 11 + 2} \right) + 2\left( {18 + 29 + 20 + 5} \right)} \right]\)

\( = ;\frac{2}{3}\left[ {0 + 320 + 144} \right]\)

= 309.33

Concept:

Merge sort algorithm worst case time complexity is O (nlogn)

Data:

T₁ (n) =30 seconds, n₁ = 64

T₂ (n) = 6 minutes

Formula:

T(n) = nlog₂n

Calculation:

30 = c × 64 log₂(64)

30 = c × 64 log₂(2⁶)

30 = c × 64 × 6

\(c = \frac{5}{{64}}\)

6 × 30 = c n₂ log₂n₂

\(6 \times 60 = \frac{5}{{64}} \times {n_2}{\log _2}{n_2}\)

∴ n₂ = 512

The maximum input size of a problem that can be solved in 6 minutes is 512

Total 24 + 1 = 25 times get() function will be invoked.

Last 1 call will be of get (6).

Recurrence relation for this will be: T(n) = T (n-1) + T (n- 3) + 2

Concept:

Order of an internal node (non – leaf node) of the tree is the maximum number of children it can have.

Data for B+ Tree:

Disk Block size = D=1024 byte

Block pointer = B = 8 byte

Key field = K = 12 byte.

Record or data pointer = R = 10 byte

Order = p

Formula:

p × B + (p – 1) (K) ≤ D

Calculation:

p × 8 + (p – 1) (12) ≤ 1024

8p + 12p ≤ 1024 + 12

20p ≤ 1036

p ≤ 51.8

∴ p = 51

Number of key = p – 1 = 51 - 1 = 50

Concept:

Sum of product (SOP) – The concept of sum of products mainly includes minterm. Minterm is a Boolean expression resulting in 1 for the output of a single cell and 0’s for all other cells in K-Map. MInterm is all the 1’s in the truth table.

Product of sum (POS) – Product of sum mainly includes max term. Max term is a Boolean expression resulting in 0 for the output of a single cell and 1 for all other cells in K-Map. Maxterm is all the 0’s in the truth table.

Explanation:

Function: F = P’ + QR

Construct the truth table for this function:

Here \(\sum = \left( {0,;1,;2,;3,7} \right)\) means sum of product which is all the 1’s in output of truth table.

\(\prod = \left( {4,;5,;6} \right)\) means product of sum which is all the 0’s in the output of truth table.

K-MAP for the given function :

F = P’ + QR

So, here S2 and S3 is true.

S1 and S4 is false.

Concept:

If a problem A is polynomial time reducible to problem B. So, B is at least as hard as A.

Explanation:

Here, L₁ is polynomial time reducible to L₂, L₂ is at least as hard as L₁.

L₃ is polynomial time reducible to L₂

L₂ is polynomial time reducible to L_4.

Option 1:

if L₄ ∈ P, then L₂ ∈ P

L₂ is polynomial time reducible to L₄. L₄ belongs to P type problem then L₂ is also P type problem. So, it is true.

Option 2:

if L₁ ∈ P or L₃ ∈ P, then L₂ ∈ P

If L₁ belongs to P or L₃ belongs to P, then L₂ belongs to P. This is not true because L₁, L₃ is a polynomial time reducible to L₂ not L₂ is polynomial time reducible to L₁.

Option 3:

L₁ ∈ P, if and only if L₃ ∈ P

L₁ belongs to P, if and only if L₃ belongs P. This is false because L₃ is polynomial time reducible to L₂ not L₁.

Option 4:

if L₄ ∈ P, then L₁ ∈ P and L₃ ∈ P

This statement is true because we know that L₁ is polynomial time reducible to L₂ and L₃ is polynomial time reducible to L­₂ and L₂ is polynomial reducible to L₄ so L₁ and L₂ is polynomial time reducible to L₄.

First call to f1( )

int f1( ) { int x = 25; x++; return x; } // it will return x as 26

Next call to f2():

int f2( ) { static int x = 50; x++; return x; } // it will return x as 51

Next call to f3( ):

int f3( ) { x *= 10; return x} ; // it will return x = 100 because global value for x = 10

Next call to f2() :

int f2( ) { static int x = 50; x++; return x; } // As, x is static, it will return x as 52

Final value will be :

x = x + f1( ) + f2( ) + f3( ) + f2( )

= 1 + 26 + 51 + 100 + 52 = 230

It will print the output 230.

Concept:

Rule of pointer arithmetic: When two pointers are subtracted belonging to same array then result is number of elements separating them.

Explanation:

Consider integer size as 2 bytes. Consider base address of array as 100.

Let array p base address is 200 and double ptr base address is 300

ptr++;                             // It points to address 202

ptr – p 

\(\frac{{address;of;ptr; - ;address;of;p}}{{size;of;int}}; = \frac{{202 - 200}}{2} = 1;\)

** ptr = ** 202 = * (a+3) = 40

printf(“%d%d”, ptr – p, **ptr) ;

It will print 140

(I) \({L_1} = \left{ {{a^m}{b^n}{a^n}{b^m}|m,;n \ge 1} \right}\)

Using just one stack we can recognise it.

(II) \({L_2} = \left{ {{a^m}{b^n}{a^m}{b^n}|m,;n \ge 1} \right}\)

Can not be recognised using single stack because crossing of order.

(III) \({L_3} = \left{ {{a^m}{b^n}|m = 2n + 1} \right}\)

We can push all ‘a’s in stack with are extra ‘a’ later we can pop 2 a’s for every input b.

Concept:

A deadlock will not occur if one of the following four conditions doesn’t occur :

• Mutual exclusion: it prevents simultaneous access to a shared resource.
• Hold and wait: Process is holding a resource that may be required by other processes.
• Circular wait: It means there are processes which are waiting for other processes to finish.
• No pre-emption: If a process that is holding some resources requests another resource and that  resource cannot be allocated to it, then it must release all resources that are currently allocated to it.

Explanation:

Option 1:

Processes should acquire all their resources at the beginning of execution. If any resource is not available, all resources acquired so far are released. If this is allowed , then hold and wait will never occur. So, deadlock will not occur.

Option 2:

The resources are numbered uniquely, and processes are allowed to request for resources only in increasing resource numbers. It violates circular wait .

Option 3:

The resources are numbered uniquely, and processes are allowed to request for resources only in decreasing resource numbers. It also violates circular wait.

Option 4:

The resources are numbered uniquely. A process is allowed to request only for a resource with resource number larger than its currently held resources. It also violates circular wait.

So, all options are needed to prevent deadlock.

Binary representation if given IP address is => 11001000 00001010 00001011 10010000

The first address in the block can be found by setting the rightmost 32 - n bits to 0.

The last address in the block can be found by setting the rightmost 32 - n bits to 1.

Here prefix length, n = 27

Set the last 32 - 27 = 5 bits to 1.

Last address => 11001000 00001010 00001011 10011111 => 200.10.11.159​

But it is the network broadcast address. Hence last address will be 11001000 00001010 00001011 10011110 => 200.10.11.158

Data:

Distance = 8000 km

Bandwidth = 500 × 10⁶ bits per second

Propagation speed = 4 × 10⁶ meters/second

Average packet size = 10⁷ bits

Formula:

\({\rm{Transmission;time}} = \frac{{{\rm{packet;size}}}}{{{\rm{bandwidth}}}}\)

\({\rm{Propagation;time}} = \frac{{{\rm{Distance}}}}{{{\rm{velocity}}}}\)

Calculation:

\({\rm{Transmission;time}} = \frac{{{{10}^7}}}{{500 \times {{10}^6}}} = 0.02;seconds\)

\({\rm{Propagation;time}} = {\rm{;}}\frac{{8000 \times 1000}}{{4 \times {{10}^6}}} = 2{\rm{;seconds}}\)

RTT = 2 × Propagation time = 2 × 2 = 4 seconds

Number of packets that can be transmitted (window size) = 4/ 0.02 = 200

Window size in GO BACK – N protocol = 2ⁿ – 1 (where n is the number of bits for sequence number)

2ⁿ – 1 = 200

2ⁿ = 201, n = 8

Find the forbidden and permissible latencies in this.

Here, S₁ is needed at time 1 and 5, So forbidden latency = 5 -1 = 4

S₂ is needed at time 2 and 4, so, forbidden latency = 4 – 2 = 2

Forbidden latencies = 0, 2, 4 (0 by default)

Permissible latencies = 1, 3, 5 (any value more than 5 also)

Pipeline collision vector = [ 1 0 1 0 ]          // state 1

We have taken c = 1 for forbidden and c= 0 for permissible.

Collision vector for next cycle = 1111

It is by shifting right 1 bit to collision vector and perform OR operation to result with collision vector.

Similarly, after 3 cycles = collision vector = [1011]

After 5 or more cycles = [1010]

State 2: [1111]

Reaches state 1 [1010] after 5 or more cycles.

State 3: [1011]

Reaches state [1011] after 3 cycles and reaches state 1 [ 1010] after 5 or more cycles.

After this, state diagram will be:

Here, latency cycle = 3 and (1, 5)

Greedy cycle is (1,5)

Minimum average latency = (1+ 5)/ 2 = 3

Concept:

Anti- dependence: It is also known as write after read, occurs when an instruction requires a value that is later updates.

Anti-dependency can be overcome in pipeline using register renaming.

Explanation:

Instructions are:

I₁: R1 = R2 + R3

I₂: R7 = R1 * R3

I₃: R4 = R1 – R5

I₄: R3 = R2 + R4

I₅: R7 = R8 * R9

Here, in this anti- dependencies (WAR) are:

I₁ – I₂

I₁ – I₃

I₃ – I₄

I₄ – I₁

I₄ – I₂

Statement 1: There is an anti-dependence between instructions I₂ and I₅

This statement is false, I₂ and I₅ don’t form any write after read operation. There is no anti dependency in this.

Statement 2: There is an anti-dependence between instructions I₂ and I₄

This statement is true, here I₂ reads R3 and I₄ writes it.

Statement 3: Within an instruction pipeline an anti-dependence always creates one or more stalls

This statement is false as anti- dependency can be removed by using register renaming in pipeline.

Code segment 1:

                //initialize elements of y to 0

                //initialize elements X[i] [j] of X to i+j

                      for (i = 0; i < n; i++)

                                Y[i] += X[0] [i];

As, it is given that y element are initially 0 and x elements are i+j

Consider n = 5

So, final contents in array y= [0, 1, 2, 3, 4]

Code segment 2:

//initialize elements of Y to 0

                //initialize elements X[i] [j] of X to i+j

                       for (i = 0; i < n; i++)

                                Y[i] += X[i] [0];

Consider n = 5

Final contents of array y in this code segment = [0, 1, 2, 3, 4]

Statement S1: Final contents of array Y will be same in both code segments

As, it is clear that, final contents of array Y is same in both code segments. This is true.

Statement S2: Elements of array X accessed inside the for loop shown in code segment 1 are contiguous in main memory

In C programming, array are stored in row major order which gives address of each element in sequential order means we cross single element each time to move next shows, contiguous in memory. So, this is true.

Statement S3: Elements of array X accessed inside the for loop shown in code segment 2 are contiguous in main memory

In code segment 2, y[i] += x[i][0]

Means we are crossing n element to move next, so elements of array X accesses inside the for loop are not contiguous in memory in code segment 2.

Concept:

Recoverable schedule: A schedule is said to be recoverable in which for every transaction T_i and T_j , if T_j is reading a data item that is written by T_i then the commit operation of T_i must before the commit operation of T_j.

Aborting: Aborting means to disrupt the action by killing the current ongoing transaction.

Explanation:

Option 1: Incorrect

As, it is not giving any surety about T1, there is no commit in T1.  Rolling back of T2 may not be required in this.

Option 2: Correct

In given schedule, T2 is reading data item A that is written by T1 so it means commit of T1 must before the commit of T2, but here in this schedule it is not happening. So, this is non – recoverable schedule. In this after T1 fails, if we want to undo all the operations, still we cannot undo a committed transaction. So, it cannot ensure transaction atomicity.

Option 3: Incorrect

It is redoing all the operations of T2. But in this, it is reading data item A that is written by T1 and T1 is not committed. So, it results in dirty read problem.

Option 4: Incorrect

Since Schedule S is non – recoverable. So, it is incorrect. Also, it cannot ensure atomicity.

Concept:

If rank of 3 × 3 homogeneous matrix is less than 3 then the corresponding equations will have non-trivial solutions.

Explanation:

For non-trivial solution

\(\left| {\begin{array}{*{20}{c}} p&q&r\ q&r&p\ r&p&q \end{array}} \right| = 0\)

R₁ = R₁ + R₂ + R₃

\(\left| {\begin{array}{*{20}{c}} {p + q + r}&{;q + r + p}&{r + p + q}\ q&r&p\ r&p&q \end{array}} \right| = 0\)

\(\left( {p + q + r} \right)\left| {\begin{array}{*{20}{c}} 1&{;1}&1\ q&r&p\ r&p&q \end{array}} \right| = 0\)

∴ p + q + r = 0

(OR)

\(\left| {\begin{array}{*{20}{c}} 1&{;1}&1\ q&r&p\ r&p&q \end{array}} \right| = 0\)

∴ p = q = r

The correct answer is 10.

Concept:

• The break statement is used inside the switch to terminate a statement sequence. When a break statement is reached, the switch terminates, and the flow of control jumps to the next line following the switch statement.
• The break statement is optional. If omitted, execution will continue into the next case. The flow of control will fall through to subsequent cases until a break is reached or the switch block gets executed.

Explanation:

k = 0

j = 2 * 3 / 4 + 2.0 / 5 + 8 / 5

j = 6/4 + 0 + 1               //integer division

j = 1 + 0 + 1 = 2

k -= --j;

∴ k = k – (--j) = 0 – (1) = – 1;

lets consider m = i + k

The number of times the print statement is executed is 10 times.

Hence the correct answer is 10.

Given x as non- zero,

\(af\left( x \right) + bf\left( {\frac{1}{x}} \right) = \frac{1}{x} - 25\)       ---(1)

Consider x as 1/x

\(af\left( {\frac{1}{x}} \right) + bf\left( {\frac{1}{{\frac{1}{x}}}} \right) = x - 25\)

\(af\left( {\frac{1}{x}} \right) + bf\left( x \right) = x - 25\)       ---(2)

Multiply equation 1 by a and 2 by b and subtract both

\({a^2}f\left( x \right) + abf\left( {\frac{1}{x}} \right) - abf\left( {\frac{1}{x}} \right) - {b^2}f\left( x \right) = \frac{a}{x} - 25a - bx + 25b\)

\({a^2}f\left( x \right) - {b^2}f\left( x \right) = \frac{a}{x} - 25a - bx + 25b\)

\(f\left( x \right) = \frac{a}{{x\left( {{a^2} - {b^2}} \right)}} - \frac{{bx}}{{{a^2} - {b^2}}} - \frac{{25\left( {a - b} \right)}}{{{a^2} - {b^2}}}\)

\(\mathop \smallint \limits_1^2 f\left( x \right)dx = \frac{1}{{{a^2} - {b^2}}}\left[ {a\left( {\ln 2 - 25} \right) + \frac{{47b}}{2}} \right]\)

Data:

W(MST) = 500

V = 100

Increase in weight = wt = 5

Concept:

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges(V – 1 ) of a connected, edge-weighted undirected graph G(V, E) that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Explanation:

W(MST) = x + y + w

New W(MST) = x + y + w + 5 + 5 + 5 = x + y + w + 15

Formula:

New W(MST) = W(MST) + wt × (V – 1)  

Calculation:

New W(MST) = 500 + 5 × (100 – 1)

New W(MST) = 995

Note:

W(MST) → Weight of minimum spanning tree

New W(MST) → new Weight of minimum spanning tree

Data:

Packet size = 10000

Packet size1 = 5000 and packet size2 = 5000

Bandwidth = 10⁷ b/s

Propagation delay = T_p = 20 μs

Queuing delay = T_q = 35 μs

Formula:

\({\rm{Transmission;delay}} = {{\rm{T}}_{\rm{t}}} = {\rm{;}}\frac{{{\rm{packet;size}}}}{{{\rm{Bandwidth}}}}{\rm{;}}\) 

Calculation:

Packet 1:

Source:

\({{\rm{T}}_{\rm{t}}} = \frac{{5000}}{{{{10}^7}}} = ; = 500;\mu s\) 

T_p = 20 μs

T_q = 35 μs

Router:

\({{\rm{T}}_{\rm{t}}} = \frac{{5000}}{{{{10}^7}}} = 500;\mu s\) 

T_p = 20 μs

As soon as packet1 is transmitted on link

Packet2 will start its transmission

Source:

\({{\rm{T}}_{\rm{t}}} = \frac{{5000}}{{{{10}^7}}} = ;500;\mu s\) 

Transmission same as packet

Total time = 500 + (500 + 20 + 35 + 500 + 20) = 1575 μs

The time elapsed between the transmission of the first bit of data and the reception of the last bit of the data in microseconds is 1575 μs

Scheduling Algorithm:

First come first serve

Gantt chart:

0                 3                  9                 13               15

Process Table:

Average turnaround time = 29/4 = 7.25

Scheduling Algorithm:

Non pre-emptive shortest job first

Gantt chart:

0            3             9            11           15

Process Table:

Average turnaround time = 27/4 = 6. 75

Scheduling Algorithm:

Shortest remaining time first

Gantt chart:

0           3            4            8           10         15

Process Table:

Average turnaround time = 25/4 = 6.25

Scheduling Algorithm:

Round Robin with Quantum value two

Gantt chart:

0       2       4        5       7        9       11     13     15

Process Table:

Average turnaround time = 33/4 = 8.25

So, shortest remaining time first has the minimum average turnaround time.

Concept:

Cyclomatic complexity is a source code complexity measurement that is being correlated to a number of coding errors.

Formula:

Cyclomatic complexity = e – n + 2p

Where, e = number of edges

n = number of nodes

p = number of nodes that have exit points

Also, cyclomatic complexity = number of predicates + 1

Or, cyclomatic complexity = number of regions

Explanation:

Program X contains three predicates i.e. three conditional statement i.e. 3

So, cylomatic complexity = 3 + 1 = 4

Program Y:  this contains 4 regions.

So, cyclomatic complexity = 4

Program Z: Program Z contains both X and Y. Combining both, it contains 6 predicates .

So, cyclomatic complexity = 6 + 1 = 7

(43)_x = (y3)₈

∴ x > 4 and y < 8

4x + 3 = 8y + 3

4x – 8y = 0

∴ x = 2y and x > 4, y < 8

The number of possible solutions is 5.

Given: ((p, q), (r, s)) ∈ R

Only if p – s = q – r

Consider,

If ((p,q), (p,q)) ∈ R, then, p – q = q – p

It is not true for any positive integer p and q.

So, relation is not reflexive.

For symmetric: if ((p,q),(r,s)) ∈ R then also, ((r,s), (p,q)) ∈ R

Means if p – s = q – r then r – q = s – p

Both are equal, so relation is symmetric.

Formula:

P (A|B) = P (A ꓵ B)/ P(B)

Data:

Y = X1X2 ⊕ X3

Pr[Y = 0|X3 = 0]

Explanation:

Given: X₃ = 0,

To have: Y = 0,  needs X₁.X₂ = 0 that is  {(0,0) (0, 1) (1,0)}

There are totally 4 possibilities - {(0,0) (0,1) (1,0), (1,1)}, out of which 3 are favourable cases.

P (Y = 0 |X3 = 0) = P ((Y = 0) ꓵ (X3 = 0)) ÷  P(X3 = 0) = 3/4

So, required probability = 0.75

f(w, x, y, z) = ∑ (0, 2, 4, 5, 6, 10)

K- Map:

Number of prime implicant is 3.

Initially z = 1, a = 2, n = 8, k = 4

Loop will go from i = 1 to 3

for i = 0, z = 1 mod 8 = 1

c[0] = 1, if (c[i] = 1)     --- true

z = 1 × 2 mod 8 = 2

for i = 2, z = 2² mod 8 = 4

Now c[1] = 0, if condition become false, so z remains 4

For i = 3, z = 4² mod 8 = 0.

After this, z value will always be 0. It can never be non zero.

So, output of DOSOMETHING(c, a, n) is 0.

Concept:

Sin function value ranges from -1 to + 1. (-1, 0, 1)

Explanation:

Case 1: when sin(n) is -1,

g(n) = n^{(1 - 1)} = n⁰ = 1

so, for this case f(n) > g(n) i.e. g(n) = O (f(n))

So, statement 1 is incorrect.

Case 2: when sin(n) is +1,

g(n) = n^{(1 + 1)} = n²

so, for this case f(n) < g(n) i.e. f(n) = O(g(n))

but for this, second statement i.e. f(n) = Ω(g(n)) is incorrect.

Both statements are not true for all values of sin(n).

Hence, option 4 is correct answer.

Concept:

First, check the grammar is ambiguous or not. If a grammar is ambiguous then it cannot be LL(1) and LR(1).

Explanation:

Given grammar is: S → F | H

F → p | c

H → d | c

First derivation for “c”:

S → F → c

Second derivation for “c”:

S → H → c

Two parse tree exists for single string and hence given grammar is ambiguous. It is neither LL(1) nor LR(1).