GATE CS 2013 Official Paper (Previous Year Paper)

The correct answer is Option 2 i.e Lowest.

Let's look at the meaning of the given word

• Nadir: The lowest or most unsuccessful point in a situation.

From the above word meaning, we find that Nadir is closest in meaning to Lowest which is Option 2

Let's look at the meaning of all the given options

• Highest: Great, or greater than normal, in quantity, size or intensity.
• Lowest: Of less than average height from top to bottom or to the top from the ground.
• Medium: About hallway between two extremes of size or another quality; average.

The correct answer is Option 1 i.e Specificity

Explanation.

The statement given here is about antonyms. Let's look at the meaning of the first two words given in the sentence. 

• Universalism: The belief that all humankind will eventually be saved.
• Particularism: Exclusive attachment to one's own group, party, or nation.

Here we find that these two words are antonyms as they have opposite meanings. Therefore the next part also follows with antonyms. Hence the correct answer is the word opposite in meaning to Diffuseness.

Let's look at the meaning of the given word and the marked option. 

• Diffuseness​: Widely spread or scattered.
• Specificity: The quality of being unique to one subject.

Here we find that both the words have opposite meanings and therefore Option 1 Specificity is the correct answer. 

Let's look at the meaning of the other options. 

• Neutrality: The state of not supporting or helping either side.
• Generality: A statement or principle having general rather than specific validity.
• Adaptation: The action or process of adapting or being adapted.

Concept:

The sum of ‘n’ terms of an AP

\(S_n = \frac{n}{2}\left[ {2a + \left( {n - 1} \right)d} \right]\)

Calculation:

Given:

AP is 44, 42,- - - - - 2.

n = 22, a = 2 and d = 2

The sum of ‘n’ terms of an AP

\(S_n= \frac{n}{2}\left[ {2a + \left( {n - 1} \right)d} \right]\)

S_n = 11[4 + (21 × 2)] = 11 × 46 = 506

The correct answer is option 1) i.e. would fly

Explanation:

• The given sentence is a conditional sentence. There are 5-6 categories in conditional sentences.

1. Zero condition
2. First Condition
3. Second Condition
4. Third condition
5. Imaginary Condition
6. A few exceptional cases

• If we talk about the Imaginary condition, it describes a condition that is not possible in real life or it has very few possibilities of its occurrence.
• If I were a lion, I would eat you right now.​
• Syntax of Imaginary sentences: If + Sub + were/had + other words, Sub + would + Verb¹  + other words.

Important Point:

• There is one more thing to take care of while dealing with conditional sentences and i.e. Inversion of the verb.
• The inversion of the verb is to use the auxiliary verb before the subject. We use the concept of inversion in many cases and 'conditional sentences' is one of them.
• I am not working on this project.
• Am I not working on this project? (Inversion)
• If You had informed me, I would have come to you.
• Had you informed me, I would have come to you. (Inversion)

Conclusion: 

• The sentence given in the question is an imaginary condition and inversion has been done. So we must use **would + Verb¹ **in the second part.
• Hence, the completed sentence would be: Were you a bird, you would fly in the sky.​

The correct answer is Option 3 i.e She is an European

Explanation.

A and An are the indefinite articles used in English. As a rule:

• A is used before words starting with a consonant sound
• An is used before words starting with a vowel sound

In the given sentence the word European starts with a consonant sound i.e 'Y' sound. 

Since the word starts with a consonant sound the article before the word European should be A​. Therefore Option 3 is grammatically incorrect and thus the correct answer. 

Important Point.

One should always be aware that:

• The article A or An should be used depending upon the starting sound and not the letter.
• Example: An hour. Here since the 'h' is silent the stating sound is that of a vowel hence we use An.

Calculation:

Given:

\(\frac{1}{{\sqrt 1 + \sqrt 2 }} + \frac{1}{{\sqrt 2 + \sqrt 3 }} + \frac{1}{{\sqrt 3 + \sqrt 4 }} + \ldots + \frac{1}{{\sqrt {80} + \sqrt {81} }}\)

We can write as,

\( = ;\frac{1}{{\sqrt 2 + \sqrt 1 }} \times \left( {\frac{{\sqrt 2 - \sqrt 1 }}{{\sqrt 2 - \sqrt 1 }}} \right) + \frac{1}{{\sqrt 3 + \sqrt 2 }} \times \left( {\frac{{\sqrt 3 - \sqrt 2 }}{{\sqrt 3 - \sqrt 2 }}} \right) + \frac{1}{{\sqrt 4 + \sqrt 3 }} \times \left( {\frac{{\sqrt 4 - \sqrt 3 }}{{\sqrt 4 - \sqrt 3 }}} \right) + \ldots + \frac{1}{{\sqrt {81} + \sqrt {80} }} \times \left( {\frac{{\sqrt {81} - \sqrt {80} }}{{\sqrt {81} - \sqrt {80} }}} \right)\)

∵  a² – b² = (a + b) × (a – b)

\( = ;\frac{{\sqrt 2 - \sqrt 1 }}{{{{\left( {\sqrt 2 } \right)}^2} - {{\left( {\sqrt 1 } \right)}^2}}} + \frac{{\sqrt 3 - \sqrt 2 }}{{{{\left( {\sqrt 3 } \right)}^2} - {{\left( {\sqrt 2 } \right)}^2}}} + \frac{{\sqrt 4 - \sqrt 3 }}{{{{\left( {\sqrt 4 } \right)}^2} - {{\left( {\sqrt 3 } \right)}^2}}} + \ldots + \frac{{\sqrt {81} - \sqrt {80} }}{{{{\left( {\sqrt {81} } \right)}^2} - {{\left( {\sqrt {80} } \right)}^2}}}\)

\( = ;\frac{{\sqrt 2 - \sqrt 1 }}{{2 - 1}} + \frac{{\sqrt 3 - \sqrt 2 }}{{3 - 2}} + \frac{{\sqrt 4 - \sqrt 3 }}{{4 - 3}} + \ldots + \frac{{\sqrt {81} - \sqrt {80} }}{{81 - 80}}\)

\( = \sqrt 2 - \sqrt 1 + \sqrt 3 - \sqrt 2 + \sqrt 4 - \sqrt 3 + \ldots \sqrt {81} - \sqrt {80} \)

After cancellation of suitable terms,

We get,

\( = \sqrt {81} - \sqrt 1 \Rightarrow 9 - 1 = 8\)

Explanation:

The sample space for the event is (S) = 90 (i.e. from 10 to 99)

2-digit integers divisible by 7 = 14, 21, 28,..................91, 98.

i.e. Total 2-digit integers divisible by 7 = 13

∴ Total 2-digit integers not divisible by 7 = 90 - 13 = 77

∴ Required Probability =  \(\frac{Desired~Outcome}{Sample~Space}\) =  \(\frac{77}{90}\)

The correct answer is Option 4 i.e No adversity justifies giving up hope.

Explanation

The passage talks about the following things:

• How a man was on the verge of suicide, after several defeats.
• He observed a spider achieve the near-impossible goal despite countless failures.
• He drew inspiration from the spider that failed a countless number of times but didn't give up hope.

From the above passage and the above points, we find that the passage talks about not giving up despite our multitude of failures. 

The answer that resonates with the meaning of the passage is, therefore, Option 4 and thus the correct answer.

Concept:

Average speed is given by:

\(Average;speed = \frac{Total~ distance~ covered}{{Total;time;taken}}\)

Calculation:

Given:

Let the total distance covered by ‘D’

Distance covered by train = D/2

Distance covered by bus = D/4

Distance covered by cycle = D/4

Now, \(Average;speed = \frac{D}{{Total;time;taken}}\)

\(V_{avg}= \frac{D}{{\left( {\frac{{\frac{D}{2}}}{60} + \frac{{\frac{D}{4}}}{30} + \frac{{\frac{D}{4}}}{{10}}} \right)}} = \frac{1}{{\frac{1}{{120}} + \frac{1}{{120}} + \frac{1}{{40}}}} = \frac{{120}}{5} = 24~\frac{{km}}{{hr}}\)

 

As the Average speed does not depends on total distance D.

Let the total distance be LCM(60,30,10) = 60 km

time taken by car = \(\frac {30}{60} = 0.5 ~hour\)

time taken by bus = \(\frac{15}{30}=0.5~hour\)

time taken by cycle = \(\frac{15}{10}=1.5~hour\)

Total time taken = 0.5 + 0.5 + 1.5 = 2.5 hour

Average speed is :

\(Average;speed = \frac{Total~ distance~ covered}{{Total;time;taken}}= \frac{60}{2.5}=24 ~km/hour\)

Concept:

Total cost of erection = Rs. (W × T)

where, W = Labour wages in Rs., T = working hours.

Calculation:

Given:

Current erection cost(W × T) = Rs. 13,200, Increase in wages = \(\frac{W}{5}\), Decrease in working hours = \(\frac{T}{24}\)

Now, we know that

Total cost of erection = W × T

Revised wages = W + \(\frac{W}{5}\) = 1.2 W, Revised time = T - \(\frac{T}{24}\) = \(\frac{23T}{24}\)

∴ New cost of erection = 1.2W × \(\frac{23T}{24}\) = 1.2 × \(\frac{23}{24}\) × 13200 

∴ New cost of erection = 1.15 × 13200 = Rs. 15,180.

Concept:

Associative

A binary operation ∗ on a set S is said to be associative if it satisfies the associative law:

a ∗ (b ∗c) = (a ∗ b) ∗ c for all a, b, c ∈S.

Commutative

A binary operation ∗ on a set S is said to be commutative if it satisfies the condition:

a ∗b=b ∗a for all a, b, ∈S.

Calculations:

First started with checking for associative, x ⊕ (y ⊕ z) = (x ⊕ y) ⊕ z.

L.H.S: x ⊕ (y ⊕ z) = x ⊕ (y² + z²) = x² + (x² + z²)² .

R.H.S: (x ⊕ y) ⊕ z = (x² + y²) ⊕ z = (x² + y²)² + z² .

L.H.S ≠ R.H.S then the operator is not associative.

For commutative, x ⊕ y = y ⊕ x

L.H.S:  x ⊕ y = x² + y²

R.H.S: y ⊕ x = y² + x²  

L.H.S = R.H.S then the operator is Commutative.

Data:

Mean = \(\lambda \) = 3.

Formula:

\({\rm{p}}\left( {{\rm{X}} = {\rm{x}},{\rm{\lambda }}} \right) = \frac{{{{\rm{\lambda }}^{\rm{x}}}}}{{{\rm{x}}!{{\rm{e}}^{\rm{\lambda }}}}}\) 

Calculation:

\(p\left( {X \le 3,;\lambda = 3} \right)\)

\( = p\left( {X = 0,;\lambda = 3} \right) + ;p\left( {X = 1,;\lambda = 3} \right) + p\left( {X = 2,;\lambda = 3} \right)\)

\( = \frac{{{3^0}}}{{0!{e^3}}} + \frac{{{3^1}}}{{1!{e^3}}} + \frac{{{3^2}}}{{2!{e^3}}}\)

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

\(= \frac{{17}}{{2{e^3}}}\)

Concepts:

1. Switching two rows or columns causes the determinant to switch sign
2. Adding a multiple of one row/column to another row/column causes the determinant to remain the same

Calculations:

Now we can use the above concepts to determine the answer.

For options 1.

\(\left| {\begin{array}{*{20}{c}}
1&{x\left( {x + 1} \right)}&{x + 1}\
1&{y\left( {y + 1} \right)}&{y + 1}\
1&{z\left( {z + 1} \right)}&{z + 1}
\end{array}} \right| = \left| {\begin{array}{*{20}{c}}
1&{{x^2} + x}&{x + 1}\
1&{{y^2} + y}&{y + 1}\
1&{{z^2} + z}&{z + 1}
\end{array}} \right|\)

\(c3 \to c3 - c1.\)

\(\left| {\begin{array}{*{20}{c}}
1&{{x^2} + x}&x\
1&{{y^2} + y}&y\
1&{{z^2} + z}&z
\end{array}} \right|\)

\({\rm{c}}2 \to {\rm{c}}2 - {\rm{c}}3\)

\(\left| {\begin{array}{*{20}{c}}
1&{{x^2}}&x\
1&{{y^2}}&y\
1&{{z^2}}&z
\end{array}} \right|\)

Since,

\(\left| {\begin{array}{*{20}{c}}
1&{{x^2}}&x\
1&{{y^2}}&y\
1&{{z^2}}&z
\end{array}} \right| = ; - ;\left| {\begin{array}{*{20}{c}}
1&x&{{x^2}}\
1&y&{{y^2}}\
1&z&{{z^2}}
\end{array}} \right|\)

Therefore, switching two rows or columns causes the determinant to switch sign

\(\left| {\begin{array}{*{20}{c}}
1&{{x^2}}&x\
1&{{y^2}}&y\
1&{{z^2}}&z
\end{array}} \right| \ne \left| {\begin{array}{*{20}{c}}
1&x&{{x^2}}\
1&y&{{y^2}}\
1&z&{{z^2}}
\end{array}} \right|\) 

Therefore option 1 correct

Data:

number of bits = n = 8 

Formula:

Range of 2's compliment number with n bits is (–2^n-1 ) to +(2^n-1 – 1)

Smallest integer = –2n-1

largest integer = 2n-1 – 1

Calculation:

Smallest integer = –28-1 = –128

Concept:

A multiplexer or MUX is a combination circuit that contains more than one input line, one output line and more than one selection line.

Simple encoder takes 2ⁿ input bits and produces n output bits.

Explanation:

V = 1

When input D₃ = 1, then it does not care about the input D₀, D₁, and D₂

Output put will be 1, 1

When input D₃ = 0 and D₂ = 1, then it does not care about the input D₀, and D₁

Output put will be 1, 0

When input D₃ = 0, D₂ = 0 and D₁ = 1, then it does not care about the input D₀,

Output put will be 0, 1

When input D₃ = 0, D₂ = 0, D₁ = 0 and D₀ = 1,

Output put will be 0, 0

Here priority has been assigned to input and hence it is a Priority encoder.

Concepts:

To sort elements in increasing order, selection sort always picks the maximum/minimum element from remaining unsorted array and swaps it with the last/first element respectively (according to implementation) in the remaining array

Pseudo code of selection sort.

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

{

min_idx=i;

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

{

f(a[j] < a[min_idx])

min_idx=j;

}

swap(a[i],a[min_idx]); // only 1 swap each iteration for a total of n-1 iterations

}

Here, the 9^th line in pseudo code there are in single for loop and loop will run for the n – 1 time

swap condition in code will execute only n – 1 time.

Number of swaps = θ(n) = O(n).

Concept:

Height of BST could of order n, that is, O(n). Where n represents a number of elements in BST.

Explanation:

To insert an element, we need to search for its place first and inserting a node.  The search operation may take O(n) for a left-skewed binary search tree or a right-skewed binary search tree.

Right-Skewed Binary Search Tree

The time complexity of inserting an object into a binary search tree of n nodes is O(n).

Concepts

\({{\rm{L}}^{\rm{*}}} = {{\rm{L}}^0} \cup {{\rm{L}}^1} \cup {{\rm{L}}^2} \cup {{\rm{L}}^3} \cup {{\rm{L}}^4} \ldots \ldots .{{\rm{L}}^{\rm{k}}} \cup {{\rm{L}}^{{\rm{k}} + 1}} \ldots \ldots \ldots \)

For any language \({{\rm{L}}^0} = \epsilon\)

Concatenation of \({\rm{\Phi }}\) with any other language is \({\rm{\Phi }}\). It works as 0 in multiplication.

And for \({{\rm{L}}^{\rm{k}}} = {\rm{L}}.{\rm{L}}.{\rm{L}}.{\rm{L}}.{\rm{L}}.{\rm{L}}.{\rm{L}} \ldots \ldots \ldots {\rm{;L}}\) language is concatenated K- times.

Data:

 L₁ = Φ, L₂ = {a}

Calculation:

\({L_1}L_2^* \cup L_1^* = ;?\)

\({{\rm{L}}_1}\) concatenated with \(L_2^*\) and whole thing union with \(L_1^*\).

First \({\rm{;L}}_1^{\rm{*}} = {\rm{;;}}{\phi ^0} \cup {\phi ^1} \cup {\phi ^2} \ldots \ldots {\rm{;}}\)  \(= \epsilon \cup \phi \cup \phi \ldots \ldots = \left{ \epsilon \right}.\)

Similarly, \({\rm{L}}_2^{\rm{*}} = {\left{ {\rm{a}} \right}^0} \cup {\left{ {\rm{a}} \right}^1} \cup {\left{ {\rm{a}} \right}^2} \ldots \ldots {\rm{;}} = \epsilon \cup \left{ {\rm{a}} \right} \cup \left{ {{\rm{aa}}} \right} \ldots \ldots .. = {{\rm{a}}^{\rm{*}}}\)

\({{\rm{L}}_1}{\rm{L}}_2^{\rm{*}} \cup {\rm{L}}_1^{\rm{*}} = {\rm{\Phi ;}}{{\rm{a}}^{\rm{*}}} \cup \left{ \epsilon \right} = \left{ \epsilon \right}\)

Explanation:

Grammar with no epsilon- and unit-production

S → PQ

P → pp

Q → qq

Derive String: ppqq

S → PQ

S → ppQ

S → pppqq

String length = 4

Production needed = 4 – 1 = 3.

Concepts:

• First come first serve automatically executes queued requests and processes in order of their arrival.
• Round robin: In RR, each ready task runs turn by turn only in a cyclic queue for a limited time slice.
• Shortest –job-first: In which the process having the smallest execution time present in ready queue is chosen for the next execution.
• Shortest-remaining-time-first: In this scheduling algorithm, the process with the smallest amount of time remaining until completion is selected to execute next.

Data:

The given scheduling algorithm assigns priority proportional to the waiting time of a process and every process starts with priority zero (the lowest priority). The scheduler re-evaluates the process priorities every T.

Explanation

With options elimination method

• The scheduler re-evaluates the process priorities every T time units and decides the next process to schedule means here the algorithm using- pre-emptive approach. By this analogy we can eliminate the option 1(FCFS) and 3(SJF).
• This means there must be a time quantum T exists without time quantum scheduler cannot re-evaluates the process priorities and the scheduling algorithm assigns priority proportional to the waiting time of a process instead the less service time.
• From this it is quite clear that the algorithm cannot be Shortest-remaining-time-first and it will equivalent to Round-robin algorithms.

The correct answer is option 3.

Key Points

• Service-oriented computing involves the operations such as publish, find and bind which act on the service artifacts: service description and service implementation.

• Interoperability Infrastructure and Incremental learning for unreliable heterogeneous communicating Systems.

• XML is used for information representation.

• Business Process Modeling Notation (BPMN) is a flow chart method that models the steps of a process description from end to end.

Hence the correct answer is ​P - 3, Q - 1, R - 4, S - 2.

Answer: Option 3

Concept: 

Transport Layer:

It performs the same functions as that of the transport layer present in the OSI model. Here are the key points regarding the transport layer:

1. It uses TCP and UDP protocol for end-to-end transmission.
2. TCP is a reliable and connection-oriented protocol (In OSI Stack).
3. TCP also handles flow control.
4. The UDP is not reliable and a connection-less protocol also does not perform flow control.

Protocols utilized in this layer: TCP/IP and UDP protocols are deployed in this layer.

Explanation:

1. Real-Time Multimedia: For real-time multi-media applications the packets must be delivered faster if some packets are lost in between that is ok with these particular types of applications. Hence UDP will work just fine for these applications.
2. File Transfer: for file transfer applications generally used FTP. FTP also relies on TCP.
3. Domain Name Server: DNS generally employs UDP as its underlying transport layer protocol. ( at Some places it also uses TCP but we have to choose the best possible answer among the available options)
4. E-mail: Email employs SMTP which also uses TCP.

Hence Option 3 is the correct answer.

The correct answer is option 4.

Key Points

As previously indicated, X adds a digital signature to message M, encrypts M, and sends it to Y.

The following key sequences are used for the operations to ensure that Y receives the message and is able to decrypt it.

• Encryption X’s private key followed by Y’s public key  In order to guarantee authenticity and confidentiality, the message should be encrypted using the sender's private key and receiver's public key.
• Decryption Y’s private key followed by X’s public key Receiver Y will need to decrypt it using its own private key and send X's public key when received with the encrypted message.

Hence the correct answer is Encryption: X’s private key followed by Y’s public key; Decryption: Y’s private key followed by X’s public key.

Answer: Option 3

Concept: 

The Routers only contains 3 layer that's the reason sometimes they also called as 3-layer switch.

The Router is a physical or virtual internetworking device that is designed to receive, analyze, and forward data packets between computer networks. A router examines a destination IP address of a given data packet, and it uses the headers and forwarding tables to decide the best way to transfer the packets.

Explanation: 

At Intermediate Router R the packet will not go beyond the network layer. Hence Network layer will only be visited once at both the routers.

But the Data link layer will be visited twice.

Hence Network layer will be visited 4 times and the Data link layer will be visited 6 times (1 + 2 (at R) + 2 (at R) + 1 = 6 )

Answer: Option 3

Concept:

Primary index:

It is defined on an ordered data file and the data file is ordered on a key field. The key field is generally the primary key of the relation.

Clustering Index:

It is defined on an ordered data file. The data file is ordered on a non-key field.

Secondary index:

It may be generated from a field that is a candidate key and has a unique value in every record, or a non-key with duplicate values only dense ordering in the non-clustered index (Secondary index) as sparse ordering is not possible because data is not physically organized accordingly

Multi-level Index:

Index records comprise search-key values and data pointers. The multi-level index is stored on the disk along with the actual database files.

B/B+ tree index → Multi-level index

Explanation:

The only option matches with the definition of the Clustered index in Option 3.

because for Clustered index two necessary things 1. index on non-key fields 2. must be on ordered data file.

Option 1 and Option 2 will be a clustered indexes.

Option 4 violates the ordered data file property, of the clustered index.

Hence Option 3 is correct.

Answer: Option 2

Explanation: 

Given

Process X will perform down operation on a, b, c

Process Y will perform down operation on b, c, d

Process Z will perform down operation on c, d, a

all the binary semaphores initialized to 1.

Option 1: X: P(a)P(b)P(c) Y: P(b)P(c)P(d) Z: P(c)P(d)P(a)

Consider the following sequence 

X: P(a)    // a = 0

Y: P(b)   // b = 0

Z: P(c)   // c = 0

X: P(b)   // unsuccessful down operation hence X will be blocked.

Y: P(c)   // again unsuccessful down operation hence Y will be blocked.

Z: P(d)   // d=0

Z: P(a)   // unsuccessful down operation hence Z will be blocked. Hence all 3 processes are blocked. so this option does not represent the deadlock-free order.

Option 2: X: P(b)P(a)P(c) Y: P(b)P(c)P(d) Z: P(a)P(c)P(d)

In this Order, you execute in any sequence deadlock not possible. Hence this is the correct Option**.**

Option 3: X: P(b)P(a)P(c) Y: P(c)P(b)P(d) Z: P(a)P(c)P(d)

X: P(b)   // b = 0 

Y: P(c)   // c = 0 

Z: P(a)   // a = 0 

X: P(a)   // unsuccessful down operation hence X will be blocked.

Y: P(b)   // again unsuccessful down operation hence Y will be blocked.

Z: P(c)   // unsuccessful down operation hence Z will be blocked. Hence all 3 processes are blocked. so this option does not represent the deadlock-free order.

Option 4: X: P(a)P(b)P(c) Y: P(c)P(b)P(d) Z: P(c)P(d)P(a)

X: P(a)   // a = 0

Y: P(c)   // c = 0

Z: P(c)   // unsuccessful down operation hence Z will be blocked.

X: P(b)   // b = 0

Y: P(b)   // unsuccessful down operation hence Y will be blocked.

X: P(c)   //  unsuccessful down operation hence X will be blocked. Hence all 3 processes are blocked. so this option does not represent the deadlock-free order.

Answer: Option 3

Concept: 

A Turing machine is an automaton whose temporary storage is tape. This tape is divided into cells, each of which is capable of holding one symbol. Associated with the tape is a read-write head that can travel right or left on the tape and that can read and write a single symbol on each move.

Languages that are recognized and accepted by this Turing machine are Turing recognizable languages.

Turing machines can be viewed as acceptors. Turing recognizable languages are those for which there exists a Turing machine that will halt and accept the strings in that language. Turing machine does not halt for those strings which are not present in a language.

Closure properties of Turing recognizable languages:

1. Union

2. Concatenation

3. Kleen closure

4. Intersection

Turing recognizable languages are not closed under complement.

The power of the Turing machine in both the cases deterministic and non-deterministic is the same.

For every deterministic Turing machine there exists a non-deterministic Turing machine that recognizes the same language as that of the deterministic machine. So, this statement is correct.

Explanation: 

Statement 1:For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine

This Statement is true. The question is asking for a false statement.

Statement 2: Turing recognizable languages are closed under union and complementation.

This Statement is false since Turing recognizable languages are not closed under complementation operation.

Statement 3: Turing decidable languages are closed under intersection and complementation.

This Statement is true. since Turing decidable languages are nothing but recursive languages and recursive languages are closed under both intersection and complementation operation.

Statement 4: Turing recognizable languages are closed under union and intersection.

This Statement is true. since Turing recognizable languages are closed under union and intersection.

Hence Option 3 is the correct answer.

The correct answer is option 1.

Key Points

BFS or DFS can be used to find whether there is a cycle in an undirected graph. For example, see DFS based implementation to detect cycle in an undirected graph. The time complexity is O(V+E) which is polynomial and it is a P problem.

Every p problems are NP problem (since P⊂NP). So, statement 1 and statement 2 are true.

NP-Complete ⊂ NP, for every NP problem, has a non-deterministic polynomial-time algorithm. Hence statement 3 is true.

Hence the all the statements are correct

The correct answer is option 3.

EXPLANATION

• The Bellman-Ford algorithm is an algorithm that calculates the shortest paths in a weighted digraph from one source vertex to all other vertices.
• Bellman-Ford is also simpler than Dijkstra and suites well for distributed systems. But time complexity of Bellman-Ford is O(VE), which is more than Dijkstra.  where V is a number of vertices and E is a number of edges. For a complete graph with n vertices, V = n, E = O(n²). So overall time complexity becomes O(n³).

Hence the correct answer is Θ(n3).

The correct answer is option 1.

CALCULATION:

Position of main memory set in the cache is = (Main memory block number) mod (Total number of cache sets)

As the lines in the set are placed in sequence, we can have the cache blocks (lines) from 0 to (k-1) in each set.

Number of sets = V, Main memory block number=J 

So, 1^st line of cache= \((j \space mod \space v) \times K\)

Last line of the cache= \((j \space mod \space v) \times K+(K-1)\)

Hence the correct answer is (j mod v) * k to (j mod v) * k + (k - 1).

The correct answer is option 4.

Key Points

 x'y'+xy = x⊙y (exclusive NOR)

x ⊕ y' = x'y' + x(y')' =  x'y'+xy = x ⊙ y (exclusive NOR )

x' ⊕ y = (x')' y + x'y' =  xy + x'y'= x ⊙ y (exclusive NOR )

x' ⊕ y' = (x')' y' + x'(y')' =  xy' + x' y = x ⊕ y (exclusive OR )

Hence the correct answer is x' ⊕ y'.

Additional Information

X ⊕ Y = XY' + X' Y (exclusive OR)= Logical inequality operator.

X ⊙ Y = X' Y' + XY (exclusive NOR)= Logical equality operator.

The correct answer is option 1.

Key Points

If \(Lt_{x \to a^-} f(x) = Lt_{ x \to a^+ } f(x)=f(a) \space then f(x) is \space continuous \space at \space x=a \)

Option 1: Correct

\(f\left( x \right)\left{ {\begin{array}{*{20}{c}} {2,;;;;if;;;x = 3}\ {x - 1,;;;;if;;;x > 3}\ {\frac{{x + 3}}{3},;;;;if;;;;x < 3} \end{array}} \right.\)

\(f(3) = 2\)

\(\Lt_{x \to 3^+} f(x) = Lt_{x \to 3} {(x-1)}=2, \)

\(Lt_{x \to 3^-} f(x) = Lt_{x \to 3} {(x+3) \over 3}=2,\)

 

Therefore the function is continuous at x = 3

The correct answer is option 4.

Key Points

Formula:​

The Trapezoidal Rule for approximating \(\int_{a}^{b} f(x) dx\)  is given by

\(\int_{a}^{b} f(x) dx={ {\bigtriangleup(x)} \over 2}[f(x_0)+f(x_n)+2(f(x_1)+f(x_2)+f(x_3)+...+f(x_{n-1}))] \{\bigtriangleup(x)}={b-a \over n} and \space x_i= a+i\bigtriangleup x \)

Calculation:

\(\bigtriangleup(x)={3-0 \over 10}=0.3\)

\(\int_{0}^{3} f(x) dx={ {0.3} \over 2}[0+9+2(0.09+0.36+0.81+1.44+2.25+3.24+4.41+5.76+7.29)] \={0.3 \over 2}{ [9+2(25.65)]} \={0.3 \over 2} { [9+51.3]} \=9.045\)

Hence the correct answer is 9.045.

The correct answer is option 1

EXPLANATION:

A cycle length 3 requires 3 vertices

Total number of ways choosing 3 vertices from 8 vertices = \({{\rm{;}}^8}{{\rm{C}}_3} = 56\)

The probability that three vertices form a cycle = probability of an edge between vertices 1 and 2 + probability of an edge between vertices 2 and 3 + probability of an edge between vertices 1 and 3

The probability that three vertices form a cycle = \(\frac{1}{2} \times \frac{1}{2} \times \frac{1}{2} = \frac{1}{8}\)

So, the expected number of unordered cycles of length 3 = \(56\times{1\over8}=7\)

Answer: Option 3 

Explanation: 

By handshaking lemma

Sum of all Degree of vertices of an undirected graph is even 

\(\mathop \sum \limits_{i; = ;1}^v di\) = 2 ×| v| (statement Q is true)

via Handshaking lemma, we can prove the P statement as well. 

Sum of odd degree + sum of even degree = 2×|v|

sum of odd = 2 × |v| - sum of even degree

Hence Statement P is also true.

The correct answer is “option 1”.

EXPLANATION:

Statement P: True

Every edge in a given cycle graph will become a vertex in the new defined graph L(G) and every vertex of the cycle graph will become an edge in the new graph.

Statement R: False

Consider a planar graph with 5 vertices and 9 edges.

Also assume, the degree of one vertex is 2 and the rest is 4.

So L(G) has 9 vertices (since G has 9 edges) and 25 edges.

But, the planar graph must satisfy the condition:

|E| < = 3|V| - 6

So for 9 vertices,

|E| < = 3×9- 6

|E| < = 21 

But L(G) has 25 edges & hence it is not planar.

So this statement is false.

Since Option 2 and 3 contains R, these options are eliminated.

Statement S: False

From this tree:

By drawing its line graph, a cycle graph can be formed of 3 vertices.

So this statement is wrong.

Hence, option 4 is wrong.

Hence, the correct answer is “option 1”.

Statement:

None of my friends are perfect

From option it can be considered:

F(x) – x is my friend

P(x) – x is perfect

In mathematical logic form:

“All my friends are imperfect” means

∀x (F(x) → ¬ P(x))

∀x (¬F(x) ∨ ¬P(x))

∀x ¬(F(x) ∧ P(x))

¬∃x (F(x) ∧  P(x))

The correct answer is "option 4".

CONCEPT:

Micro-operations are also known as micro-ops.

They are the atomic or functional operations of a processor.

It is an elementary Central Processing Unit (CPU) operations performed during one clock pulse.

Micro-operations are low-level instructions, used in some designs, to implement complex instructions.

Micro-operations generally perform data stored in one or more registers.

EXPLANATION:

1. Program counter holds the next instruction value to be executed.

Here**, MBR <- PC** means the value of the program counter will get stored in MBR. 2. MAR <- X means some address value X is storing in MAR so to access memory location X.

3**. PC <- Y** means storing new instruction value Y to the program counter to access new instruction. 4. Memory <- MBR means MBR register will store its value to Memory. This saves the previous value of PC to memory.

This sequence of instructions matches with Interrupt Service Routine (ISR) since the sequence of instructions saved the address of current instructions into memory.

Then started executing new address by loading new instruction value to Program counter.

Hence, the correct answer is “option 4”.

Additional Information

1. Instruction fetch means fetching the instruction.

2. Operand fetch means fetching the operands.

3. Conditional branch means the program will branch to another instruction after satisfying a condition.

Data:

File size is 42797 KB= 42797 ×210 B=85594×29 B.

recording surfaces = 16 (0 to 15)

cylinders = (0-16383)

sectors(0-63

one sector=512 B

Calculation:

The file will be stored in 85594 sectors, that is, it needs to cross 85594 sectors

starting of the file is

number of cylinders to cross = (85594÷16)× 64 = 83 cylinders

remaining sectors to cross = 85594-(83×16× 64) = 602

number of surfaces to cross = 9

so to cross 9 surfaces we need to cross on more cylinder as the file has started at surface 9 and no surface in the cylinder is 16 so

number of the cylinder to cross=83+1=84

so cylinder number = 1200+84=1284

The correct answer is option 3

CONCEPT:

To sort K elements using heap sort, time complexity = \(\theta(k\log k)\)

Let assume \(k={\rm }\left( {\frac{{\log n}}{{\log \log n}}} \right)\) from option c

put the value of k into heap sort time complexity

⇒ \(\theta(k\log k)\)

⇒\(\theta({\rm }\left( {\frac{{\log n}}{{\log \log n}}} \right)\log {\rm }\left( {\frac{{\log n}}{{\log \log n}}} \right))\)

⇒\(\theta({\rm}\left(\frac{\log n}{\log\log n}\right){\rm}\left({\log\log n-\log\log\log n}\right))\)

⇒\(\theta(\log n-\frac{log\log\log n}{\log\log n})\)

⇒\(\theta(\log n)\)

So the answer is option c

The correct answer is “option 2”.

CONCEPT:

The time complexity of an algorithm or a function is the amount of time taken by that function or algorithm to run as a function of the length of the input.

It basically measures the time taken by an algorithm to execute each algorithm.

It signifies the total time required by the program or algorithm to run till its completion.

Space complexity is of any algorithm or a function is the amount of memory space taken by that function or algorithm to solve an instance of any computational problem as a function of characteristics of the input.

EXPLANATION:

int unknown(int n){                      //a function named unknown, returns integer value, called with integer argument “n”

 int i, j, k=0;                                 // variable I, j, k initialized with value 0

for (i=n/2; i<=n; i++)                    //This outer loop runs approx. (\(\frac{n}{2}\)) times

                                                    Consider n = 8 then value of i will be 4,5,6,7,8.

 for (j=2; j<=n; j=j*2)                   // This inner loop will run (\(\frac{n}{2}\)log₂n) times.

                                                   Consider n = 8 then value of j will be 2,4,8, (log₂8 = 3)

 k = k + n/2;                   //Final value k will be \(\frac{n}{2}\) × \(\frac{n}{2}\)log₂n times i.e. \(\frac{n^2 }{4}\)log₂n.

              return (k); 

}                                      

This function will have time complexity O(n²log₂n).

Hence the correct answer is “option 2”.

The correct answer is “option 4”.

EXPLANATION:

Option 1:  TRUE

Language L₁ can be written as 010*.

So, L₁ is a regular language.

Language L₂ has one comparison p! = r.

So, L₂ is a Context-free language.

Option 2:  TRUE

According to the closure property of context-free language, intersection of a regular language with Context-free language is also Context-free language.

 So, L1 ∩ L2 is context-free.

Option 3:  TRUE

According to the closure property of context-free language (CFL), it is not closed under complementation.

So, L₂ can be assumed as Context-sensitive language (CSL) since every CFL is CSL.

Also, CSL is closed under complementation and every CSL is recursive.

So complement of L₂ is CSL & hence recursive.

Option 4:  FALSE

According to the closure property of regular language, it is closed under complementation.

So, complement is L₁ also regular.

Hence, the complement of L1 is context-free but not regular is false.

The correct answer is “option 4”.

The correct answer is option 4.

Key Points

 1. The complement of L(A) is context-free. 

     True, According to closure property complement regular language is regular.  And every regular language is context-free. 2. L(A) = L((110 + 0)(0 + 1)01)

     True, Above DFA accepts the regular equation and generate the strings like {0,00,01,10,000,001,010,011,100,101,110,..}

3. For the language accepted by A, A is the minimal DFA.

    False, The given DFA can be minimized to two states and the minimal DFA is, 

4. A accepts all strings over {0, 1} of length at least 2.

    False, DFA accepts the string of length 1 and accepted strings are {0,00,01,10,000,001,010,011,100,101,110,..}

 Hence the correct answer is 3 and 4 only.

Additional Information

The correct answer is option 4.

Key Points

X, W reads X and increment X by 1.

Y, W reads X and decrement by 2.

Start with X,  will perform P(S) then S=1, read X=0, X=X+1=1

Then Y will perform P(S) then S=0, read X=0, X=X-2=-2, then store X. V(S), S=1

Then Z will perform P(S) then S=0, read X=-2, X=X-2= -4, then store X, V(S), S=1 

Then X will  store X, V(S), S=2, X=1

Then W will perform  P(S), S=1, read X=1, X=X+1=2, store X, V(S), S=2, X=2

Hence the correct answer is 2.

The correct answer is option 1.

Key Points

Structured Query Language, Relational algebra, Tuple relational calculus, and domain relational calculus all are representing the same. i.e, all these expressions representing finding the distinct names of all students who score more than 90 % in the course numbered 107.

(I) SELECT DISTINCT S.sname

FROM Students as S, Registration as R

WHERE R.rollno=S.rollno AND R.courseno=107 AND R.percent >90

The above query is Structured Query Language, It takes two tables are student and registration and cross-product the tuples based on Rollno attribute those tuple course number should be 107 and percentage more than 90%.

(II) Πsname (σcourseno = 107∧percent>90 (Registration ⋈ Students))

The above query is Relational algebra. ​It first performs a natural join of Students and Registration and natural join implicitly join on the basis of the common attribute, which here is roll no. Select operation( sigma) keeps only those rows where the student is registered for course no 107, and the percentage is more than 90%. And then the projection operation (pi) projects only distinct student names from the set.

(III)  {T | ∃S ∈ Students, ∃R ∈ Registration (S.rollno = R.rollno ∧R. courseno = 107 ∧ R.percent > 90 ∧ T.sname = S. sname)}

The above query is Tuple relational calculus. It is not a procedural language. It just represents a declarative mathematical expression. It finding the distinct names of all students who score more than 90 % in the course numbered 107.

(IV)  {〈SN〉 | ∃SR∃RP(〈SR, SN〉 ∈ Students ∧ 〈SR, 107, RP〉 ∈ Registration ∧ RP > 90)}

The above query is domain relational calculus. It is not a procedural language. It just represents a declarative mathematical expression. And S_N is a domain variable. It finding the distinct names of all students who score more than 90 % in the course numbered 107.

Hence the correct answer is I, II, III, and IV.

Data:

Length of packet = L = 10,000 bits

Bandwidth = BW = 500 Mbps = 500 × 106 bps

Velocity = V = 2,00,000 km/s = 2 × 105 km/s

d → length of cable

Tp → propagation time

Tt → transmission time

Formula:

For CSMA/CD,

\({T_t} \ge 2 \times {T_p}\)

\(\frac{L}{{BW}} \ge 2 \times \frac{d}{V}\)

\(d \le \frac{{L \times V}}{{2 \times BW}}\)

Calculation:

\(d \le \frac{{10,000 \times 2 \times {{10}^5};}}{{2 \times 500; \times {\rm{;}}{{10}^6}}}\)

\(;d \le 2;km\)

\({d_{max}} = ;2;km\)

The correct answer is option 3

EXPLANATION:

In the question given that M bit is 0, it means that no more fragments remaining to send after this fragment, hence this is the last fragment.

So the answer should be either option 1 or option 3

Let's check

the value of HLEN is 10 × 4 =40B because the scaling factor is 4 byte for the field,

Total length is given that is 400B

Payload size =Total length - header length

Payload size = 400B - 40B

Payload size = 360B

Fragment offset = 300 × 8 =2400B, where 8 is the scaling factor

Value of the first byte for this last fragment =2400

and the last byte is =2400 +360 -1 = 2759, here we subtract -1 because start the byte from 0

So the correct answer is option 3

The correct answer is option 1.

Key Points

• The degree to which the elements within a module belong together is referred to as cohesion.
• The degree of interdependence between software modules is referred to as coupling. A measure of how closely two routines or modules are linked.

\(Coupling = {(Number \space of \space external \space links) \over (Number \space of \space modules) }\)

\(Cohesion = {(Number \space of \space internal \space links) \over (Number \space of \space methods) }\)

Coupling between M1 and M2 =  \({2 \over 2}=1\)

The cohesion of M1 =\({8 \over 4 }=2\)

The cohesion of M2=\({6 \over 3 }=2\)

After moving method m to M2, we get the following graph as

 

Coupling between M1 and M2 =  \({2 \over 2}=1\)

The cohesion of M1 =\({6 \over 3 }=2\)

The cohesion of M2=\({8 \over 4 }=2\)

Hence the correct answer is There is no change.

The correct answer is “option 3”.

EXPLANATION:

Process X:

private i;

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

     a[i] = f(i);

     ExitX(R, S);

}

Process Y:

private i;

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

      EntryY(R, S);

      b[i] = g(a[i]);

}

From the given structure of two processes, main purpose is :

1. Deadlock should not occur
2. Binary semaphore must not be assigned value greater than 1.

Option 1: FALSE

ExitX(R, S) {

P(R);

V(S);

}

EntryY(R, S) {

P(S);

V(R);

}

This statement will leads to deadlock.

So this statement is false.

Option 2: FALSE

ExitX(R, S) {

      V(R);

      V(S);

}

EntryY(R, S) {

         P(R);

          P(S)

This statement will increase value of semaphore between 1 to n.

But value of binary semaphore must be less than 1.

So this statement is false.

Option 3: TRUE

ExitX(R, S) {

        P(S);

        V(R);

}

EntryY(R, S) {

          V(S);

          P(R);

}

In this statement, each and every value inserted by the process X in array will be immediately consumed by process R.

Hence, this statement represents correct implementation of ExitX & EntryY.

Option 4: FALSE

ExitX(R, S) {

        V(R);

        P(S);

}

EntryY(R, S) {

         V(S);

         P(R);

}

This statement will also increase value of semaphore R & S between 2 in many cases which should be less than 1.

So this statement is false.

Hence, the correct answer is “option 3”.

The correct answer is option 4.

Key Points

1. Cannot be merged since lookaheads are different.

False, We can find the LALR stage by merging LR(1) states that have the same set of the first component. We can take the union of lookahead symbol of the respective item. The given LR (1) items can be merged as, 

X → c.X, c/d/$

X → .cX, c/d/$  

X → .x, c/d/$   

2. Can be merged but will result in S-R conflict.

3. Can be merged but will result in R-R conflict.

The given items have no reduced entry(means dot at end of the production) then there is no S-R conflict and R-R conflict in the given grammar. So clearly it says both option 2 and 3 are false. 

4. Cannot be merged since goto on c will lead to two different sets. 

False, Because goto is carried on Non-terminals symbols, not on terminal symbols, and c is a terminal symbol.

Hence the correct answer is 1, 2, 3 and 4.

Additional Information

Checking LALR conflicts:

Shortcut:

Let's consider the production A → αaβ and B→α and a,b are lookaheads of the grammar. Then S-R conflicts will occur when one production with reducing production and another one is a shift production. This will make the conflict when shifting terminal and lookahead are same then parsing table has multiple entries. And R-R conflicts have two productions with the same lookaheads.

• If there is no S-R conflict in LR(1) state it never be reflected in the LALR(1) parser.
• If there is no R-R conflict in LR(1) state it may be R-R conflict in LALR(1) parser.
• The parse generates tool 'YAAC' uses LALR(1) parsing algorithm$.

The correct answer is "option 4".

CONCEPT:

If any algorithm can be constructed for a problem such that the answer to the problem can be answered correctly then the problem is said to be decidable.

Example: To find 5 prime numbers, the algorithm can be constructed, so this problem is decidable.

The definition of decidability in terms of the Turing machine: 

“For any problem, if there exists a Turing machine which halts on every input with an answer- yes or no then the problem will be decidable”.

Turing decidable problems are the problem for which the Turing machine always halts on every input, accepting or rejecting it.

EXPLANATION:

Option 1:

The emptiness problem for Context-free language is decidable.

So, L(G) = Φ is decidable.

Option 2:

The completeness problem for Context-free language is not decidable i.e. un-decidable.

So, L(G) = Σ* is un-decidable.

Option 3:

Whether the language generated by a Turing machine is always un-decidable.

Therefore, Is L(M) regular is un-decidable.

Option 4:

The problem of whether any language will get accepted by DFA and NFA is decidable.

So, Is L(A) = L(N) is decidable.

Hence, the correct answer is “option 4”.

The correct answer is option 2

EXPLANATION:

Since c is passed by value and x is passed by reference, all functions will have the same copy of x, but different copies of c.

CODE:

int f (int &x, int c) {

c = c - 1;

if (c == 0) return 1;

x = x + 1;

return f(x,c) * x;

}

Function call

 

So, the answer is 6561

The correct answer is "option 4".

CONCEPT:

A Binary Search Tree (BST) is also known as an ordered tree or sorted binary tree.

It is a binary tree with the following properties:

1. The left sub-tree of a node contains only nodes with key-value lesser than the node’s key value.
2. The right subtree of a node contains only nodes with a key-value greater than the node’s key value.

There are three types of traversal:

1. In-order traversal: In this traversal, the first left node will traverse, the root node then the right node will get traversed.
2. Pre-order traversal: In this traversal, the first root node will traverse, the left node then the right node will get traversed.
3. Post-order traversal: In this traversal, the First left node will traverse, the right node then the root node will get traversed.

The in-order traversal of the Binary search tree always returns key values in ascending order.

EXPLANATION:

The pre-order traversal of given BST is:

30, 20, 10, 15, 25, 23, 39, 35, 42.

So, the In-order traversal of the BST is:

10, 15, 20, 23, 25, 30, 35, 39, 42.

The Binary Search Tree is:

So the post-order traversal of the tree is:

15, 10, 23, 25, 20, 35, 42, 39, 30

Hence, the correct answer is "option 4".

The correct answer is "option 1". 

CONCEPT:

A queue is a data structure that is used to manage data in the First In First Out (FIFO) rule.

FIFO rule states that any element that enters the queue first will get deleted first from the queue.

Enqueue is the operation of inserting elements in the queue.

Dequeue is the operation of deleting elements from the queue.

EXPLANATION: 

Initially, the queue is empty and n operations have to be performed.

There are two solutions for this problem:

First solution: Perform all Enqueue operations i.e. n Enqueue operations.

So, The time complexity for the n operations will be O(n).

Second solution: Perform mix Enqueue & Dequeue operations.

Perform n/2 operations for En-queue & n/2 operations for De-queue or perform En-queue and De-queue operations alternatively (totalling n times).

So, the total complexity will be O(n).

Hence, the correct answer is “option 1”.

The correct answer is "option 2".

CONCEPT:

A pipeline is a process where multiple instructions get overlapped during execution.

The pipeline is divided into stages and these stages are connected with one another to improve the execution process

The pipeline allows storing and executing instructions in an orderly process.

In the instruction pipeline, a stream of instructions is executed by overlapping phases of the instruction cycle like fetch, decode, execute, etc.

It reads an instruction from memory while previous instruction being executed in others segments of the pipeline.

EXPLANATION:

 

Cycle time = max of all stages delay + buffer delay

= max (5ns,7ns,10ns,8ns,6ns) + 1ns

= 10ns + 1ns

= 11ns

Out of all the instructions from I1 to I12, I4 is the only branch instruction.

When I4 takes branch, the control will jump to the target instruction I9.

There will be 3 stalls in stages DI, FO & EI.

So after 3 stalls, I9 will start its execution as it is a branch target.

So, total number of clock cycles = 15

Since 1 clock cycle time = 11ns

So, total time to complete the program = 15 × 11ns = 165 ns

Hence, the correct answer is "option 2".

RAM capacity = 1024 words of 8 bit each = 1K × 8

RAM to construct = 32 K × 8

Number of chips required = \(\frac{{RAM;to;construct}}{{Ram;capacity}}\)

Number of chips required = \(\frac{{32;K; \times 8}}{{1K; \times 8}} = 32; \times 1\)

We use 5 : 32 decoders for this. But requirement is of 2 × 4 decoders.

11 decoders are required for this conversion.

At Layer 3 we will decode 32 rams from 8 2:4 decoders. At Layer 2 we will decode those 8 inputs from 2 2:4 decoders. And finally to decode those 2 decoders we will use another decoder.

So total = (1+2+8)

So, total 11 decoders are needed with enable line needed to construct a 32K × 8 RAM from 1K × 8 RAM.

The correct answer is "option 1 and 4".

EXPLANATION:

Option 1:

 ∀x (∃z (¬ β) → ∀y (α))

→ ∀x (¬∃z (¬ β) v ∀y (α))

→ ∀x (∀z (β) v y (α))

→ ¬∃x ¬ (∀z (β) v y (α))

→ ¬∃x (¬∀z (β) ∧ ¬y (α))

Hence, ∀x (∃z (¬ β) → ∀y (α)) is not equivalent to ¬ ∃x (∀ y (α) ∧ ∀ z(β)).

Option 2:

∀x (∀z (β) → ∃y (¬ α))

→ ∀x (¬∀z (β) v ∃y (¬ α))

→ ¬∃x¬ (¬∀z (β) v ∃y (¬ α))

→ ¬∃x (∀z (β) v ∀y (α))

Hence, ∀x (∀z (β) → ∃y (¬ α)) is equivalent to ¬ ∃x (∀ y (α) ∧ ∀ z(β)).

Option 3:

∀x (∀y (α) → ∃z (¬ β))

→ ∀x (¬∀y (α) v ∃z (¬ β))

→ ¬∃x¬ (¬∀y (α) v ∃z (¬ β))

→ ¬∃x (∀y (α) ^ ∀z (β))

Hence, ∀x (∀y (α) → ∃z (¬ β)) is equivalent to ¬ ∃x (∀ y (α) ∧ ∀ z(β)).

Option 4:

∀x (∃y (¬ α) → ∃z (¬ β))

→ ∀x (¬∃y (¬ α) v ∃z (¬ β))

→ ∀x (∀y (α) v ∃z (¬ β))

→ ¬∃x¬ (∀y (α) v ∃z (¬ β))

→ ¬∃x (¬∀y (α) ∧ ¬∃z (¬ β))

→ ¬∃x (¬∀y (α) ∧ ∀z (β))

Hence, ∀x (∃y (¬ α) → ∃z (¬ β)) is not equivalent to ¬ ∃x (∀ y (α) ∧ ∀ z(β)).

Hence, the correct answer is "option 1 and 4".

NOTE:

Marks are given to all for this question in the official GATE CS 2013

The correct answer is “option 2”.

EXPLANATION:

Value d & c of statements d = c*a & e = c +a are not used anywhere.

So, by applying code motion optimization these statements can be moved to else section.

 

Hence, the total number of spills to memory is 1.

The correct answer is “option 2”.

EXPLANATION:

 

Hence, total number of registers required is 4.

The correct answer is “option 2”.

EXPLANATION:

From the given flawed procedure:

void find_and_replace (char *A, char *oldc, char *newc) {

for (int i=0; i<5; i++)

for (int j=0; j<3; j++)

if (A[i] == oldc[j]) A[i] = newc[j];

}

The following procedure is tested:

(1) oldc = “abc”, newc = “dab”

(2) oldc = “cde”, newc = “bcd”

(3) oldc = “bca”, newc = “cda”

(4) oldc = “abc”, newc = “bac”

First procedure: oldc = “abc”, newc = “dab”

1. A[i=0] == a & oldc[j=0] == a, replace with value newc[j=0] = d.
2. A[i=1] == a & oldc[j=1] == b, replace with value newc[j=1] = a.
3. A[i=2] == a & oldc[j=2] == c, replace with value newc[j=2] = c.

Second procedure: oldc = “cde”, newc = “bcd”

1. A[i=2] == c & oldc[j=0] == c, replace with value newc[j=0] = b.
2. A[i=3] == d & oldc[j=1] == d, replace with value newc[j=1] = c.
3. A[i=4] == e & oldc[j=1] == e, replace with value newc[j=2] = d.

Third procedure: oldc = “bca”, newc = “cda”

1. A[i=1] == b & oldc[j=0] == b, replace with value newc[j=0] = c.

2. A[i=1] == c & oldc[j=1] == c, replace with value newc[j=1] = d.  {first flaw} 3. A[i=2] == c & oldc[j=1] == c, replace with value newc[j=1] = d.

Fourth procedure: oldc = “abc”, newc = “bac”

1. A[i=0] == a & oldc[j=0] == a, replace with value newc[j=0] = b.

2. A[i=0] == b & oldc[j=1] == b, replace with value newc[j=1] = a.  {second flaw} 3. A[i=1] == b & oldc[j=1] == b, replace with value newc[j=1] = a.

Updating newc value with another newc value is known as flaw here.

So, there are 2 flaws here.

Hence, the correct answer is “option 2”.

The correct answer is “option 2”.

EXPLANATION:

From the given flawed procedure:

void find_and_replace (char *A, char *oldc, char *newc) {

for (int i=0; i<5; i++)

for (int j=0; j<3; j++)

if (A[i] == oldc[j]) A[i] = newc[j];

}

The following procedure is tested:

(1) oldc = “abc”, newc = “dab”

(2) oldc = “cde”, newc = “bcd”

(3) oldc = “bca”, newc = “cda”

(4) oldc = “abc”, newc = “bac”

First procedure: oldc = “abc”, newc = “dab”

1. A[i=0] == a & oldc[j=0] == a, replace with value newc[j=0] = d.
2. A[i=1] == a & oldc[j=1] == b, replace with value newc[j=1] = a.
3. A[i=2] == a & oldc[j=2] == c, replace with value newc[j=2] = c.

Second procedure: oldc = “cde”, newc = “bcd”

1. A[i=2] == c & oldc[j=0] == c, replace with value newc[j=0] = b.
2. A[i=3] == d & oldc[j=1] == d, replace with value newc[j=1] = c.
3. A[i=4] == e & oldc[j=1] == e, replace with value newc[j=2] = d.

Third procedure: oldc = “bca”, newc = “cda”

1. A[i=1] == b & oldc[j=0] == b, replace with value newc[j=0] = c.
2. A[i=1] == c & oldc[j=1] == c, replace with value newc[j=1] = d.  {first flaw}
3. A[i=2] == c & oldc[j=1] == c, replace with value newc[j=1] = d.

Fourth procedure: oldc = “abc”, newc = “bac”

1. A[i=0] == a & oldc[j=0] == a, replace with value newc[j=0] = b.
2. A[i=0] == b & oldc[j=1] == b, replace with value newc[j=1] = a.  {second flaw}
3. A[i=1] == b & oldc[j=1] == b, replace with value newc[j=1] = a.

Updating newc value with another newc value is known as a flaw here. 

So, there are 2 flaws here.

The third & fourth procedures are producing flaws while the first & second procedures work fine.

Hence, the correct answer is “option 3”.

The correct answer is “option 3”.

CONCEPT:

To minimize the need for contiguous allocation of physical memory, paging is used.

Logical address space or virtual address space is the set of all logical addresses generated by the program.

Physical addresses are the actual addresses available in memory.

Physical address space is the set of all physical addresses generated by the program.

Mapping of the virtual address to physical address is done by hardware device i.e. Memory Management Unit (MMU) & is called paging technique.

Physical Address space is divided into fixed-size no. of blocks called frames.

The logical address space is divided into fixed-size no. of blocks called pages.

CALCULATION:

Page table entry size = 32 bits or 4 Bytes

No. of entries in one page = \(\frac{2^p }{4}\)

VAS = 46 bits

Consider size of page = 2^p Bytes

Virtual address space (VAS) = No. of entries x page size

No. of entries for one level Page table (PT) = 2^p ×4

Therefore, for 3 levels PT = \(\frac{2^p }{4}\) × \(\frac{2^p }{4}\) × \(\frac{2^p }{4}\)

VAS = \(\frac{2^p }{4}\) × \(\frac{2^p }{4}\) × \(\frac{2^p }{4}\) × 2^p

2⁴⁶ x 2⁶ = 2^4p

2⁵² = 2^4p

52 = 4p

P = 13

So, the page size is 2¹³ or 8KB.

Hence, the correct answer is “option 3”.

The correct answer is “option 3”.

CONCEPT:

Cache memory is the faster, smaller size memory used for faster access of the data.

It acts as a buffer between RAM and CPU.

It mainly holds frequently accessed data & instructions that are immediately available to the CPU.

The cache is divided into cache blocks or cache lines.

The fields of cache are Tag, Index & Offset.

Cache address can be specified by only index & offset.

Tag is used to allowing the cache to translate from cache address to unique CPU address.

A cache that is n-way set associative then cache addresses (index & offset) specifies n cache blocks.

To minimize the need for contiguous allocation of physical memory, paging is used.

Physical Address space is divided into fixed-size no. of blocks called frames.

The logical address space is divided into fixed-size no. of blocks called pages.

Logical address space or virtual address space is the set of all logical addresses generated by the program.

Physical addresses are the actual addresses available in memory.

Physical address space is the set of all physical addresses generated by the program.

CALCULATION:

The processor has a 1 MB 16-way set associative cache,

Cache block size = 64 bytes or 2⁶

So, block offset = 6 bits

No. of sets in cache –

No of blocks in cache = 2^20 / 2^6 = 2^14

No. of sets = \(\frac{2^{14} }{2^4 }\)= 2¹⁰

So, Set bits = 10 bits

Therefore tag bits = VA – (set + offset)

= 46 – (10+6)

= 30 bits

For indexing, 16 bits are used.

Also, the page size is 8KB or 13bits so out of 16 bits, these 13 bits can’t be translated during VA to PA. (Since used for indexing purpose)

So, (16-13) i.e. 3 bits can produce 2³ i.e. 8 combinations which can be mapped on different sets.

Hence, 8 different colors are needed to color pages.

The correct answer is “option 2”.

CONCEPT:

A set of attributes that uniquely identify tuples in a table is called the Candidate key.

It is a super key with no repeated attributes.

A table can have multiple candidate keys but only one primary key.

The primary key can be selected from the candidate keys.

Candidate keys may have multiple attributes.

A functional dependency is a relationship or dependency that exists between two attributes.

Closure means the complete set of all possible attributes that can be functionally derived from the functional dependencies.

Closure of C is denoted by C+.

EXPLANATION

According to the given dependencies,

CH → G

A → BC

B → CFH

E → A

F → EG

Since D is not part of any functional dependency so it can be a candidate key or maybe part of a candidate key.

To find more candidate keys add A, B, C, D, E, G, and H to D & find its closure:

(AD)⁺ = {ABCDEFGH}

(BD)⁺ = {ABCDEFGH}

(CD)⁺ = {CD}

(ED)⁺ = {ABCDEFGH}

(FD)⁺ = {ABCDEFGH}

(GD)⁺ = {GD}

(HD)⁺ = {HD}

Since AD, BD, ED and FD gives all attributes, so they are candidate keys.

Hence, the correct answer is “option 2”.

The correct answer is “option 2”.

CONCEPT:

A set of attributes that uniquely identify tuples in a table is called the Candidate key.

Candidate keys may have multiple attributes.

A functional dependency is a relationship or dependency that exists between two attributes.

Closure means the complete set of all possible attributes that can be functionally derived from the functional dependencies.

Normalization is used to minimize redundancy from a set of relations.

It is used to organize data effectively in the database.

Normal forms are used to reduce redundancy from the database.

 

EXPLANATION

According to the given dependencies,

CH → G

A → BC

B → CFH

E → A

F → EG

Since D is not part of any functional dependency so it can be a candidate key or maybe part of a candidate key.

To find more candidate keys add A, B, C, D, E, G, and H to D & find its closure:

(AD)⁺ = {ABCDEFGH}

(BD)⁺ = {ABCDEFGH}

(CD)⁺ = {CD}

(ED)⁺ = {ABCDEFGH}

(FD)⁺ = {ABCDEFGH}

(GD)⁺ = {GD}

(HD)⁺ = {HD}

Since AD, BD, ED & FD gives all attributes, so they are candidate keys.

But the dependencies,

A → BC, B → CFH, and F → EG are partial dependencies.

{Here C, G, H are non-key attributes.}

Hence, the given relation is in 1NF but not in 2NF.