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

Concept: Based on the concept of clauses.

A clause is a combination of related words containing a subject and a verb. It can be a simple sentence or a part of a compound sentence.

Main clause: It gives a complete meaning and can stand alone as a complete sentence

Subordinate clause: It depends on the main clause to give a complete meaning.

Explanation

Rules of clauses:

According to the rule, when main clause is in the past or past perfect tense, the subordinate clause must also be in the past or past perfect tense.

So, here past form of verb will be used. Given sentence will become:

“After Rajendra Chola returned from his voyage to Indonesia, he wished to visit the temple in

Thanjavur.”

Beside and besides both have different meaning.

CASE 1:

When s is added after beside i.e. besides, it can be used as a preposition or can be used as an adverb. While using as a preposition, its meaning is “in addition to” or “apart from” and while using as an adverb its meaning is “furthermore; as well as; also”.

CASE 2:

When beside is used without s at the end, it behaves only like a preposition which means “next to “, “at the side of”.

Here, correct answer is ‘besides money’, used as a preposition.

Correct sentence will be:

Research in the workplace reveals that people work for many reasons besides money.

The correct answer is option 3

EXPLANATION

While facing towards the center of the square,

Left – clockwise direction

Right – anticlockwise direction

So, Srinivas and Murali are seating opposite to each other.

Given y × 162,

Take the factors of 162:

Factors of 162 = 2 × 3 × 3 × 3 × 3  

So to make it a perfect cube, there is need of two 2’s and two 3’s .

So y = 2 × 2 × 3 × 3 = 36

Minimum value of y to make y × 162 a perfect cube is 36.

Consider k = 1, means 1-digit number doesn’t contain the digits 0, 5, or 9.

Remaining digits are 1, 2, 3, 4, 6, 7 ,8.

Total outcomes = 10

Favourable outcomes = 7

Probability = $\frac{7}{{10}}$ = 0.7

Consider k = 2, means 2-digit number doesn’t contain the digits 0, 5, or 9

So, both the places can be filled by the remaining 7 digits.

Total outcomes = 10 × 10

Favourable outcomes = 7 × 7

Probability = $\frac{7}{{10}}$ × $\frac{7}{{10}}$ = ${0.7^2}$

Similarly it goes for k = 3, probability = ${0.7^3}$

It goes up to k….

The probability that a k-digit number does NOT contain the digits 0, 5, or 9 = ${0.7^k}$

The author is saying that the hold of the nationalist imagination is on our country's colonial history, but it is not always necessary that anything that is not completely nationalist is not history. History and nationalism can be seen together but not always. Sometimes, history is viewed through the imagination of nationalism.

So, the correct answer is, "History is viewed through the filter of nationalism."

There are atleast two men and two women and atleast three right-handed person.

No women is right handed. It means, all three right-handed person are men.

So, women can’t be more than 3.

Now it is given that every woman has a left-handed person to her right. Here two cases:

CASE 1:

Diagram

If 3 women are considered on table, then there will be atleast one women who has a right-handed person on her right. So, it violates the given condition.

CASE 2:

Diagram

So, only 2 women are there on the circular table.

Equation: $\frac{{\left( {x + y} \right) - \left| {x - y} \right|}}{2}$

CASE 1

When x > y

$\left| {x - y} \right|$ = x – y,

$\frac{{\left( {x + y} \right) - \left| {x - y} \right|}}{2} = \frac{{\left( {x + y} \right) - x + y}}{2} = \frac{{2y}}{2} = y$

It means minimum of x and y.

CASE 2

When x < y

$\left| {x - y} \right|$ = y - x,

$\frac{{\left( {x + y} \right) - \left| {x - y} \right|}}{2} = \frac{{\left( {x + y} \right) - y + x}}{2} = \frac{{2x}}{2} = x$

Results in minimum of x and y.

So, in both the cases result is minimum of x and y.

Total number of shirts = 4

Total number of persons = 4

Arun dislikes red colour and Shweta dislike white colour.

No. of ways in which Arun chooses the shirt = $^3{P_1}$ = 3

No. of ways in which Shweta chooses shirt = 3

As, Gulab and Neel can choose from all colour’s shirts.

So, no. of ways in which Gulab chooses a shirt = 4

no. of ways in which Neel chooses a shirt = 4

Total possible ways = 3 + 3 + 4 + 4 = 14

Explanation:

Heights of all the villages according to the given data is :

As contour lines are shown at 25 m intervals.

Height of P = more than 550

Height of Q = between 525 and 550

Height of R = between 450 and 500

Height of S = between 425 and 450

Height of T = between 500 and 525

The water level is 525 m. All the villages below this water level height get submerged.

So, the answer is R, S, and T.

Formula:

p ⇒ q ≡ ¬ p ∨ q

Derivation:

(¬ p) ⇒ (¬ q)

≡ ¬ (¬ p) ∨ (¬ q)

≡ p ∨ (¬ q)

Statement I,

p ⇒ q

≡ (¬ p) ∨ q,

Statement II,

q ⇒ p

≡ (¬ q) ∨ p

≡ p ∨ (¬ q)

Statement III,

(¬q) ∨ p

≡ p ∨ (¬ q)

Statement IV,

(¬p) ∨ q

Only II and III option matches with the given implication.

Alternate Method:

By using Truth table:

So, only II and III matches with the given implication.

Concept:

One of the methods for this question is by considering x and y as the domains by using some statements.

Let us suppose x is for a girl and y is for a boy.

Given F is ∀x(∃ y R(x, y)) , in case of English language this means,

F: All girls like some boys

Now, check all the option one by one.

1. ∃y (∃x R(x, y)) means some boys are liked by some girls.

From this statement it is clear that it is the subset of given statement. TRUE

1. ∃y (∀x R(x, y)) means some boys are liked by all the girls. FALSE
2. ∀y (∃x R(x, y)) means all boys are liked by some girls which is opposite of given statement. So, this is FALSE.
3. ¬ ∃x (∀y ¬ R(x, y)) means for all girls like some boys. So, this is equivalent to given statement. TRUE

Alternate:

¬ ∃x (∀y ¬ R(x, y)) ≡ ∀x(¬ ∀y( ¬ R(x, y))) ≡ ∀x(∃x R(x, y))

∀x (∃ y R(x, y)) → ∃ x (∃ y R(x, y))

Explanation:

c₁, c₂, … c_n are scalars i.e. not all zero. \(\mathop \sum \limits_{i = 1}^n {c_i}{a_i} = 0\). Here c_i is scalar and a_i vector.

And when a scalar multiplied with vector, result will be zero, scalar value will be zero.

c₁a₁ + c₂ a₂ + … + c_n a_n = 0 So, here c_i value will be 0.

Here we can say that A is linearly dependent, and determinant of A is 0. (Linearly Dependent: Vectors being linearly independent means they represent independent directions in your vector spaces, while linearly dependent vectors mean they don’t. So, for example if you have a set of vectors {v1, v2, v3, v4, v5} and you can walk some distance in the v1 direction, then a difference distance in v2 and then in direction v3. If in the end, you are back at the point where you started then the vectors are linearly dependent otherwise not). A= [a1, a2, a3, … an]

b = \(\mathop \sum \limits_{i = 1}^n {a_i}\)

Ax = b

a₁x₁ + a₂ x₂ + … + a_n x_n = a₁ + a₂ + … + a_n

x₁ = x₂ = x₃ = … = x_n = 1 (It is one of the infinite solutions) and all other solution are on that same line.

So, the answer will be infinitely many solutions.

Given values are: 10 (a constant value)

√n (square root of a variable n which can take any value) n (a variable) log₂n (logarithmic)

$\frac{100}{n}$ (it divides 100 by a variable)

As we know that constant is smaller than a variable in case of asymptotic complexity because a variable can take any value smaller or larger. But when we compare 10 with $\frac{100}{n}$, as 100 is divisible by n and if n goes to infinite than this value will become zero. So, $\frac{100}{n}$ is smaller than 10.

In the case of log₂n growth rate is logarithmic which is smaller than linear growth.

Comparison between √n and n. Linear growth in case of n, it is larger than √n.

So, complete order is: $\frac{100}{n}$ < 10 < log₂ n < √n < n                                                                                        

Alternated method:

Take n = 2¹⁰²⁴

10, $2^{\frac{1024}{2}}$, $\frac{100}{2^{1024}}$, log₂(2¹⁰²⁴), 2¹⁰²⁴

10, 2⁵¹², $\frac{100}{2^{1024}}$, 1024 × log₂2, 2¹⁰²⁴

10, 2⁵¹², $\frac{100}{2^{1024}}$, 1024, 2¹⁰²⁴

In terms of increasing order:

100/(2¹⁰²⁴) < 10 < 1024 < 2⁵¹²< 2¹⁰²⁴

that is, $\frac{100}{n}$< 10 < log₂ n < $\sqrt n$ < n

• Quick Sort algorithm is based on divide and conquer approach in which a pivot is element is selected and array is partitioned based on that pivot element.
• Kruskal algorithm is a minimum spanning tree algorithm in which in every iteration, minimum weighted edge is found and then it is added to the construction of minimum spanning tree. Edges are added in increasing order of the edge weights. That’s why it is a greedy approach.
• Floyd Warshall algorithm is based on the principle of dynamic programming. It is used to solve the all pair shortest path problem.

Concepts:

Minimum height of the tree is when all the levels of BST are completely filled.

Maximum height of the binary search tree (BST) is the worst case when nodes are in skewed manner.

Formula:

Minimum height of the BST with n nodes is ⌈log₂ (n + 1)⌉ - 1

Maximum height of the BST with n nodes is n - 1.

Calculation:

Maximum height of the BST with 15 nodes 15 - 1 = 14

Diagram:

Minimum height of the BST with n nodes is ⌈log₂ (15 + 1)⌉ - 1 = 3

Diagram: 

Diagram:

i represents an integral part of the and f represents the fractional part of the number.

Since, the n number is in unsigned representation, it's decimal value starts with 0. So Minimum value will be zero.

Range of unsigned representation is 0 to 2ⁱ - 1.

So, the mum value with i bits goes to 2ⁱ - 1.

Fraction of value is in the form of 2^(-i). So, when we take the value of i = 1, 2, 3 … n this range of fractional value goes like, 2^-1, 2^-2, 2^-3, …

So, it makes a GP series, with f bit maximum number possible is sum of GP series.

Consider a = ½, r = ½

Maximum value with f bits possible

= $\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{{16}} + \frac{1}{{32}} + \ldots$

= $a \times \frac{{1 - {r^n}}}{{1 - r}}$

$= \frac{1}{2};\frac{{1 - {{\left( {\frac{1}{2}} \right)}^f}}}{{1 - \frac{1}{2};}} = 1 - {2^{ - f}};$

So, maximum fractional value possible

= maximum value with i bits + maximum value with f bits

= 2ⁱ - 1 + 1 - 2^-f

= 2ⁱ - 2^-f

So, require range will be 0 to 2ⁱ - 2^-f.

It is not mentioned in the question that both the lists m and n are empty or not. So, consider two cases.

CASE 1:

When lists are not empty, so according to the code given, join will append list m to end of the list n.

Diagram

CASE 2:

When lists are empty but valid like this,

node *head;

head - > NULL;

p = head

p- > next! = NULL. So, it will create a NULL reference issue.

So, answer will be either cause a null pointer dereference or append list m to the list n.

Overflow is a condition that indicates that the result is too large or too small to fit in the original data type.

Here given 2’s complement representation means signed bit representation.

Two key points that must remember in a signed operation:

1. MSB is used to indicate the sign of the number.
2. For negative numbers, 2’s complement representation is used.

2’s complement overflow rules:

• If the sum of two positive numbers gives a negative output, then the sum is overflowed.
• If the sum of two negative numbers gives a positive output, then the sum is overflowed.
• In other cases, the sum is not overflowed.

Overflow for the signed numbers occurs when the carry-in into the MSB (most significant bit) is not equal to carry out. Now according to the rules,

If both A₇ and B₇ are 1 then S₇ must be 0. For this C₇ will be 1 and C₆ will be 0. Hence, it will give

C₇.C₆’

If both A₇ and B₇ are 0 then S₇ must be 1. For this C₇ will be 0 and C₆ will be 1. Hence, it will give

C₇’.C₆

When we combine these two, we get C₇.C₆’ + C₇’.C₆ (means C₇ XOR C₆) which is a condition to detect overflow. So, Option C is the answer.

Overflow is said to have occurred if:

(A7.B7.S̅7 + A̅ 7.B̅ 7.S7) is 1

String Derivation:

S → abScT

→ ababScTcT (∵ S → abScT)

→ abababcTcTcT (∵ S → abcT)

→ abababcbTcTcT (∵ T → bT)

→ abababcbbTcTcT (∵ T → bT)

→ abababcbbbTcTcT (∵ T → bT)

→ abababcbbbbcTcT (∵ T → b)

→ abababcbbbbcbcT (∵ T → b)

→ abababcbbbbcbcbT (∵ T → bT)

→ abababcbbbbcbcbb (∵ T → b)

abababcbbbbcbcbb = (ab)³cb⁴cbcb²

From this string, it is clear that all the option 1),3) and 4) are not generated by given grammar.

Only option 2 matches.

Concept:

The field student. Grade can be accessed efficiently using the base address of the student which is available in register R1.

Explanation:

Now, consider all the options one by one.

• Post – increment addressing mode, (R1) +: In this, after accessing the operand, the content of the register are automatically incremented to point to next memory location, not to the desired student.grade memory location.
• Pre – increment addressing mode, - (R1) : In this, before accessing the operand, the contents of the register are decremented to point to the previous consecutive memory location, not to the desired memory location.
• Register direct addressing mode. R1: In this, location of the operand is a data register or an address register, memory location is itself embedded in the instruction code.
• Index addressing mode: In index mode, the addition of base address and displacement index value gives the actual memory location. So, by adding constant (offset) value to the base address, we can easily access the student.grade.

Index addressing mode

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.

Explanation

Now consider, all the option one by one

Option 1:

It violated the rule 1 of static single assignment form. Because in this, p₁ is assigned (initialized) two times: one in p₁ = a – b and another in p₁ = u * v

Option 3:

It violates the rule 2. Because in this case p₂, p₄ and q₃ are not assigned any values. They are being used here without initializing.

Option 4:

It is invalid, because in last line p + q is directly added without moving into the register.

Option 2:

Follows all the rules of static single assignment form. So, this is the answer.

Option 1:

As, it is a C program not a C++ program, so typecasting will de done automatically. There is no need to do typecasting. FALSE

Option 2:

Null means, memory location is 0. There is no difference between (x==NULL) and (NULL==x ), ( == ) is just to check the equality. FALSE

Option 3:

When the given code is compiled, it runs successfully, and x always points to a valid memory location and doesn’t result in dangling pointer.  FALSE

Option 4:

In the given code, x is assigned memory location two times. When memory location is assigned again to x, then the previous memory location gets lost and that results in memory leak problem. TRUE

Code Explanation:

void main () {

int *x = malloc(sizeof(int));    // Allocates memory to x i.e.   

if (NULL == x) return;                                                                              

x = assignval (x, 0);           // It calls the function *assignval ( int *x, int val ) and x gets the value 0.

if (x) {                                  // Condition becomes true, as x means address here

x = (int *) malloc (sizeof(int));           //Again allocates memory to x and previous memory get lost

if(NULL == x) return;                          // condition false as x means address not NULL

x = assignval (x, 10);                          // Again calls the function and x values becomes 10.

}

printf(“%d\n”, *x);                           // Print the value of x i.e. 10

After completing the data transfer, the TCP client executes a close primitive, and a FIN segment is sent to the TCP server by the client and wait for the corresponding ACK from the server. After this, two cases will happen:

1. When the ACK arrives from the server, a transition is made to state FIN-WAIT 2 by the client and then one direction of the connection will be closed. When other side closes too, a FIN comes in which is acknowledged and both sides will be closed.

2. In second case, instead of getting ACK from server till the time-out, TCP client received FIN from server. Client will acknowledge this FIN and then it will move to the close state. TCP client will wait for the ACK for its own FIN from server. After receiving ACK, TCP client will move to the TIME-WAIT state.

Diagram:

Concept:

Birthday attack means sending a fraudulent message with the same has value and digitally signed as that of original message.

Two ways are there for using digital signature:

One is, in which whole message will be encrypted first using sender’s private key and then receiver’s public key.

Second is, when only message digest is encrypted using sender’s private key.

Explanation:

Consider all the violations one by one:

1. S can launch a birthday attack to replace m with a fraudulent message. TRUE

 In this, S can use some fraudulent message and then encrypt it with its private key and then receiver’s public key.

2. A third-party attacker can launch a birthday attack to replace m with a fraudulent message.  FALSE

Third party attacker can’t launch birthday attack, as it doesn’t have sender’s private key and then can’t encrypt the message.

3. R can launch a birthday attack to replace m with a fraudulent message. FALSE

R can’t launch the birthday attack, because it doesn’t have the sender’s (S) private key and thereby can’t encrypt the message.

Concept: 

To find the irreducible equivalent of the given functional dependencies, we need to find the minimal cover set for these functional dependencies by removing all the left extraneous attributes and extra dependencies.

Explanation

V → W

VW → X

Y → VX

Y → Z

Consider,

V → W (As this is a single dependency that must be required, no need to remove)

VW → X ( In this, we have to delete the left extra attribute, for this we need to find the V⁺  and W⁺ from original dependencies, Now doing V⁺ if in V⁺ we get a W, then we can remove W attribute otherwise not same in case of W⁺)

So here, V⁺ = {V W X} and W⁺ = {W}

So, W → X can be removed from these functional dependencies.

Y → VX (Y → X can be find out using Y → V, V → X)

So, the irreducible equivalent of the given functional dependencies is:

V → W

V → X

Y → V

Y → Z

Concept:

Follow(X) is the set of terminals that can appear immediately to the right of non-terminal X in some sentential form. Rules for finding the follow (X) are given here as:

1) Follow (S) = {$}, where S is the start symbol.

2. If A → bBC is the production, where b, B and C are grammar symbols, then Follow (B) is first (C).

3. If A → bB is production then follow (B) is follow (A).

4. If A → bBC is production and first(c) contains ε, then follow (B) contains {first (C) - ε} U follow (A).

Explanation:

Follow (Q) = First (RS) = {w, ε} = {w}, First (S) = {w, y}

Diagram:

Concepts:

Multiple threads of the same process share other resources of process except register, stack and stack pointer.

A process is generally considered to consist of a set of threads sharing an address space, heap, static data, code segments and file descriptors.

Diagram:

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)

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

If edge weights are distinct then there exist unique MST.

Hence Statement I is correct.

When edge weights are distinct and positive in that case shortest path between any two vertices of the graph is not always unique. Shortest path can be different even if the edge weights are unique.

Example:

Distance between A → C (3) and A → B → C (1 + 2 = 3), both paths has same distance.

Hence statement II is incorrect.

Concept:

Re-entrant locks: It allows a thread to reacquire the lock multiple times without blocking on itself. It prevents the thread from the situation of deadlock.

Non- re-entrant locks: It don’t allow a thread to re-acquire the lock. Same process cannot acquire the lock multiple times without releasing it. So, here situation of deadlock occurs.

Explanation:

Three key points to be considered for this:

1. It is asking about minimum value of x and y

2. Locks are non-re-entrant (recursive)

3. Programs gets block if another lock is unavailable

Now, question is asking about the minimum value of x and y for which execution of p can result in a deadlock. So, minimum value of x and y are 1 and 1. Only one thread and one lock can cause deadlock, if the thread tries to reacquire the lock. If there are more than one lock available in the system, then process/thread can acquire the lock to do the further execution.

Concept:

Substitute the value of x as 1 in given function, if it results in $\frac{0}{0}$ form, then use L’Hospital rule for this.

In L’Hospital rule, both then numerator and denominator are differentiated.

Calculation: 

$\mathop {\lim }\limits_{x \to 1} \frac{{{x^7} - 2{x^5} + 1}}{{{x^3} - 3{x^2} + 2}} = \frac{0}{0}$

Apply L’Hospital rule,

$\mathop {\lim }\limits_{{\rm{x}} \to 1} \frac{{7{{\rm{x}}^6} - 10{{\rm{x}}^4}}}{{3{{\rm{x}}^2} - 6{\rm{x}}}}{\rm{;}}$

$\mathop {\lim }\limits_{{\rm{x}} \to 1} \frac{{7{{\left( 1 \right)}^6} - 10{{\left( 1 \right)}^4}{\rm{;}}}}{{3{{\left( 1 \right)}^2} - 6\left( 1 \right)}} = 1$

(p → q) → r is a contradiction which is possible only when r is false and (p → q) is true.

Now, from here we can clearly say that option 4 is correct as (r → p) → q means ¬ (r → p) ∨ q.

Since r is false, (r → p) is true and ¬ (r → p) becomes false.

So, it becomes (false ∨ q). Now it totally depends on q. Whenever q is true, this value will always be true.

Alternate Method:

Let X ≡ p → q, Y ≡ (p → q) → r ≡ X → r,

Z ≡ r → p and W ≡ (r → p) → q ≡ Z → p

Using Truth table

So, from truth table also, it is clear that (r → p) → q is always true when q is true, and Y is false.

Concept: 

The resultant of two equal vectors bisects the angle between them.

Explanation: 

w = u + αv (given)

where u and v are two vectors

Here, we can say that w is the resultant of two vectors u and αv. For w, to bisect the angle between u and v, magnitude of two vectors must be same.

$\parallel u\parallel = 2\parallel v\parallel$, [Given]

Also,              

$\parallel u\parallel = {\rm{\alpha }}\parallel v\parallel$, i.e. $2\parallel v\parallel = ;{\rm{\alpha }}\parallel v\parallel$

∴ α = 2.

Alternate Method:

By using graph method.

From here, u = 0 x + 2 y

v = 1 x + 0 y [Because, $\parallel u\parallel = 2\parallel v\parallel$]

It is given that, w = u + αv

Put value of u and v in w.

w = (0x + 2y) + α (1x + 0y)

= α.x + 2y

Now, vector w bisects the angle between u and v only when magnitude of along both the directions is same.

i.e. α should be 2.

Try to find out the eigen values by taking the example of matrix with rank 2. Then check if given statement follows from that or not.

Calculation:

A be (n x n) real valued square symmetric matrix of rank 2.

\(\mathop \sum \limits_{i = 1}^n \mathop \sum \limits_{j = 1}^n A_{ij}^2 = 50\),

which means, sum of square of all elements of A = 50.

Also, rank of A = 2 i.e. we have (n – 2) eigen values are 0.

So eigen values are in the form of a₁, a_2,0, 0, ……

Let us consider a matrix A = \(\left[ {\begin{array}{*{20}{c}} { - 5}&0\ 0&5 \end{array}} \right]\)

Here, for this eigen values are [-5, 5].

Take another example, B = \(\left[ {\begin{array}{{20}{c}} 5&0&0\ 0&5&0\ 0&0&0 \end{array}} \right]\) and C = \(\left[ {\begin{array}{{20}{c}} 6&0&0\ 0&{\surd 14}&0\ 0&0&0 \end{array}} \right]\)

Matrix B and C are of rank 2 and symmetric.

Eigen value for A = 5, 5, 0

And eigen value for B = $6,;\sqrt {14} ,;0$

As 0 and 5 are in the range of [-5, 5], So statement 1 is correct.

But eigen value with largest magnitude which is 6 for C must be strictly greater than 5 and in case of B largest value is 5 which is not strictly greater than 5, So, second statement is incorrect here.

STEP:

Append no. of 0’s equal to the degree of the generator polynomial to the original data and then divide the message with the generator polynomial. Remainder obtained from this will be added with the original message and transmitted as CRC.

Calculation:

Generator is given as x³ +x +1

Degree of the generator is 3.

So, 3 0’s is added to the data and new data will be 01011011000 and it is divided by 1011.

Diagram

Here remainder is 101. Append this to the original message. The message will become 01011011101. So, the original message 01011011 will be transmitted as 01011011101.

Output of one flip- flop becomes the input of another flip- flop. Two flip flops are given T and D flip flop. We can solve it using the characteristic equation of D and T flip flop and then calculate the next states Q_1N and Q_0N.

Explanation:

Here, T flip flop output is denoted by Q₁ and D flip flop output by Q_0.

Output of D flip flop i.e. Q₀ is coming at the T flip flop and Q₁ is going to D flip flop as input.

So, Q_1N = Q₁ EXOR T = Q₁ EXOR Q₀

       Q_0N = D = Q₁

Initially, Q₀ = Q₁ = 1

Next State Table:

So, Q₁Q₀ after 3^rd clock cycle is 11 and Q₁Q₀ after 4^th clock cycle is 01.

STEP:

Consider all the strings, then check if they can be generated from given grammar or not.

Derivation:

Grammar Production: S → SaS | aSb | bSa | SS | ∈

Option 1: String: abab

S → aSb

S → abSab 

S → ab∈ab

S → abab

So, abab can be generated by the given grammar.

Option 2: String: aaab

S → SS

S → SaSS 

S → SaSaSS 

S → aaaSbS 

S → aaa∈bS 

S → aaa∈b∈ 

S → aaab

Option 3: String:  abbaa

S → SS

S → aSbS 

S → a∈bS 

S → abbSa  

S → abbSaSa 

S → abb∈aSa

S → abba∈a

S → abbaa  

All three abab, aaab and abbaa are generated by the given grammar.

Only babba can’t be generated. So, option 4) is the answer.

STEP:

This problem can be solved using tree approach. Make a tree as the function call arrives, then traverse the tree from top to bottom and left to right.

Diagram:

So, output printed when fun1(5) is called is 53423122233445.

CASE 1:

Here, when foo(3) is called, this block is executed.

Int foo (int val) {     // val is 3 here

int x = 0;

while (val  > 0)        // condition becomes true as (3 > 0)

x = x + foo (val --); 

}

return val;

}

Here, foo (val - -) is equivalent to

1. foo(val )

2. val = val -1

val is post decremented, here it will not change the value of val during the function call. So, it will call foo(3) again and again. So, foo (3) is called infinite number of times causes abnormal termination.

Key point: 

In foo (3) , there is no problem of infinite loop. Because val is decrementing here.

CASE 2:

When bar (3) is called, block that is executed is,

int bar (int val) {               // val become 3

int x = 0;

while (val > 0) {            // condition becomes true as (3 > 0)

x = x + bar (val – 1);                     //here it will call bar (2)

}

return val;

}

So, in this case val is not not decremented in the loop only it is decrementing during the function call. i.e

bar (3) is called, then bar (2), then bar (1), then bar (0), again bar (0) …

bar(0) will return 0.

But while (val > 0) // this condition will always become true. As val value remain the same throughout.

So, Infinite loop problem occurs here in this case.

Grammar G₁ is:  S → aSb | T, T → cT | ∈

Grammar G₂ is:  S   → bSa | T, T → cT | ∈

Language generated by grammar G1 is in the form of acb* + ∈

Language generated by grammar G₂ is in the form of bca* + ∈

We have to find the intersection of L (G₁) and L (G₂)

So, only common production from two grammar G₁ and G₂ is:

S → T

T → cT | ∈

This will result in the language c*.  [Because, it generates string like ∈, c, cc, ccc, cccc, ………]

As, c* is a regular and infinite language. So, option 2) is the answer.

CFL Properties:

1. Union of two context free languages is context free.

2. Intersection of two context free languages may or may not be context free.

L₁ = {aⁿ bⁿ c^m | m, n ≥ 0}

This language is DCFL and hence CFL.  As number of a’s are equal to number of b’s in this. Hence, only one stack is needed.

L₂ = { a^m bⁿ cⁿ | m, n ≥ 0}

This language is also DCFL and hence CFL also. In this, number of b’s are equal to number of c’s, so, one stack is needed for this.

Now, from properties of CFL it is clear that union of two CFL is CFL.

So, statement 1 is correct

Statement 2 is correct.

 intersection of two CFL may or may not be CFL.

For, L₁ ∩ L_2, we require two stacks, which becomes the case of context sensitive language. L₁ ∩ L₂ is not a CFL. So, option 2) is incorrect.

Here, question is asking about the reason behind f is computable.

Since, x belongs to A* is a total function, that’s why every alphabet in x yields some alphabet in B* (same as f(x)) if given to a turing machine. In given statement, it is mentioned that f is computable only if there exists a Turing machine M which always halts with f(x) output. It means language that has to be always halting and accepting by Turing machine must be recursive language.

Therefore option 1 is the answer.

Important Points:

Second option is not true because recursive language has the membership property which proves that f is computable while in case of recursive enumerable languages, membership property is not available.

Concepts:

Belady’s anomaly is that the page-fault rate may increase as the number of allocated frames increases.

Explanation:

S1: Random page replacement algorithm (where a page chosen at random is replaced)

Suffers from Belady’s anomaly.

Random page replacement algorithm can behave like any replacement algorithm. It may behave as FIFO, LRU, MRU etc.). When random page replacement algorithm behaves like a FIFO page replacement algorithm in that case there can be chances of belady’s anamoly.

For this let us consider an example of FIFO case, if we consider the reference string 3  2 1 0 3 2 4 3 2 1 0 4 and 3 frame slots, in this we get 9 page fault but if we increase slots to 4, then we get 10 page faults.

So, page faults are increasing by increasing the number of frame slots. It suffers from belady’s anamoly.

S2: LRU page replacement algorithm suffers from Belady’s anomaly

It doesn’t suffers from page replacement algorithm because in LRU, the page which is least recently used is replaced by the new page. Also, LRU Is a stack algorithm. (A stack algorithm is one that satisfies the inclusion property.) and stack algorithm doesn’t suffer from belady’s anamoly.

Concept:

Safe tuple expression is the one that guaranteed to yield a finite number of tuples as its results. Otherwise, it is called unsafe.

Explanation:

∀ = for all

∃ = There exist / some

Consider the options one by one

Option 1:

 {t |∃u ∈ EMP(tEmpName] = u[EmpName] ∧ ∀ v∈ DEPT(t[DeptId] ≠ v[DeptId]))}

It gives all the name of employees who do not belong to the any department. Before ∧ operator, it results in finite tuples, after ∧ it results in infinite number of tuples. Finite ∧ infinite results in finite number of tuples. So, it is safe expression

Option 2:

{t |∃ u ∈ EMP(t[EmpName] = u[EmpName] ∧ ∃ v ∈ DEPT(t[DeptId] ≠ v[DeptId]))}

It gives the employee names who do not belong to some department. Before ∧ it is finite, after ∧ it is infinite. Results in a finite number of tuples. So, it is safe expression.

Option 3:

{t | ∃ u∈ EMP(t[EmpName] = u[EmpName] ∧ ∃ v ∈ DEPT(t[DeptId] = v[DeptId]))}

This expression gives the name of employees who belongs to atleast one same department. It also results in a finite expression. So, it is safe expression.

All three are safe expressions.

Concept:

Wound – wait scheme means the newer transactions are killed when an older transaction make a request for a lock being held by newer transaction.

Explanation:

Here, Unique timestamps are assigned to each transaction using Lamport’s logical clock.

1. Now, first check if is it wound – wait scheme?

If TS(T₂) < TS(T₁) then

T₁ is killed

else T₂ waits.

This logic comes under wound – wait scheme, because it is given that T₁ holds a lock on the resource R and T₂ has requested a lock on same resource R. When T₂ requests, T₁ is killed because timestamp of T_{1 ­}is larger than T₂ means T₁ is the newer transaction.

2. Now, wound – wait avoid starvation or not?

As newer transaction dies and restart with same timestamp and older one survives so after older transaction new will definitely execute. It means no possibility of starvation.

3. Deadlock free or not?

As, there is no starvation in this means no deadlock possibility.