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

Here the subject is ‘minister’ and a singular, so the verb too has to be singular to agree with it, the verb ‘meet’ in A,B and C is plural so it will be incorrect here; ‘meets’ is plural hence D is the right answer.

A and B have another incorrect usage in it, i.e. the two negatives in the same sentence ‘will not leave’ and ‘does not meet’.

Paraphrase is to rewrite something in a more concise manner, in order to make the meaning clear. Hence this is the right answer.

Paradox is a contradiction

Paradigm is a new view point on something

Paraffin is a flammable oily liquid used in medicine / or wax

Explanation:

‘Figurative’ is a poetic/metaphorical/symbolic way of speech, just like the given sentence the lever and fulcrum are symbols, hence it is the right answer here.

‘Collateral’ is to pledge something as a surety/guarantee for gaining a favor/ thing required

‘Literal’ is the exact meaning of each word, which is not applicable here as no one can ‘move the earth with a fulcrum and a long stick’.

‘Figurine’ is a small statue of a human being usually made with bone china as a decorative piece

Given that the part of the word ‘taga’ is repeated in all, and ‘care’ is repeated in all solutions, we can conclude that taga means care.

Further, ‘fer’ is part of the word careless, so we can conclude that it means ‘less’.

Also, the part ‘taga’ comes in the second half of the word when ‘care’ comes in the first part. Therefore, for ‘care’ to come in the second half, as in ‘aftercare’, taga will have to come in the first half.

Therefore, tagazen could mean aftercare.

Volume of a cube = side³

Surface area of the cube = 6 × side²

Given, cube is built using 64 cubic blocks of side one unit.

∴ side³ = 64

⇒ side = 4 unit

Now, one cubic block is removed from every corner of the cube. This won’t change the surface area of the cube as the number of visible faces remain the same.

Resulting surface area of the body = 6 × 4² = 96 sq. unit

Elegance sells at Rs. 48, Smooth at Rs. 63, Soft at Rs. 78 and Executive at Rs. 173 per piece.

From the table,

Number of Elegance razor sold in a year = 27300 + 25222 + 28976 + 21012 = 102510

Number of Smooth razor sold in a year = 20009 + 19392 + 22429 + 18229 = 80059

Number of Soft razor sold in a year = 17602 + 18445 + 19544 + 16595 = 72186

Number of Executive razor sold in a year = 9999 + 8942 + 10234 + 10109 = 39284

Revenue earned by selling Elegance razor = 102510 × 48 = Rs. 4920480

Revenue earned by selling Smooth razor = 80059 × 63 = Rs. 5043717

Revenue earned by selling Soft razor = 72186 × 78 = Rs. 5630508

Revenue earned by selling Executive razor = Rs. 6796132

Thus, Executive razor contributes the greatest fraction to the revenue of the company in that year.

‘A’ cannot be true as ‘currency notes’ are a minimalistic representation, meaning they just show a fraction of something, hence it is not a complete picture and there definitelty can be more languages

‘B’ Diversity is not based on only languages, as it has to take into account various factors like clothes,cuisines,climates,mountains, people, etc, so though language is a part of the diversity it cannot be the only indicator.

‘C’ The currency notes come in various sizes and denominations, here it is not specified and so it is ambiguous as to which currency note is referred to here, also no currency note can have ‘sufficient space’ on it to fit in the 22 official or the1652 in totality that are spoken here.

‘D’ Linguistic pluralism is strong evidence of India’s diversity is definitely correct as a country which speaks in so many languages is a country which has a diverse set of people, traditions, cultures etc. hence this can clearly be ‘one’ of the indications of the nation’s diversity.

Using the ‘>’ to imply the winner in encounters between the two, we can conclude the following from the given statements:

I. P > Q

II. R > S

III. S > P (only sometimes = more likely to win).

IV. Q > R

Based on this, we can analyse the given statements:

i) P is likely to defeat the other players is not true, as P tends to lose to S, and we cannot determine the performance against R.

ii) S is the worst player amongst the lot is always untrue as S tends to defeat P in most encounters.

Hence neither statement (i) nor (ii) can be logically inferred from the given statement.

Given, f(x) = 2x⁷ + 3x – 5

We have to check each option and find the factor.

A) x³ + 8 = (x + 2)(x² – 2x + 4)

∴ For x³ + 8 to be a factor, (x + 2) should be a factor too.

Thus, for x = -2, f(x) = 0

⇒ 2 × -2⁷ + 3 × -2 – 5 ≠ 0

Thus x³ + 8 is not a factor.

B) x – 1

∴ For (x – 1) to be a factor, f(1) = 0

= 2 × 1⁷ + 3 × 1 – 5

= 0

Thus (x – 1) is a factor

C) 2x - 5

For (2x – 5) to be a factor, f(5/2) = 0

= 2 × (5/2)⁷ + 3 × (5/2) – 5

≠ 0

Thus (2x – 5) is not a factor.

D) x + 1

For (x + 1) to be a factor, f(-1) = 0

= 2 × (-1)⁷ + 3 × -1 – 5

= -10

Thus, (x + 1) is not a factor.

∴ (x – 1) is a factor of f(x) = 2x⁷ + 3x – 5

Given, in a process, the number of cycles to failure decreases exponentially with an increase in load.

Let the relation be : c = a × b^l,

Where, c is number of cycles and l is load units while a and b are constants.

Given, at a load of 80 units, it takes 100 cycles for failure. When the load is halved, it takes 10000 cycles for failure.

∴ 100 = a × b⁸⁰ --------- (1) and 10000 = a × b⁴⁰ -------- (2)

Dividing (1) by (2)

⇒ 1/100 = b⁴⁰

Taking log both sides

∴ log(1/100) = 40 logb

\(\Rightarrow \frac{1}{{40}}\log \left( {\frac{1}{{100}}} \right) = \log b;\) 

Substituting value of b⁴⁰ in eq2,

⇒ 10000 = a × 1/100

⇒ a = 10⁶

Given, failure happened in 5000 cycles.

∴ 5000 = 10⁶ × b^l

⇒ 5 × 10^-3 = b^l

Taking log both sides.

log(5 × 10^-3) = l × logb

\(\Rightarrow \frac{{\log \left( {5 \times {{10}^{ - 3}}} \right)}}{{\frac{1}{{40}}\log \left( {\frac{1}{{100}}} \right)}} = l\) 

⇒ l = 46.021

Data:

p: x ∈ {8, 9, 10, 11, 12}

q: x is a composite number

r: x is a perfect square

s: x is a prime number   

Explanation:

p ⇒ q means p̅ + q

As, q is composite number So, p ⇒ results in {8, 9, 10, 12}

As, r: x is a perfect square, ¬ r results in all the numbers which are not perfect square

So, ¬ r: {8, 10, 11, 12}

¬ s: {8, 9, 10, 12}

¬ r ∨ ¬ s = {8, 9, 10, 11, 12}

Now, (p ⇒ q) ∧ (¬ r ∨ ¬ s) = {8, 9, 10, 12}

¬ ((p ⇒ q) ∧ (¬ r ∨ ¬ s)) results in a number which is not present in ((p ⇒ q) ∧ (¬ r ∨ ¬ s))

¬ ((p ⇒ q) ∧ (¬ r ∨ ¬s)) will give {11}.

We have to take n-bit strings that do not contain two consecutive 1’s

For n = 1, i.e. 1 bit string , number of strings with 1 bit = { 0, 1 } = 2

For n = 2 i.e. 2 bit string, number of strings with 2 bit = {00, 01, 10} = 3

For n = 3, i.e. 3 bit string, number of strings with 3 bit = {000, 001, 010, 100, 101} = 5

For n = 4 i.e. 4 bit string, number of strings with 4 bit = {0000, 0001, 0010, 0100, 1000, 0101, 1010, 1001} = 8

Here, these values are making a Fibonacci series. Because we are getting the next value by adding the previous two values like in Fibonacci sequence (0, 1, 1, 2, 3, 5, 8 ……..)

Recurrence relation for Fibonacci sequence is : T(n) = T (n -1 ) + T(n - 2)

So, here recurrence relation for a_n = a_n-1 + a_n-2

Concepts:

L’Hospital rule:  

Evaluate the limit of numerator and denominator. If \(\frac{0}{0}\) form, then it is indeterminate form. L’ Hospital rule states that the limit of a quotient of functions is equal to the limit of the quotient of their derivatives.

Calculation:

\(\mathop {\lim }\limits_{x \to 4} \frac{{\sin \left( {x - 4} \right)}}{{x - 4}} = ;\frac{{\sin \left( {4 - 4} \right)}}{{4 - 4}} = ;\frac{{\sin 0;}}{0} = \frac{0}{0}\)

As, it is  form, take the derivative of numerator and denominator both.

\(\mathop {\lim }\limits_{x \to 4} \frac{{\frac{d}{{dx}}\left[ {{\rm{sin}}\left( {x - 4} \right)} \right]}}{{\frac{d}{{dx}}\left( {x - 4} \right)}} = ;\mathop {\lim }\limits_{x \to 4} \frac{{{\rm{cos}}\left( {x - 4} \right)}}{1} = ;\frac{{{\rm{cos}}\left( {4 - 4} \right)}}{1} = \frac{{\cos 0;}}{1} = 1\)

Concept:

A probability density function is a function of continuous random variable, whose integral across

an interval gives the probability that the value of the variable lies within the same interval.

Calculation:

Integral value must be equal to 1.

\(\mathop \smallint \nolimits_a^1 \frac{1}{{{x^2}}} = \left[ {\frac{{ - 1}}{x}} \right]_a^1 = ;\left[ { - 1 + ;\frac{1}{a}} \right]\)

Equate this to 1.

\(- 1 + \frac{1}{a} = 1\)

\(a = 0.5\)

Concept:

Eigenvalues are the roots of the characteristic equation and determinant of a matrix is the product of its eigenvalues.

Calculation:

We have to consider a 3 × 3 matrix, so roots will be 3 means 3 eigenvalues. Two eigenvalues are given as : (2 + √-1) and 3.

As 3 × 3 is a real matrix, in real matrix roots can never be imaginary. We have to take the complex roots in pair. So,

Three eigenvalues are:

2 + i , 2 – i, and 3

Determinant of the matrix P = product of its eigenvalues

= (2 + i) × (2 - i) × 3

= (4 – i²) × 3 = (4 – (–1)) × 3

= 5 × 3 = 15

Find out the value of # function with the help of truth table;

Given:

x # 0 = x,

x # 1 = x̅,

x # x = 0 and

x # x̅ = 1

 

So, according to this # function results in XOR operation on x and y.

x # y equivalent to x.y̅ + x̅.y

Alternate method:

Rules of XOR function are:

1)  XOR of a with 0 = a

2. XOR of a with 1 = a’

3. XOR of a with a = 0

4. XOR of a with a’ = 1

So, here also given properties follow the rules of XOR operation so, this # function here represents the XOR function.

x # y is equivalent to xy̅ + x̅ y.

16- bit 2’s complement representation of an integer is:

an interval gives the probability that the value of the variable lies within the same interval. To convert this into decimal form:

1)  First take the 1’s complement of it:

1111 1111 1111 0101 => 0000 0000 0000 1010

2. Now add 1 to it:

0000 0000 0000 1010 + 1 = 0000 0000 0000 1011

3. Now, all 0’s in left side have no meaning in decimal form. Just take the number 1011

4. As, 1011 decimal representation is 11. But here sign bit is 1, means it is a negative number.

5. if MSB = 0, number is positive and if MSB = 1 , number is negative.

6. So, result is – 11.

Alternate Method:

1111 1111 1111 0101 ≡ 10101

10101 = 1 × 2^-4 + 0 × 2³ + 1 × 2² + 0 × 2¹ + 1 × 2⁰ = -16 + 4 + 1 = -11

Given counter sequence is: 0 – 1 – 0 – 2 – 0 -3

There are three transition from 0 to 1, 2 and 3.

To differentiate with these transitions, we require 2 bits.

Sequence will be like 00 – 01 – 00 -10 – 00 – 11

Now again we need 2 more bits to differentiate between these 3 0’s.

0000 – 0001 – 0100 – 0010 – 1000 – 0011

Total 4 bits are needed; 4 minimum flip flops are needed to implement this counter.

Maximum memory size = 4 GB = 2³² bytes

Word size = 2 byte

Total number of words = \(\frac{{memory;size}}{{word;size}} = ;\frac{{{2^{32}}}}{2} = {2^{31}}\)

To, address these words, minimum size of the address bus we needed = 2³¹

Minimum size of address bus in bits = \(\left\lceil {{{\log }_2}{2^{31}}} \right\rceil \) = 31 bits

NOTE:

1 G → 2³⁰

When we consider a normal implementation of the queue using an array, in that case for enqueue and dequeue operation, we have to shift every other element.  In this, every time we remove the item from the start of the queue, all of the rest of the items in the queue move down by one to fill the space made by the removal of other items.

But if we consider the circular array implementation of a queue, in this case, both enqueue and dequeue can be performed in O(1) time.

Diagram

STEPS:

1. Take the vertex with the in-degree 0. i.e. a

2. Print this vertex and remove a. Then consider the edges coming out of it.

3. similarly, repeat these steps till all the vertices are printed.

Here, vertex a has in-degree 0 .

Output: a _ _ _ _ _

Next we have to take either b or d.

Output : a b _ _ _ _ and a d _ _ _ _

Here, we get 4 orderings as a b d _ _ _ or a d b _ _ _

So, in this way,

Topological ordering of the vertices :

a – b – c –d – e – f

a – b – d –c – e – f

a – b – d –e – c – f

a – d – e –b – c – f

a – d – b –c – e – f

a – d – b –e – c – f

Tips and Tricks:

Initial and final node is fixed

There are 4 nodes: total arrangement is 4!

But sequence of b – c   and d – e cannot be altered

different topological order: \(\frac{{4!}}{{2! \times 2!}} = 6\)

Consider all the options one by one.

1. f(s,*s)

In this function call, second argument is a pointer variable but, in the question, 2^nd argument is given as short not a pointer variable. So, it is incorrect.

2. i = f(i, s)

Here in this value of this function f(i, s) will  store into variable i. But in case of actual function there is no return type. So, it is incorrect.

3. f(i,*s)

Same as in 1^st option. So, it is incorrect.

4. f(i,*p)

Here, both the arguments and return type matches. As p is a pointer to short and *p is value of short. So, it is correct.

Insertion sort:

In Insertion sort, the worst-case takes Θ (n²) time, the worst case of insertion sort is when elements are sorted in reverse order. In that case the number of comparisons will be like:

\(\mathop \sum \limits_{{\rm{p}} = 1}^{{\rm{N}} - 1} {\rm{p}} = 1 + 2 + 3 + \ldots . + {\rm{N}} - 1 = {\rm{;}}\frac{{{\rm{N}}\left( {{\rm{N}} - 1} \right)}}{2} - 1\)

This will give Θ (n²) time complexity.

Merge sort:

In Merge sort, the worst-case takes Θ (n log n) time. Merge sort is based on the divide and conquer approach. Recurrence relation for merge sort will become:

T(n) = 2T (n/2) + Θ (n)

T(n) = n + Θ (n)

T (n) = n × logn

Quicksort:

In Quicksort, the worst-case takes Θ (n²) time. The worst case of quicksort is when the first or the last element is chosen as the pivot element.

Diagram

\(\mathop \sum \limits_{{\rm{p}} = 1}^{{\rm{N}} - 1} {\rm{p}} = 1 + 2 + 3 + \ldots . + {\rm{N}} - 1 = {\rm{;}}\frac{{{\rm{N}}\left( {{\rm{N}} - 1} \right)}}{2} - 1\)

This will give Θ (n²) time complexity.

Recurrence relation for quick sort algorithm will be,

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

This will give the worst-case time complexity as Θ (n²).

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.

Example:

Graph G(V, E)

Shortest path between A and C = A → B and B → C, that is,1 + 2 = 3

G(V, V – 1) → minimum spanning tree

Increase the weight of G(V, E) by 10

Graph G'(V, E)

Shortest path between A and C = A → C = 20 (different path)

G'(V, V – 1) → minimum spanning tree

 

Statement P: TRUE

Minimum spanning the tree of G does not change

Statement Q: False

Shortest path between any pair of vertices may change

In the given program, in mystery function only addresses are swapped not the values. Values remain same as in the main function. Pointer swapping is local to the mystery function here.

In C language, parameters are passed by value even if they are pointer. So, there will be no change in the value of a, b, c and d.

Code Explanation:

int main () {

                int a = 2016, b = 0, c = 4, d = 42;                      // a= 2016, b= 0

                mystery (&a, &b);                                              // call void mysery (int *ptra, int *ptrb)

                if (a < c)

                mystery (&c, &a);

                mystery (&a, &d);

                printf (‘’%d\n’’, a);

}

void mysery (int *ptra, int *ptrb)                               // ptra = 2016, ptrb =0 during first call

{

                int *temp;

                temp = ptrb;

                ptrb = ptra;

                ptra = temp;                                                   // ptra = 0, ptrb = 2016,

}

But after this mystery(&a, &b); popped out of stack and all the pointers lost and all values wil remain same as original.

printf (‘’%d\n’’, a);                 // it will print the value of a i.e. 2016.

S → aS | bS | ϵ 

This grammar results in (a + b)*

DFA for this grammar is:

Diagram

Now, consider the options one by one:

Option 1:

{aⁿb^m | n, m ≥ 0}

Here order is fixed, means first any number of a will come then any number of b. It is incorrect.

Option 2: 

{w ϵ {a, b} * | w has an equal number of a’s and b’s}

As given grammar is not generating the expression which generates only equal number of a and b. So,

not correct.

Option 3:

{aⁿ | n ≥ 0} {bⁿ | n ≥ 0} {aⁿbⁿ | n ≥ 0}

Here, also order is fixed. So, it is incorrect.

Option 4:

{a, b}*

This is equivalent to (a + b)*. So, it is correct.

I. Given NFAs N1 and N2, is L(N1) ∩ L(N2) = ϕ?

This is decidable, when we convert the NFA into DFA, if no common final state in it. Then this will become true.

II. Given a CFG G = (N, ∑, P, S) and a string x ∈ ∑*, does x ∈ L(G)?

Membership property of a context free grammar is decidable.

III. Given CFGs G1 and G2, is L(G1) = L(G2)?

Equivalence of two context free grammar is undecidable.

IV. Given a TM M, is L(M) = ϕ?   

Emptiness problem of Turing machine is undecidable.

Consider all the options one by one:

1. (0 + 1) 0011 (0 + 1) + (0 + 1) 1100 (0 + 1)

It consider only those string which have either 0011 or 1100 as a substring. So, it is wrong.

2. (0 + 1) *(00(0 + 1)*11 + 11 (0 + 1)00) (0 + 1)

It contains set of all the binary strings that contain two consecutive 0’s and 1’s.

3. (0 + 1) 00 (0 + 1) + (0 + 1) 11 (0 + 1)

This set contains only those string which have either 00 or 11 as substring but not does not contain all the strings that contain two consecutive 0’s and 1’s.

4. 00 (0 + 1) *11 + 11 (0 + 1) *00

It represents those strings which start with 00 or 11 and end with 11 or 00 respectively. So, it is wrong.

Concept:

Rules in static single assignment form:

Each variable must be assigned exactly once.

Every variable must be defined before it is used.

All of the uses reached by the assignment must be renamed.

Diagram: DAG representation is

Explanation

x = u – t;

y = x * v;

x = y + w;

y = t – z;

y = x * y;

Static single assignment form is:

t1 = u – t

t2 = t1 * v

t3 = t2 + w

t4 = t – z

t5 = t3 * t4

So, total 10 variables are needed in static single assignment form which are (t1, t2, t3, t4, t5, u, t, v, w, z).

Concept:

Waiting time:

It is the total time spent by the process in the ready state waiting for CPU.

Shortest remaining time first:

This algorithm is the pre-emptive shortest job first algorithm and optimal. In this process having small running time remaining until completion are selected to execute first, this can also cause starvation. But in shortest remaining time first algorithm, turnaround time, waiting time is minimum and CPU utilization is high.

Example:

 

For shortest remaining time first,

Gantt chart:

0            1               2              3              5              9            15

Average waiting time in SRTF = 3.67 ms (Burst time are in ms)

For round robin scheduling with TQ = 1

Gantt chart:

0     1      2      3      4      5      6      7      8      9     10    11    12   15

Average waiting time in RR = 6.33 ms

For uniform random (say FCFS)

Gantt chart:

0               5               12             15

Average waiting using FCFS = 4.67 ms

Priority scheduling algorithm:

In this example, average waiting time for this = 4.67 ms

Therefore, Shortest remaining time first algorithm has minimum average waiting time.

Concept:

Superkey is a set of attributes within a table whose values can be used to uniquely identify a tuple. A candidate key is a minimal superkey.

Superkey is superset of candidate key or primary key.

Explanation:

Primary key is VY. (given)

All superkeys must contain this primary key VY. From the given keys, key, which doesn’t contain

the VY.

Here, option 2: VWXZ

“VWXZ” doesn’t contain the primary key VY. So, it is not a superkey.

ACID properties of database transaction:

Atomicity: The entire transaction takes place at once or doesn’t happen at all.

Consistency: The database must be consistent before and after the transaction.

Isolation: Multiple transactions occur independently without interference.

Durability: The changes of a successful transaction occurs even if the system failure occurs.

So, deadlock freedom is not the ACID property of database transaction.

First relational schema:

(VOLUME, NUMBER, STARTPAGE, ENDPAGE, TITLE, YEAR, PRICE)

Primary key: (VOLUME, NUMBER, STARTPAGE, ENDPAGE)

Functional dependencies are:

(VOLUME, NUMBER, STARTPAGE, ENDPAGE) → TITLE   

(This dependency is in BCNF, satisfy form X → A, where X is the candidate key)

(VOLUME, NUMBER) → YEAR

(This dependency is not in 2NF, as there is partial dependency in this)

(VOLUME, NUMBER, STARTPAGE, ENDPAGE) → PRICE       (BCNF form).

First relational schema is in 1NF.

Second relational schema:

(VOLUME, NUMBER, STARTPAGE, ENDPAGE, TITLE, PRICE)      - 1^st

(VOLUME, NUMBER, YEAR)   - 2^nd

1^st satisfy

(VOLUME, NUMBER, STARTPAGE, ENDPAGE) → TITLE     //BCNF form

(VOLUME, NUMBER, STARTPAGE, ENDPAGE) → PRICE      // BCNF form

2^nd satisfy

(VOLUME, NUMBER) → YEAR               // According to this, satisfy 2 NF form.

Weakest normal form that new database satisfies but old one doesn’t is 2NF.

For, this we must know what each of these protocol does.

DNS:

DNS stands for domain name server. DNS converts domains to IP address. These are internet’s equivalent of a phone book.

ARP:

ARP stands for address resolution protocol.  This is a protocol uses to convert IP address into MAC address. This protocol operates below the network layer as part of interface between OSI network and link layer.

RARP:

RARP stands for reverse address resolution protocol. This is used to convert a particular MAC address into a corresponding IP address.

DHCP:

DHCP stands for dynamic host configuration protocol. It enables a server to automatically assign an IP address to a computer from a defined range of numbers. It is not used to resolve one address form to another.

Concept:

Stateless protocols: A stateless protocol does not require the server to retain session information or status about each communicating partner for the duration of multiple requests. Each request is treated as an independent transaction.

Stateful protocols: A protocol that requires keeping of the internal state on the server is known as stateful protocol.

Explanation:

HTTP: Hypertext transfer protocol is a stateless protocol. No information is maintained by server in this protocol.

FTP: File transfer protocol is a stateful protocol. It remembers all the log files corresponding to the client.

TCP: Transfer control protocol is not an application layer protocol. TCP works at transport layer.

POP3: It is a client/ server protocol in which e-mail is received and held by the internet server. It is a stateful application layer protocol.

Therefore, option 3 is correct

We have to find the coefficient of x¹² in (x³ + x⁴ + x⁵ + x⁶ + …)³

(x³ + x⁴ + x⁵ + x⁶ + …)³ = [ x³ (1 + x¹ + x² + x³ + x⁴ + x⁵ + …)]³

                                      = [ x⁹ (1 + x¹ + x² + x³ + x⁴ + x⁵ + …)³]

Now, in remaining term we need to find coefficient of x³. Because x¹² = x⁹ × x³.

Now, [ x⁹ (1 + x¹ + x² + x³ +…… )³] = \({x^9}{\left( {\frac{1}{{1 - x}}} \right)^3} = {x^9}{\left( {1 - x} \right)^{ - 3}}\)

Now, by using binomial coefficient here,

x⁹ (1 – x)^-3 = x⁹ (1 + 3x + 6x² + 10x³ + …) = x⁹ + 3x¹⁰ + 6x¹¹ + 10x¹² + …

Here, it is clearly shown that, coefficient of x¹² is 10.

Given a₁ = 8

a_n = 6n² + 2n + a_n-1

a_n = 6n² + 2n + 6 (n -1)² + 2 (n - 1) + a_n-2

a_n = 6n² + 2n + 6 (n -1)² + 2 (n - 1 ) + 6 (n - 2)² + 2(n - 2) + a_n-3

a_n = 6n² + 2n + 6 (n -1)² + 2 (n - 1) + 6 (n - 2)² + 2(n - 2) + … + a₁

a_n = 6n² + 2n + 6 (n -1)² + 2 (n - 1) + 6 (n - 2)² + 2(n - 2) + … + 6 (1)² + 2 × 1

a_n = 6 (n² + (n - 1)² + (n - 2)² + … +2² + 1²) + 2 (n + (n – 1) + (n- 2) + ……………+2 + 1)

\({a_n} = 6 \times \frac{{n\left( {n + 1} \right)\left( {2n + 1} \right)}}{6} + 2;\frac{{n\left( {n + 1} \right)}}{2}\)        [By using sum of square and sum of n positive numbers]

a_n = n (n+1)(2n + 1) + n (n +1)

a_n = 2n (n +1)2

n = 99

a₉₉ = 2 × 99 (99 + 1)2 = 198 × (100)² = 198 × (10)⁴         ----(1)

Also, a₉₉ = K × 104          ----(2)

Equate (1) and (2)

198 × (10)⁴ = K × 10⁴

So, K = 198

Let f(1) = a

Given:

f(n) = f(n/2) if n is even

f(n) = f(n + 5) if n is odd

Now, f (2) = f (2/2) = f(1) = a   [Because 2 is even]

For n = 3; 3 is odd

f(3) = f (3 + 5) = f (8) = f(8/2) = f(4) = f(4/2) = f (2) = f(2/2) = f(1) = a

For n = 4; 4 is even

f(4) = f (4/2) = f(2) = f(2/2) = f(1) = a;

For n = 5, 5 is odd

f(5) = f(5 + 5) = f(10) = f(10/2) =f(5) = f(5 + 5) = f(10) = f(10/2) = f(5) = b    [As f(5) is repeating ,let f(5) = b]

for n= 6

f(6) = f(6/2) = f(3) = x

So, there are two values only a and b. All multiples of 5 are b and others have value a.

So, the maximum possible size of R is 2.

When a fair coin is flipped twice then the possible outcomes are: {HH, HT, TH, TT}

If (TH) comes then output Y, i.e. Y = ¼

If (HH, HT) comes then output is N; N = 2/4 = ½

If (TT) comes, then again flip the coin again.

Possible outcomes are {TTTT, TTTH, TTHT, THTT, HTTT, TTHH, HTTH, THTH, HTHT, HHTT, THHT, HTTH, THHH, HTHH, HHTH, HHHT, HHHH}

In this case Y = 1/16

We have to find the probability that output of the experiment is Y = \(\frac{1}{4} + \frac{1}{{16}} + ;\frac{1}{{64}} + \ldots .;\)

It forms a GP series:

Where, a = ¼, r = ¼

So, required probability = \(\frac{{\frac{1}{4}}}{{1 - \frac{1}{4}}} = ;\frac{1}{3} = 0.33;\)

input given at 0 is R̅ in MUX 2

Concept:

For a 2: 1 multiplexer, if S is enabled and I₀, I₁ are the input, output = S̅ I₀ + SI₁

Explanation:

                          MUX 1                       MUX 2

Here, output of MUX 1 is input to MUX 2.

Here, output of MUX1 = P̅.0 + P.R = P R

Output of MUX 2 = X = Q̅.R̅  + Q.P.R

The minimal sum of products form of the output X is Q̅.R̅ + PQR

Concept:

A hardware device used for DMA (Direct memory access) is DMA controller. DMA controller is a control unit, which can transfer blocks of data between I/O devices and main memory with intervention from the processor.

Data count register provides the number of words DMA can transfer in one cycle.

If memory is byte addressable; 1 word = 1 byte

1 kilobytes = 2¹⁰ bytes

Calculation:

Size of data counter register of DMA controller = 16 bits

It means, 2¹⁶ words can be transferred in one cycle.

As, memory is byte addressable.

So, 2¹⁶ bytes in one cycle. (2¹⁶ bytes = 2⁶ kilobytes)

File size = 29154 kilobytes

Minimum number of times the DMA controller needs to get control of the system bus from the processor to transfer the file from the disk to main memory is = \(\left\lceil {\frac{{File;size}}{{bytes;in;one;cycle}}} \right\rceil = \left\lceil {\frac{{29154;KB}}{{{2^{16}}}}} \right\rceil = 456\)

Formula:

Throughput of the pipeline = \(\frac{{number;of;instructions;}}{{Total;time;to;complete;the;instructions}}\)

OR

Throughput = number of instructions executed per unit time = 1/T_p

Calculation:

CASE 1:

Initial stage delays:

800, 500, 400 and 300 picoseconds

Number of stages = 4

In case of pipeline, CPI = 1

Here, max stage delay = 800 picoseconds

As, we have to find the increase in throughput so just consider the stage delays, ignore other units.

So, throughput in initial case = \(\frac{1}{{800}}\)

CASE 2

Updated stage delay:

600, 350, 500, 400, 300 picoseconds

Max stage delay = 600 picoseconds

Throughput in this case = \(\frac{1}{{600}}\)

So, percentage increase in throughput = \(\frac{{\left( {\frac{1}{{600}} - \frac{1}{{800}}} \right)}}{{\frac{1}{{800}}}} = 33.33% \)

Concept:

A carry look- ahead adder reduces the propagation delay by introducing more complex hardware. In this, ripple carry design is suitably transformed such that the carry logic cover fixed groups of bits of the adder is reduced to two – level logic.

Explanation:

In case of look – ahead adder,

G_i = carry generator, P_i = carry propagator (P_i = A_i XOR B_i) and (G_i = A_iB_i)

C₁ = G₀ + P₀C₀

C₂ = G₁ + P₁G₀ + P₁P₀C₀

C₃ = G₂ + P₂G₁ + P₂ P₁G₀ + P₂ P₁ P₀C₀

From above Boolean equations, C₄ does not have to wait for C₃ and C₂ to propagate. It propagates at the same time. Boolean expression for each carry output is the sum of products so these are implemented with AND gates followed by an OR gate.

Here, for generation of n^th carry bit, we perform AND between (n+1) inputs.  If we have AND gates with a fan-in of k then we find the AND of all the bits in log_k(n + 1) time.

Here we have to find for fan-in with atmost 2 bits.

So, time to perform this addition =   Θ (log(n))

Consider size of array; n= 5

  p[0]          p[1]       p[2]        p[3]        p[4]

In this array, we have to find the maximum element.

CASE 1 :  while (a ! = n)

int max (int *p, int n)  {                  // p points to array and n= 5

                        int a = 0, b = n – 1;                       // a = 0 , b= 4

                        while( a ! = n ) {                          

          if(p[a] <= p[b])  { a = a+1;  }

          else                      { b = b-1;   } 

                        }

                       return p[a];

                } 

In this case, at the end value of  a becomes 5, p[5] doesn’t result in any value.

CASE 2: while (b ! = 0)

With this condition, it will not print the maximum value.

CASE 3: while (b > (a + 1 ))

This will give the required output which gives the maximum element of the array but this condition doesn’t hold true for n = 2.

CASE 4: while ( b ! = a )

It will give the maximum element of the array.

A static local variable is initialized only once no matter how many times the function in which it resides is called.

1. Here, count (3) calls the function

void count (int n) {

             static int d=1;             // d= 1(only once)

             printf("%d ", n);         // print 3

             printf("%d ", d);            // print 1

             d++;                                   // d = 2

             if(n>1)   count (n-1);                // (3 > 1) condition true, count (2), again call goes to function.

             printf("%d ", d);

}

2. Now, count (2) is called,

It will print value of n and d  i.e. 2 2 will be printed and d will become 3

3. Now, condition become true again (2 > 1). Count (1) will be called.

4. Count (1) will print the valued of n and d i.e. 1 3 will be printed and d will become  4.

5. Now if condition becomes false as 1 is not greater than 1 . So, it will print the value of d which is 4.

6. control will go back to count (2). It will also print final value of d i.e. 4. Count (2) execution finished.

And control will go to count (3).

7. count (3) finally prints the value of d i.e. 4.

8 ) So, final output is 3 1 2 2 1 3 4 4 4

The correct answer is option 3.

Concept:

Static Scope:

Referencing the environment of a statement in a static scope language is the collection of all local variables and all other ancestor variables that are visible in the statement.

Dynamic Scope:

Referencing the environment of a statement in a dynamical scope language is the collection of all local variables and all other active subprogram variables which are visible in the statement.

Explanation:

Step 1:

Here 'a' is a global variable it can be accessed throughout the program.

Step 2:

In m(y) here a is not a local variable so it updates the value in the global section. Then control moves to n(x) function.

Step 3:

In n(x), the local variable x is updated by x = x*a. So print x value as 4. Then n(x) function is removed from stack moves back to m(y) function call.

Step 4:

In m(y), The value 'a' prints by checking the local variable and other active sub-programs. Hence the main function has the variable 'a'. Hence it prints the 'a' as 2 as output.

Hence the correct answer is 4,2.

STEPS:

1)  delete (i) will delete the element at ith index in the binary heap in O (1) time.

2. But, we have to fill the empty position with the last node of the heap.

3. Last node of the heap can be easily found in O (1) time and replace empty position with this node.

4. After this, there is need to heapify the binary heap which will take  O (depth of heap tree).

5. Depth of heap tree is log n if n is number of elements in the heap.

6. But, in question it is given that depth is d. So, this delete (i) will take O (d) time not O(1)

Given weight matrix:

\(W = \left[ {\begin{array}{*{20}{c}} 0&2&8&5\ 2&0&5&8\ 8&5&0&x\ 5&8&x&0 \end{array}} \right]\)

Let graph vertices are 0, 1, 2, 3

Graph from this matrix:

To find the largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge with weight x.

So, find the shortest path between vertex 2 to 3 without including x.

Shortest path between vertex 2 to 3 (through 2 – 1 – 0 – 3) = 5 + 2 + 5 = 12

Largest possible integer value of x = 12

Concept:

Minimum spanning tree: Minimum spanning tree is a subset of the edges of a connected edge weighted undirected graph that connects all the vertices together, without any cycles and with minimum possible edge weight.

Explanation:

Graph has 4 vertices with weights 1, 2, 3, 4, 5, and 6.

Use the cut and cycle property of minimum spanning tree.

Here, for a spanning tree, 3 edges are must. Edge weights 1 and 2 must be included because 2 edges can’t form a cycle. So, according to Kruskal algorithm minimum 2 edge weights are in increasing order will be included.

Now, 4 edge weights are remaining (3, 4, 5, 6).

Assign edge weight 3 such as it forms a cycle so that it can’t be included for minimum spanning tree.

Now from remaining edge weights choose the minimum one.

Graph:

Minimum spanning tree:

So, maximum weight of minimum spanning tree = 7

I. If e is the lightest edge of some cycle in G, then every MST of G includes e          (INCORRECT)

Let G = (V, E) is a graph with 4 vertices and 5 edges. 

Here, cycle contains the edge weights (3, 4, 5) but edge weight 3 is not included in the MST.

So, according to the cut-property of MST if is the lightest edge of some cycle in G, then every MST of G may or may not include e.

II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e          (CORRECT)

According to the cycle property of MST, same example as above. Here, cycle contains the edge weights (1, 2, 3)  and 3 is the heaviest so edge weight 3 is excluded in the MST.

If there is heaviest edge in cycle, then we will exclude it from the MST because there are other low-cost edges are available to include in MST (because edge weights are distinct here).

Here, it is given that queue contains 16 numbers. Suppose 16, 15, 14, 13, 12, 11…….1 (in decreasing order)

Now first condition is if S is empty or Top(S) <= Head (Q) then x = dequeuer(Q); Push (S, x)

So, initially stack is empty, 16 will be pushed into the stack.

Top(S) = 16, Head(Q) = 15.

Now if S is empty or Top(S) <= Head (Q) // condition becomes false

16 will be popped out of the stack and enqueued into the queue because else part is executed here.

Now, Queue elements will be like this after 2 iterations and stack is empty.

 

Similarly, for remaining elements, 15, 14, 13, 12, …………2 will be pushed into stack and immediately popped out of stack. So, after 30 iterations stack is empty and queue will be like:

 

Now, 1 will be dequeued and pushed into stack. After this again Head(Q) = 16, top (S) = 1.

After this, 1 will never be popped out from stack because if condition will never become false. So, after 31 iterations queue will be like:

 

Stack contains 1.

By using same logic as above, after other 29 iterations queue will be like: 16, 15, 14, 13 ……..,4,3 and 2 in the stack top.

Iterations will go like: 31 + 29 + 27 + 25 + …………….1 (AP series)

Here a = 1, d = 2, n =16

The maximum possible number of iterations of the while loop in the algorithm is = \(\frac{n}{2}\left[ 2a+\left( n-1 \right)d \right]\)

\(=\frac{16}{2}\left[ 2\times 1+\left( 16-1 \right)2 \right]=256\)

Given grammar is :

G₁ : S → aS|B, B → b|bB

This grammar generates strings of type {b, ab, bb, aab, abb, bbb, aaab,……..}.

Here number of a’s can be 0 but number of b’s is always more than 0. From this option 1) and 2) are eliminated because these can’t generate number of a’s as 0.

Now, grammar G₂ is:

G₂ : S → aA|bB, A → aA|B|ϵ, B → bB|ϵ

This grammar generates string of type: {a, b, aa, ab, bb, aaa, aab, abb, bbb, ………..}.

This grammar doesn’t generate null string number of a’s and b’s are more than 0. So, only option 4) matches according to grammar G₁ and G₂.

G₁ generates language of type: {a^m bⁿ | m ≥ 0 and n > 0}

G₂ generates language of type: {a^m bⁿ | m > 0 or n > 0}

Concept:

Acceptance of given string by a push down automata in two ways either by

• Acceptance by final state: if machine at the end of the string enters to one of the final states then string is accepted.
• Acceptance by Empty state: if at the end of the string, stack is empty then string is accepted.

Explanation:

In this PDA, initial state is also the final state it means null string is accepted by the given push down automata (PDA). Consider the states as q₁, q₂ and q₃ where q₁ is the final state.

Transition of given PDA are:

1. (q₁, a, Z) => (q₁, XZ)

2. (q₁, a, X) => (q₁, XX)

3. (q₁, b, X) => (q₂, ϵ)

4. (q₂, b, X) => (q₂, ϵ)

5. (q₂, ϵ, Z) => (q₃, Z)

First two transition show that after giving input a at transition state remains same. With every input ‘a’ we push X into stack. It means aⁿ is always accepted for n>= 0. Transition 3 and 4 shows that for every b input a X is popped out of the stack until stack symbol is Z and string becomes empty. It means ‘b’ occurred same number of times as ‘a’. It represents language of the form {aⁿbⁿ for n>=0 }. It is a DCFL.

Concept:

Language A is reducible to language B (represented as A ≤ B) if there exists a function which will convert A to B.

Rule: If A ≤ B and B is recursive then; A is also recursive.

If A ≤ B and if A is not recursively enumerable, B is also not recursively enumerable.

Explanation;

Here X is a recursive language and X̅ is complement of X. As complement of a recursive language is also recursive, so, X̅ is also recursive.

But complement of recursive enumerable language is not recursive enumerable so, Y̅ is not recursive enumerable.

Now it is given that, Y̅ reduces to W and Z reduces to X̅.

According to the rule, X̅ is recursive. So, Z is also recursive.

But according to the property of recursive enumerable language W is not recursive enumerable language.

Given expression is:

2 – 5 + 1 – 7 * 3

= 2 – 6 – 7 * 3 [Highest priority is of +, associativity left to right]

= 2 – (–1) * 3 [2^nd highest priority is of ‘-’, associativity right to left]

= 2 + 1 * 3

= 3 * 3

= 9

We have to find the output for input aab using the bottom – up parser

Given:

S → aA {print 1}

S → a {print 2}

A → Sb {print 3}

Using the parse tree:

We stopped the parse tree at ‘aab’ because it matches with the required string. Print the output string from bottom to top i.e. 2 3 1

Formula:

Number of pages = \(\frac{logical~address~space}{page~size}\)

Page table size = number of pages × page table entry size

Calculation:

Given, Logical address space = 2⁴⁰ bytes

Page size = 16 kB = 2¹⁴ bytes

Number of pages = \(\frac{{{2}^{40}}}{{{2}^{14}}}={{2}^{26}}\)

Page table entry size = 48 bits

Page table size = 48 × 2²⁶ = \(\frac{48}{8}~\times {{2}^{26}}=384~MB\)

The total head movement incurred while servicing these requests:

= (87 – 63) + (92 - 87) + (121 - 92) + (191 - 121) + (191 – 10) + (11 – 10) + (38 - 11) + (47 - 38)

= 24 + 5 + 29 + 70 + 181 + 1 + 27 + 9

= 346 (in number of cylinders)

Concept:

Last-in-first-out page replacement policy: It replaces the newest page that arrives at last in the main memory.

Optimal Page replacement policy: It replaces the page whose next use will occur farthest in the future.

Explanation:

Access sequence is (a₁, a₂,…,a₂₀, a₁, a₂,…,a₂₀)

a₁ to a₁₀ will result in page faults. Total 10 page faults in this.

Then a₁₁ comes, it replaces a₁₀, a₁₂ replaces a₁₁, a₁₃ replaces a₁₂ and so on,….10 page faults from a₁₁ to a₂₀.

Now when a₁ to a₉ occurs again, it will result in 0 page fault because these are already present in the page frame. Again a₁₀ will replace a₂₀, a₁₁ replaces a₁₀ and so on. So, in this way total 11 page faults from a₁₀ to a₂₀­.

Total page faults = 10 + 10 + 11 = 31

Using optimal page replacement:

a₁ to a₁₀ will result in page faults. Total 10 page faults in this.

Then a₁₁ will replace a₁₀ because from a₁ to a₁₀, a₁₀ will be used later, a₁₂ replaces a₁₁ and so on. 10 page faults from a₁₁ to a₂₀.

Again a₁ to a₉, 0 page faults. a₁₀ will replace a₁, a₁₀ to a₁₉ will have 10 page faults.

Total page faults in this = 10 + 10 + 10 = 30

So, difference in number of page faults = 31 – 30 = 1

Given code is a N process synchronization solution (known as Lamport’s bakery algorithm)

; c[i]=0;

This helps in getting the token. Each process which wants to enter into critical section, gets a token number (as in a restaurant) and wait for his turn.

c[i]=1 //announce that process P_i is ready to take it’s token number

t[i] = pmax (t [0],…, t[n-1]) +1 //get token number

c[i]=0; // means process P_i has taken it’s token number

As more than one process can get same token value and then suppose P₂ wants to enter the critical section. So, this line will be executed

while (t[j] != 0 && t[j]<=t[i]) ;

Now, j!=i, P₂ scans for other processes and check if anyone of them have it’s token value less than or equal to it’s own token value. When P₂ finds true then it starts looping at the condition. Similar for other processes. So, when P_{1 ­}finds that all other processes have their token value as non zero and have value less than token of P₁. It also waits. It becomes the situation of deadlock.

When deadlock in the system, progress will not be satisfied here.

Also, when a process reaches critical section, all other processes which started before it must have its token value as 0. This means that no two processes can be in critical section at the same time.

A transaction is said to follow 2- phase locking protocol if locking and unlocking can be done in 2 phases:

1. Growing phase: New locks on data items may be acquired but none can be released.

2. Shrinking phase: Existing locks may be released but no new locks can be acquired.

Properties of conservative 2PL:

A 2PL schedule is serializable, strict recoverable, deadlock free, starvation free.

Here, locks are acquired in order O₁, O₂, O₃,……….O_k (increasing order). Locks are also not released until the transaction completes its operation. Here circular wait condition can never occur. Hence, there is no possibility of deadlock.

2PL is conflict serializable. So, it guarantees serializability. We can get a serializable schedule by ordering based on lock points.

Concept:

Digital signature is attached to an electronically transmitted document to verify its contents and the sender’s identity. It ensures the integrity, non-repudiation and authenticity of the message. Message digest is a hash value which is generated by applying a function on it.

In digital signature:

1. Private key of sender is used to encrypt the message

2. Public key of sender is used to decrypt the message.

Diagram:

Here, B sends the message m to A.

Private key is denoted by \(K_{x}^{-}\) and public keys by \(K_{x}^{+}\)

So, according to the definition of digital signature, \(\left{ m,~K_{B}^{-}\left( H\left( m \right) \right) \right}\) is the correct way to send the message m along with the digital signature to A.

IP datagram size = 1000 bytes

IP header size = 20 bytes

MTU (maximum transmission unit) = 100 bytes

Size of data transmitted in one fragment = MTU – IP header = 100 – 20 = 80 bytes

Size of data transmitted = IP datagram – IP header = 1000 – 20 = 980 bytes

Number of fragments = \(ceil\left( \frac{980}{80} \right)=13\)

Concept:

Token bucket algorithm is based on the analogy of a fixed capacity bucket into which tokens represent a unique of bytes. Tokens used to synchronize incoming and outgoing data.

Formula:

\(\text{S}=\frac{\text{C}}{\text{M}-\text{P}}\)

where M = maximum output rate

P = token arrival rate

C = capacity of a bucket

Calculation:

Capacity = 1 megabyte

Maximum output rate = 20 megabytes per second

Token arrival rate = 10 megabyte

S = \(\frac{1}{20-10}=0.1~sec\)

10 MB → 1 second 

12 - 10 = 2 MB

Output rate = 20 MB

20 MB × 0.1 = 2 MB

To send 12 MB of data, time required = 1 + 0.1 = 1.1

Formula:

Throughput = \(\left( \frac{\frac{L}{B}}{Total~time} \right)\times B\)

Where: L = frame size

B = bandwidth

Total time = transmission time + 2 × propagation time + acknowledgement time

Calculation:

Given L = 1000 bytes

B = 80 kbps

Acknowledgment size = 100 bytes

Propagation time = 100 milliseconds

Transmission time = \(\left( \frac{1000\times 8}{80\times 100} \right)=0.1~sec\)

Acknowledgement time = \(\left( \frac{100\times 8}{8\times 1000} \right)=0.1~sec\)

Total time = 0.1 + 2 × 0.1 + 0.1 = 0.4 sec

Throughput = \(\frac{1000}{0.4}=2500~bytes/sec\)