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

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

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.

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

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, 2nd 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 1st 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

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:

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

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 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)

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).

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.

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

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.