Official Paper

GATE CS 2014 Official Paper: Shift 2 (Previous Year Paper)

65 questions · 180 minutes · with answers · free

Attempt as Timed Mock Test

General Aptitude (10 questions)

Choose the most appropriate phrase from the options given below to complete the following sentence.

India is a post-colonial country because

((a))
it was a former British colony
((b))
Indian Information Technology professionals have colonized the world
((c))
India does not follow any colonial practices
((d))
India has helped other countries gain freedom

Show Answer

Answer: ((a))

it was a former British colony

The correct answer is Option 1 i.e. it was a former British colony.

Key Points

The sentence given above ends with 'because' and we know that 'because' is a subordinating conjunction. It shows the cause, a conjunction connects two sentences or phrases. As per the context of the first phrase, the second phrase must be a cause. A country is called postcolonial if it came into existence after the colonies of the British and the Europeans were abolished and the countries then under their rule were declared independent.

India was under the British colonial rule till 1947, i.e. it was a former British colony and thus is called a postcolonial country. All the other options do not seem to be a valid cause, Option 2 is an independent statement, whereas other options are irrelevant.

So, the** complete sentence will be**- India is a post-colonial country because it was a former British colony.

Who ___________ was coming to see us this evening?

((a))
you said
((b))
did you say
((c))
did you say that
((d))
had you said

Show Answer

Answer: ((b))

did you say

The correct answer is Option 2) i.e. did you say

We usually form wh-questions with wh- + an auxiliary verb (be, do or have) + subject + main verb or with wh- + a modal verb + subject + main verb. For eg- When are you leaving?

Among all the options, Option 2 is the appropriate choice as it concurs with the context of the sentence.

Option 1 is incorrect because the auxiliary verb is missing.
Option 3 is incorrect because 'that' doesn't fit as per the context of the sentence.
Option 4 is incorrect because we need simple past tense, and in the given option past perfect has been used.

Match the columns.

	Column 1		Column 2
1	Eradicate	P	Misrepresent
2	Distort	Q	Soak completely
3	Saturate	R	Use
4	Utilize	S	Destroy utterly

((a))
1 : S, 2 : P, 3 : Q, 4 : R
((b))
1 : P, 2 : Q, 3 : R, 4 : S
((c))
1 : Q, 2 : R, 3 : S, 4 : P
((d))
1 : S, 2 : P, 3 : R, 4 : Q

Show Answer

Answer: ((a))

1 : S, 2 : P, 3 : Q, 4 : R

The correct answer is Option 1) i.e. 1 : S, 2 : P, 3 : Q, 4 : R

Eradicate	Destroy utterly
Distort	Misrepresent
Saturate	Soak completely
Utilize	Use

What is the average of all multiples of 10 from 2 to 198?

((a))
90
((b))
100
((c))
110
((d))
120

Show Answer

Answer: ((b))

100

Data:

Range: 2 to 198

Multiples of 10 are 10, 20, 30 ..... 190

Since the numbers are in Arithmetic progression:

First term = a = 10,

Last term = tn= 190

Difference = d = 20 - 10 = 10

number of terms = n

Sum = S_n

Formula:

tn = a + (n - 1)d

Sn = $\frac{n(a + t_n)}{2}$

Calculation:

190 = 10 + (n - 1) 10

n = 19

Sn = $\frac{19(10 + 190)}{2} = 1900$

Average = $\frac{1900}{19} = 100$

Tips and Tricks:

$Average = \frac{a + t_n}{2} = \frac{10 + 190}{2} = 100$

The value of $\sqrt {12 + \sqrt {12 + \sqrt {12 + \ldots } } }$ is

((a))
3.464
((b))
3.932
((c))
4.000
((d))
4.444

Show Answer

Answer: ((c))

4.000

Let y = $\sqrt {12 + \sqrt {12 + \sqrt {12 + \ldots } } }$

∴ y = $\sqrt {12 +y }$

Squaring on both sides

y² = 12 + y

y² - y - 12 = 0

y2 - 4y + 3y - 12 = 0

y(y - 4) + 3(y - 4) = 0

(y - 4)(y + 3) = 0

∴ y = 4 or y = -3

The value of $\sqrt {12 + \sqrt {12 + \sqrt {12 + \ldots } } }$ is 4.000

The old city of Koenigsberg, which had a German majority population before World War 2, is now called Kaliningrad. After the events of the war, Kaliningrad is now a Russian territory and has a Predominantly Russian population. It is bordered by the Baltic Sea on the north and the countries of Poland to the south and west and Lithuania to the east respectively.

Which of the statements below can be inferred from this passage?

((a))
Kaliningrad was historically Russian in its ethnic make up
((b))
Kaliningrad is a part of Russia despite it not being contiguous with the rest of Russia
((c))
Koenigsberg was renamed Kaliningrad, as that was its original Russian name
((d))
Poland and Lithuania are on the route from Kaliningrad to the rest of Russia

Show Answer

Answer: ((b))

Kaliningrad is a part of Russia despite it not being contiguous with the rest of Russia

The correct answer is Option 2 i.e Kaliningrad is a part of Russia despite it not being contiguous with the rest of Russia

Explanation

From the passage, we find that:

Koenigsberg became Russian Kaliningrad after the war.
It had a German majority population before the war.
Poland is in its South and West and Lithuania to the east.

From the above points, we find that

Option 1 is wrong as Kaliningrad was historically German with the German population.
Option 2 concurs perfectly to the above points and is the correct answer.
Option 3 is wrong as Kaliningrad was not the original name as it was Koenigsberg.
Option 4 is wrong as Poland and Lithuania are on two different sides of the city.

Hence we find that Option 2 is the only correct option, and therefore the correct answer.

The number of people diagnosed with dengue fever (contracted from the bite of a mosquito) in north India is twice the number diagnosed last year. Municipal authorities have concluded that measures to control the mosquito population have failed in this region.

Which one of the following statements, if true, does not contradict this conclusion?

((a))
A high proportion of the affected population has returned from neighbouring countries where dengue is prevalent
((b))
More cases of dengue are now reported because of an increase in the Municipal Office’s administrative efficiency
((c))
Many more cases of dengue are being diagnosed this year since the introduction of a new and effective diagnostic test
((d))
The number of people with malarial fever (also contracted from mosquito bites) has increased this year

Show Answer

Answer: ((d))

The number of people with malarial fever (also contracted from mosquito bites) has increased this year

The correct answer is option 4 i.e. the number of people with malarial fever (also contracted from mosquito bites) has increased this year

Explanation

Option 4 is the correct answer, as it states both Dengue fever and malarial fever is caused by Mosquito bite; dengue fever had increased because of some other reasons which are not mentioned by the municipal authorities. Since Municipal authorities have concluded that measures to control the mosquito population have failed in this region so as its consequences we can easily say "The number of people with malarial fever (also contracted from mosquito bites) has increased this year"

Let’s see the given points-

Statement (1) negates or contradicts the conclusion of the municipal authorities, as it concluded that measures taken to control the mosquito population had failed; Hence 1st option is incorrect.
As there is no data mentioned in the passage related to the reporting of cases and the efficiency of the administrative capabilities; it concludes that the 2nd option is also incorrect
Statement 3rd also contradicts the conclusion of the municipal authorities mentioned in the paragraph; hence this option will be incorrect.

If x is real and |𝑥² − 2𝑥 + 3| = 11, then possible values of | − 𝑥³ + 𝑥² − 𝑥| include

((a))
2, 4
((b))
2, 14
((c))
4, 52
((d))
14, 52

Show Answer

Answer: ((d))

14, 52

|𝑥2 − 2𝑥 + 3| = 11

𝑥2 − 2𝑥 + 3 = 11 or 𝑥2 − 2𝑥 + 3 = -11

By taking:

𝑥2 − 2𝑥 + 3 = 11

𝑥2 − 2𝑥 − 8 = 0

𝑥2 − 4𝑥 + 2𝑥 − 8 = 0

𝑥(𝑥 - 4) + 2(𝑥 − 4) = 0

(𝑥 + 2)(𝑥 − 4) = 0

𝑥 = −2 or 𝑥 = 4

Substitute: 𝑥 = -2

|− 𝑥3 + 𝑥2 − 𝑥| = | − (−2)3 + (−2)2 − (−2)| = |14 | = 14

Substitute: 𝑥 = 4

|− 𝑥3 + 𝑥2 − 𝑥| = | − 43 + 42 − 4| = |-52 | = 52

The possible values of | − 𝑥3 + 𝑥2 − 𝑥| include 14 and 52

The ratio of male to female students in a college for five years is plotted in the following line graph.

If the number of female students doubled in 2009, by what percent did the number of male students increase in 2009?

At what time between 6 a.m. and 7 a.m. will the minute hand and hour hand of a clock make an angle closest to 60°?

((a))
6 : 22 a.m
((b))
6 : 27 a.m.
((c))
6 : 38 a.m
((d))
6 : 45 a.m

Show Answer

Answer: ((a))

6 : 22 a.m

1 Rotation of clock consists of 360^o

In 1 hour, minute hand covers 360^o

60 minutes → 360^o

1 minute → 6o

Therefore, the minute hand covers 6o in 1 minute.

In 12 hour, hours hand covers 360o

1 hour → 30o

60 minutes → 30o

1 minute → 0.50

Therefore, the hour hand covers 0.5^o in 1 minute.

Option 1:

22 minutes will move 110 of an hour hand

2 minutes will move 120 of a minutes hand

Angle covered:

(4 to 5) + (5 to 6) + (6 to 7)

(30 - 2× 6)o + 30o + (22 × 0.5)o

18o + 30o + 11⁰ = 59o

This is closest to 60o

Computer Science and Information Technology (55 questions)

The security system at an IT office is composed of 10 computers of which exactly four are working. To check whether the system is functional, the officials inspect four of the computers picked at random (without replacement). The system is deemed functional if at least three of the four computers inspected are working. Let the probability that the system is deemed functional be denoted by p. Then 100p = _____________.

Each of the nine words in the sentence”. The quick brown fox jumps over the lazy dog” is written on a separate piece of paper. These nine pieces of paper are kept in a box. One of the pieces is drawn at random from the box. The expected length of the word drawn is ______. (The answer should be rounded to one decimal place.)

The maximum number of edges in a bipartite graph on 12 vertices is ________

If the matrix A is such that

$A = \left[ {\begin{array}{*{20}{c}} 2\ { - 4}\ 7 \end{array}} \right]\left[ {1;;;9;;;5} \right]$

Then the determinant of A is equal to ____

A non-zero polynomial f(x) of degree 3 has roots at x = 1, x = 2 and x = 3. Which one of the following must be TRUE?

((a))
f(0) f(4) < 0
((b))
f(0) f(4) > 0
((c))
f(0) + f(4) > 0
((d))
f(0) + f(4) < 0

Show Answer

Answer: ((a))

f(0) f(4) < 0

Concept:

Concept:

If root of the function are a, b and c

then Polynomial function f(x) = (x - a)(x - b)(x - c)

Explanation:

Three roots are 1, 2 and 3

f(x) = (x - 1)(x - 2)(x - 3)

f(0) = -1 × -2 × -3 = -6

f(4) = 3 × 2 × 1 = 6

∴ f(0)× (4) = -6 × 6 = -36

Hence f(0) f(4) < 0

The dual of a Boolean function F(x₁, x₂, … , x_n, +, ∙ , ′), written as F^D, is the same expression as that of F with + and ⋅ swapped. F is said to be self-dual if F = F^D. The number of self-dual functions with n Boolean variables is

((a))
2ⁿ
((b))
2^n-1
((c))
${2^{{2^n}}}$
((d))
${2^{{2^{n - 1}}}}$

Show Answer

Answer: ((d))

${2^{{2^{n - 1}}}}$

Concept:

Self dual functions properties:

Number of min terms equal to number of max terms.

Function should not contain both min term pairs which are complement to each other.

Explanation:

Decimal	A	B	C
0	0	0	0
1	0	0	1
2	0	1	0
3	0	1	1
4	1	0	0
5	1	0	1
6	1	1	0
7	1	1	1

So here (0, 7), (1, 6), (2, 5), (3, 4) are complement to each other so in self dual function we will choose one of them not both so in this case total self dual function is 2 × 2 × 2 × 2 = 16

option 4:

${2^{{2^{n - 1}}}} = {2^{{2^{3 - 1}}}} = 16$

Hence option 4 is correct

Alternate Method

Total min terms possible with n variable are 2ⁿ but we have to select half of them.

Total self-dual functions:

Total function possible = ${2^{{2^{n - 1}}}}$

Let k = 2ⁿ. A circuit is built by giving the output of an n-bit binary counter as input to an n-to-2ⁿ bit decoder. This circuit is equivalent to a

((a))
k-bit binary up counter
((b))
k-bit binary down counter
((c))
k-bit ring counter
((d))
k-bit Johnson counter

Show Answer

Answer: ((c))

k-bit ring counter

Let’s take small example: 2-bit binary counter and 2 × 4 decoder

2 bit binary counter output: 00, 01, 10, and 11. These outputs are inputs for decoder.

Decoder input	Decoder output
00	1000 (Line 1 will be activated and all other will be deactivated)
01	0100 (Line 2 will be activated and all other will be deactivated)
10	0010 (Line 3 will be activated and all other will be deactivated)
11	0001 (Line 4 will be activated and all other will be deactivated)

Decoder output is similar to 2ⁿring counter here n is 2 so 4 ring counter outputs:

State	Q0	Q1	Q2	Q3
0	1	0	0	0
1	0	1	0	0
2	0	0	1	0
3	0	0	0	1
0	1	0	0	0
1	0	1	0	0
2	0	0	1	0
3	0	0	0	1

Johnson counter counts 2k states but ring counter counts k states.

Hence k bit ring counter is the correct answer.

Consider the equation (123)₅ = (x8)_y with x and y as unknown. The number of possible solutions is _____ .

A 4-way set-associative cache memory unit with a capacity of 16 KB is built using a block size of 8 words. The word length is 32 bits. The size of the physical address space is 4 GB. The number of bits for the TAG field is _____

Consider the function func shown below:

int func(int num) {

int count = 0;

while (num) {

count++;

num >>= 1;

}

return (count);

}

The value returned by func(435)is __________.

Suppose n and p are unsigned int variables in a C program. We wish to set p to ⁿC₃. If n is large, which one of the following statements is most likely to set p correctly?

((a))
p = n * (n-1) * (n-2) / 6;
((b))
p = n * (n-1) / 2 * (n-2) / 3;
((c))
p = n * (n-1) / 3 * (n-2) / 2;
((d))
p = n * (n-1) * (n-2) / 6.0;

Show Answer

Answer: ((b))

p = n * (n-1) / 2 * (n-2) / 3;

Concept:

and / have the same precedence but they are left associative.

Explanation:

${\rm{P}} = \frac{{{\rm{n}}!}}{{\left( {{\rm{n}} - 3} \right)!{\rm{;}} × {\rm{;}}3!}} = \frac{{{\rm{n;}} × {\rm{;}}\left( {{\rm{n}} - 1} \right){\rm{;}} × {\rm{;}}\left( {{\rm{n}} - 2} \right)}}{{3!}},{\rm{;in;question;given;that;p;is;unsigned;integer;}}$

Option 1 and 4:

According to rule of associatively n × (n - 1) (n - 2) will calculate first. Given that n is large

this value cannot fit in unsigned int p range so option 1 and 4 are wrong.

Option 3:

According to rule of associatively n × (n - 1) will calculate first and divides with 3 may not get integer value always so data can be lost, this option is also wrong.

Option 2:

According to rule of associatively n × (n - 1) will calculate first and divides with 2 will always gives integer and multiply with (n - 2) and divides with 3 will always get integer value hence no data loss.

Hence option 2 is the correct answer.

A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The level-order traversal of the heap after the insertion of the elements is:

((a))
10, 8, 7, 3, 2, 1, 5
((b))
10, 8, 7, 2, 3, 1, 5
((c))
10, 8, 7, 1, 2, 3, 5
((d))
10, 8, 7, 5, 3, 2, 1

Show Answer

Answer: ((a))

10, 8, 7, 3, 2, 1, 5

Concept:

Max heap: Root node value should be greater than child nodes.

Whenever we insert new element in heap, we will insert at the last level of heap.

After inserting element if max heap doesn’t follow the property then we will apply heapify algorithm until we get max heap.

Explanation:

Initial Heap

After inserting 1:

After inserting 7:

It doesn’t follow max heap property because 7 is greater than 5 so we will apply heapify algorithm on node 7.

After applied heapify algorithm:

Level order: 10, 8, 7, 3, 2, 1, 5

Hence option 1 is the correct answer.

Which one of the following correctly determines the solution of the recurrence relation with

T(1) = 1?

$T\left( n \right) = 2T\left( {\frac{n}{2}} \right) + \log n$

((a))
Θ(n)
((b))
Θ(n log n)
((c))
Θ (n²)
((d))
Θ(log n)

Show Answer

Answer: ((a))

Θ(n)

${\rm{T}}\left( {\rm{n}} \right) = 2{\rm{T}}\left( {\frac{{\rm{n}}}{2}} \right) + \log {\rm{n}}$

Comparing with:

${\rm{T}}\left( {\rm{n}} \right) = {\rm{aT}}\left( {\frac{{\rm{n}}}{{\rm{b}}}} \right) + f\left( n \right)$

a = 2, b = 2, f(n) = log n

${n^{{{\log }_2}2}} = n$ > f(n)

By Master’s theorem

$T\left( {\rm{n}} \right) = {\rm{O}}\left( {\rm{n}} \right)$

Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing

((a))
the shortest path between every pair of vertices
((b))
the shortest path from W to every vertex in the graph
((c))
the shortest paths from W to only those nodes that are leaves of T.
((d))
the longest path in the graph.

Show Answer

Answer: ((b))

the shortest path from W to every vertex in the graph

Concept:

BFS doesn’t calculate shortest path between every pair.

BFS computes shortest path between source vertex (w) to every vertex in the graph.

BFS doesn’t calculate shortest path between any two vertices.

Example:

After applying BFS on vertex A:

We can see that shortest distance between B and C is 1 but after applying BFS distance between B and C is 2.

Hence option 2 is the correct answer.

If L₁ = {aⁿ|n ≥ 0} and L₂ = {bⁿ|n ≥ 0}, consider

(I) L₁⋅L₂ is a regular language

(II) L₁⋅L₂ = {aⁿbⁿ|n ≥ 0}

Which one of the following is CORRECT?

((a))
Only (I)
((b))
Only (II)
((c))
Both (I) and (II)
((d))
Neither (I) nor (II)

Show Answer

Answer: ((a))

Only (I)

Concept:

Regular languages are closed under concatenation

Explanation:

L₁ = {aⁿ|n ≥ 0}

L₁ = {ϵ , a, aa, aaa, aaaa, aaaaa, ….}

L₁ = a^*

Therefore, L₁ is a regular language

L₂ = {bⁿ|n ≥ 0}

L₂ = {ϵ, b, bb, bbb, , aaaaa, ….}

L₂ = {bⁿ|n ≥ 0}

Therefore, L₂ is a regular language

L₁⋅L₂ = {ϵ, a, b, aa, bb, ab, ba, … }

L₁⋅L₂ = a^{.b}

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

Statement I: CORRECT

Therefore L₁⋅L₂ is a regular language.

Statement II: INCORRECT

L₁⋅L₂ = {aⁿbⁿ|n ≥ 0}

It doesn’t accept string: {a, b, aa, bb ….}

Hence L₁⋅L₂ ≠ {aⁿbⁿ|n ≥ 0}

Let A ≤_m B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?

((a))
If A ≤_m B and B is recursive then A is recursive
((b))
If A ≤_m B and A is undecidable then B is undecidable.
((c))
If A ≤_m B and B is recursively enumerable then A is recursively enumerable
((d))
If A ≤_m B and B is not recursively enumerable then A is not recursively enumerable

Show Answer

Answer: ((d))

If A ≤_m B and B is not recursively enumerable then A is not recursively enumerable

Concept:

Theorem 1:

If A ≤_m B then:

If B is recursively enumerable then A is recursively enumerable.

If B is recursive then A is recursive.

Theorem 2:

If A ≤_m B then:

If A is not recursively enumerable then B is not recursively enumerable.

If A is not recursive then B is not recursive.

If A is undecidable then B is undecidable.

Hence option 4 is the correct answer and false statement.

Consider the grammar defined by the following production rules, with two operators ∗ and +

S → T * P

T → U|T * U

P → Q + P|Q

Q → Id

U → Id

Which one of the following is TRUE?

((a))
- is left associative, while ∗ is right associative
((b))
- is right associative, while ∗ is left associative
((c))
Both + and ∗ are right associative
((d))
Both + and ∗ are left associative

Show Answer

Answer: ((b))

is right associative, while ∗ is left associative

In second production T → T * U here T is generating T*U left recursively so * is left associative.

In third production P → Q + P, Here P is generating Q + P right recursively so + is right associative.

Hence option 2 is the correct answer.

Which one of the following is NOT performed during compilation?

((a))
Dynamic memory allocation
((b))
Type checking
((c))
Symbol table management
((d))
Inline expansion

Show Answer

Answer: ((a))

Dynamic memory allocation

Dynamic Memory Allocation:

Performed during run time when a program executing and require a memory block.

Type Checking:

Check performed during the semantic analysis of compilation.

Symbol Table:

Management is to store and retrieve the information about tokens during compilation phase.

Inline Expansion:

Type of macro in pre-processor which happens before even compilation started.

Replace a function call by the body of respective function.

Hence option 1 is the correct answer.

Which one of the following is TRUE?

((a))
The requirements document also describes how the requirements that are listed in the document are implemented efficiently
((b))
Consistency and completeness of functional requirements are always achieved in practice.
((c))
Prototyping is a method of requirements validation
((d))
Requirements review is carried out to find the errors in system design

Show Answer

Answer: ((c))

Prototyping is a method of requirements validation

Concept:

Prototyping is a method of requirements validation (Have we got the requirements, right?)

There are some more requirements validation methods:

Test case generation
Automated consistency analysis

Requirements review determines whether the requirements are essential to design the system.

Hence option 3 is the correct answer.

A FAT (file allocation table) based file system is being used and the total overhead of each entry in the FAT is 4 bytes in size. Given a 100 x 10⁶ bytes disk on which the file system is stored and data

block size is 10³ bytes, the maximum size of a file that can be stored on this disk in units of 10⁶ bytes is ______

The maximum number of superkeys for the relation schema R(E, F,G,H) with E as the key is _____

Given an instance of the STUDENTS relation as shown below:

StudentID	StudentName	StudentEmail	StudentAge	CPI
2345	Shankar	shankar@math	X	9.4
1287	Swati	swati@ee	19	9.5
7853	Shankar	shankar@cse	19	9.4
9876	Swati	swati@mech	18	9.3
8765	Ganesh	ganesh@civil	19	8.7

For (StudentName, StudentAge) to be a key for this instance, the value X should NOT be equal to _______

Which one of the following is TRUE about the interior gateway routing protocols – Routing Information Protocol (RIP) and Open Shortest Path First (OSPF)

((a))
RIP uses distance vector routing and OSPF uses link state routing
((b))
OSPF uses distance vector routing and RIP uses link state routing
((c))
Both RIP and OSPF use link state routing
((d))
Both RIP and OSPF use distance vector routing

Show Answer

Answer: ((a))

RIP uses distance vector routing and OSPF uses link state routing

Routing Information Protocol (RIP) and Open Shortest Path First (OSPF) are Interior Gateway Protocol, i.e., they both are used within an autonomous system.
RIP is an old protocol (not used anymore) based on distance vector routing. OSPF is based on Link State Routing. Therefore option 1 is correct

Important Point:

RIP is a dynamic routing protocol which uses hop count as a routing metric between source and destination. RIP uses the UDP protocol for transmission of data.
OSPF is a link state routing protocol which uses multicast address to find the best path between source and destination. As, TCP does not support multicasting. So, OSPF packets are not sent using TCP.

Which one of the following socket API functions converts an unconnected active TCP socket into a passive socket?

((a))
connect
((b))
bind
((c))
listen
((d))
accept

Show Answer

Answer: ((c))

listen

Connect:

Actively attempt to establish a connection so this system call is doing something so we can say that this is active

Bind:

Bind the IP address and port address to the SOCKET connection so this system call is doing something so we can say that this is active

Listen:

Shows the willingness to accept connections.

Listen system call just makes the machine wait for someone to send a SYN packet so it simply convert unconnected socket to passive socket

This system call is waiting for SYN packet so this system call not doing something so passive.

Accept:

Block the caller until a connection attempts arrives, it does something so active.

Hence listen is the correct answer.

In the diagram shown below, L1 is an Ethernet LAN and L2 is a Token-Ring LAN. An IP packet originates from sender S and traverses to R, as shown. The links within each ISP and across the two ISPs, are all point-to-point optical links. The initial value of the TTL field is 32. The maximum possible value of the TTL field when R receives the datagram is ______

Consider the store and forward packet switched network given below. Assume that the bandwidth of each link is 10⁶ bytes / sec. A user on host A sends a file of size 10³ bytes to host B through routers R1 and R2 in three different ways. In the first case a single packet containing the complete file is transmitted from A to B. In the second case, the file is split into 10 equal parts, and these packets are transmitted from A to B. In the third case, the file is split into 20 equal parts and these packets are sent from A to B. Each packet contains 100 bytes of header information along with the user data. Consider only transmission time and ignore processing, queuing and propagation delays. Also assume that there are no errors during transmission. Let T1, T2 and T3 be the times taken to transmit the file in the first, second and third case respectively. Which one of the following is CORRECT?

((a))
T1 < T2 < T3
((b))
T1 > T2 > T3
((c))
T2 = T3, T3 < T1
((d))
T1 = T3, T3 > T2

Show Answer

Answer: ((d))

T1 = T3, T3 > T2

Concept:

Using concept of pipelining:

For packet 1 we have to take $3 \times {T_t}$ (because 3 links are there ) for all subsequent packets there will be one ${{\rm{T}}_{\rm{t}}}$ time.

Data:

Packet size = 10³ bytes

Head size = 100 bytes

Formula:

${\rm{Transmisson;time;}}\left( {{\rm{;}}{{\rm{T}}_{{\rm{t;}}}}} \right) = \frac{{{\rm{Data}} + {\rm{Header}}}}{{{\rm{Bandwidth}}}}$

Explanation:

Case 1:

Number of packets = 1

${{\rm{T}}_{\rm{t}}} = \frac{{1000 + 100}}{{1000000}} = \frac{{1100}}{{1000}} = 1.1{\rm{ms}}$

${\rm{T}}1 = 3 \times {{\rm{T}}_{\rm{t}}} = 3.3{\rm{ms}}$

Case 2:

Number of packets = 10

Size of one packet = $\frac{{1000}}{{10}} = 100;bytes$

${{\rm{T}}_{\rm{t}}} = \frac{{100 + 100}}{{1000000}} = \frac{{200}}{{1000}} = 0.2{\rm{ms}}$

${\rm{T}}2 = 3 \times 0.2{\rm{;}} + 0.2 \times 9 \times 1 = 2.4{\rm{;ms}}$

Case 3:

Number of packets = 20

Size of one packet = $\frac{{1000}}{{20}} = 50;bytes$

${{\rm{T}}_{\rm{t}}} = \frac{{50 + 100}}{{1000000}} = \frac{{150}}{{1000}} = 0.15{\rm{ms}}$

${\rm{T}}3 = 3 \times 0.15{\rm{;}} + 0.15 \times 19 \times 1 = 3.3{\rm{;ms}}$

So T1 = T3, T3 > T2 is the correct answer.

An IP machine Q has a path to another IP machine H via three IP routers R1, R2, and R3.

Q—R1—R2—R3—H

H acts as an HTTP server, and Q connects to H via HTTP and downloads a file. Session layer Encryption is used, with DES as the shared key encryption protocol. Consider the following four

Pieces of information:

[I1] The URL of the file downloaded by Q

[I2] The TCP port numbers at Q and H

[I3] The IP addresses of Q and H

[I4] The link layer addresses of Q and H

Which of I1, I2, I3, and I4 can an intruder learn through sniffing at R2 alone?

((a))
Only I1 and I2
((b))
Only I1
((c))
Only I2 and I3
((d))
Only I3 and I4

Show Answer

Answer: ((c))

Only I2 and I3

Explanation:

ü At router R2 only R1 and R3 link address is available so intruder can’t see the link address of Q and H.

ü At Session layer URL is very well encrypted by DES so intruder can’t see the URL address.

ü At Network layer header contains source as well as destination IP address so intruder can easily see at Router R2.

ü TCP port number of source and destination are present in TCP header so intruder can easily see at Router R2.

Hence option 3 is the correct answer.

A graphical HTML browser resident at a network client machine Q accesses a static HTML webpage from a HTTP server S. The static HTML page has exactly one static embedded image which is also at S. Assuming no caching, which one of the following is correct about the HTML webpage loading (including the embedded image)?

((a))
Q needs to send at least 2 HTTP requests to S, each necessarily in a separate TCP connection to server S
((b))
Q needs to send at least 2 HTTP requests to S, but a single TCP connection to server S is sufficient
((c))
A single HTTP request from Q to S is sufficient, and a single TCP connection between Q and S is necessary for this
((d))
A single HTTP request from Q to S is sufficient, and this is possible without any TCP connection between Q and S

Show Answer

Answer: ((b))

Q needs to send at least 2 HTTP requests to S, but a single TCP connection to server S is sufficient

Explanation:

Q makes a TCP connection with S
First request for the webpage when this request is received by S
Second request to S for picking up that image so at least 2 HTTP request are needed.
Above two request are done using HTTP version 1.1 ( HTTP persistent connection )
HTTP Persistent connection can make several requests on the same server.
Here TCP may close the TCP connection.
So at least 2 HTTP request are enough and 1 TCP connection is sufficient for desired goal.

Hence option 2 is the correct answer.

Consider the following schedule S of transactions T1, T2, T3, T4:

T1	T2	T3	T4
	Reads(X)
		Writes(X) Commit
Writes(X) Commit
	Writes(Y) Reads(Z) Commit
			Reads(X) Reads(Y) Commit

Which one of the following statements is CORRECT?

((a))
S is conflict-serializable but not recoverable
((b))
S is not conflict-serializable but is recoverable
((c))
S is both conflict-serializable and recoverable
((d))
S is neither conflict-serializable not is it recoverable

Show Answer

Answer: ((c))

S is both conflict-serializable and recoverable

Concept:

Using precedence graph method we can find out Schedule is conflict serializable or not.
If precedence graph has any loop then that schedule is going to be not conflict-serializable.
If precedence graph doesn’t have any loop then that schedule is going to be conflict-serializable.
If one transaction ( T1 )is writing some value x and that value is read by some other transaction(T2) then T1 should commit first then only T2 should read that value and commit in order to become recoverable schedule.

Explanation:

There is no loop in this graph so schedule is conflict serializable.
T2: T3: T1: T4 is the only serial schedule that is equivalent to given schedule. (Using Topological Sorting)
There are two write read dependency

T1 write(X) and T4 read (X)
T2 write (Y) and T4 read (Y)

In first case T1 is committed first then read by T4 then T4 is committed so this is recoverable.
In second case T2 is committed first then read by T4 then T4 is committed so this is also recoverable so schedule S is recoverable.

Hence option 3 is the correct answer.

Consider a join (relation algebra) between relations r(R)and s(S) using the nested loop method.

There are 3 buffers each of size equal to disk block size, out of which one buffer is reserved for

intermediate results. Assuming size(r(R))<size(s(S)), the join will have fewer number of disk block accesses if

((a))
relation r(R) is in the outer loop.
((b))
relation s(S) is in the outer loop.
((c))
join selection factor between r(R) and s(S) is more than 0.5.
((d))
join selection factor between r(R) and s(S) is less than 0.5.

Show Answer

Answer: ((a))

relation r(R) is in the outer loop.

Concept:

Nested loop join algorithm:

No of block transfers = n_rx b_s+ b_r

Where n_r is number of tuples in relation R and b_s and b_r are the number of blocks in relation R and S respectively.

Explanation :

In question it is given that size(r(R))<size(s(S)) this means b_s> b_r and n_r < n_s.

Example :

Suppose relation r is in the outer loop:

Suppose relation s is in the outer loop:

Block transfer = 100 x 10 + 20 = 1020

So relation r should be in the outer loop for effective nested loop join algorithm.

Hence option 1 is the correct answer.

Consider the procedure below for the Producer-Consumer problem which uses semaphores:

semaphore n = 0; semaphore s = 1; void producer() { while(true) { produce(); semWait(s); addToBuffer(); semSignal(s); semSignal(n); } }	void consumer() { while(true) { semWait(s); semWait(n); removeFromBuffer(); semSignal(s); consume(); } }

Which one of the following is TRUE?

((a))
The producer will be able to add an item to the buffer, but the consumer can never consume it.
((b))
The consumer will remove no more than one item from the buffer.
((c))
Deadlock occurs if the consumer succeeds in acquiring semaphore s when the buffer is empty.
((d))
The starting value for the semaphore n must be 1 and not 0 for deadlock-free operation.

Show Answer

Answer: ((c))

Deadlock occurs if the consumer succeeds in acquiring semaphore s when the buffer is empty.

Explanation:

semaphore n = 0; semaphore s = 1; void producer() { 1 while(true) 2 { 3 produce(); 4 semWait(s); 5 addToBuffer(); 6 semSignal(s); 7 semSignal(n); } }	void consumer() { 1 while(true) 2 { 3 semWait(s); 4 semWait(n); 5 removeFromBuffer(); 6 semSignal(s); 7 consume(); } }

Method 1

If consumer executes first and execute line number 1, 2, 3 and now after 3 it has been pre-empted and now producer start executing line number 1, 2 , 3 after line 3 producer will go into waiting because s is 0 it is decremented by consumer earlier, now we pre-empted producer.
Now again consumer start executing from line 4 but it cannot execute further because n=0 and it will for n to become 1, now we pre-empted consumer process.
Now we can see that both are waiting for each other, producer it waiting to become s=1 from

Consumer and consumer is waiting to become n=1 from producer.

This is nothing but deadlock.

Method 2:

Consumer: 1, 2 3 |producer 1,2, 3,4 (waiting for s to become 1)| consumer : 4 (waiting for n to become 1 ) So both are in waiting state so deadlock .

Hence option 3 is the correct answer.

Three processes A, B and C each execute a loop of 100 iterations. In each iteration of the loop, a process performs a single computation that requires t_c CPU milliseconds and then initiates a single I/O operation that lasts for t_io milliseconds. It is assumed that the computer where the processes execute has sufficient number of I/O devices and the OS of the computer assigns different I/O devices to each process. Also, the scheduling overhead of the OS is negligible. The processes have the following characteristics:

Process id	t_c	t_io
A	100 ms	500 ms
B	350 ms	500 ms
C	200 ms	500 ms

The processes A, B, and C are started at times 0, 5 and 10 milliseconds respectively, in a pure time sharing system (round robin scheduling) that uses a time slice of 50 milliseconds. The time in milliseconds at which process C would complete its first I/O operation is_______

A computer has twenty physical page frames which contain pages numbered 101 through 120. Now a program accesses the pages numbered 1, 2, …, 100 in that order, and repeats the access sequence THRICE. Which one of the following page replacement policies experiences the same number of page faults as the optimal page replacement policy for this program?

((a))
Least-recently-used
((b))
First-in-first-out
((c))
Last-in-first-out
((d))
Most-recently-used

Show Answer

Answer: ((d))

Most-recently-used

Explanation:

Optimal:

1 to 100 all are page faults(100)
20 to 99 all are page faults (80)
19 to 98 all are page faults(80)
18 to 97 all are page faults (80)

FIFO:

All are page faults so total 400 page faults are there.

LRU:

Same as FIFO so total 400 page faults are there.

Last in first out (LIFO):

In first sequence all 100 are page faults
In second sequence all 20 to 100 are page faults. (81)
In Third sequence all 20 to 100 are page faults. (81)
In forth sequence all 20 to 100 are page faults. (81)

Total 343 page faults.

Most recently used (MRU):

1 to 100 all are page faults(100)
20 to 99 all are page faults (80)
19 to 98 all are page faults(80)
18 to 97 all are page faults (80)
MRU has total 340 page faults.

Hence 4 is the correct answer.

For a C program accessing X[i][j][k], the following intermediate code is generated by a

Compiler. Assume that the size of an integer is 32 bits and the size of a character is 8 bits.

t0 = i ∗ 1024

t1 = j ∗ 32

t2 = k ∗ 4

t3 = t1 + t0

t4 = t3 + t2

t5 = X[t4]

Which one of the following statements about the source code for the C program is CORRECT?

((a))
X is declared as “int X[32][32][8]”.
((b))
X is declared as “int X[4][1024][32]”.
((c))
X is declared as “char X[4][32][8]”.
((d))
X is declared as “char X[32][16][2]”.

Show Answer

Answer: ((a))

X is declared as “int X[32][32][8]”.

Explanation:

t5 can be written as :

t5 = X[t4] = X[ t3 + t2 ] =X [ t1 + t0 + t2 ] =X[ i ∗ 1024 + j ∗ 32 + k ∗ 4]

t5 = X[ i ∗ 1024 + j ∗ 32 + k ∗ 4]

Option 1: Suppose we want to calculate address of X[1][1][1]

In order to reach X[1] we have to cross 32x8 integer each integer size is 4byte so t0 = i * 1024 (here i = 1 so t0 = 1024 ).
Now we are at X[1] but we want to go to X[1][1]we have to cross 8 integer element size of each element is 4B so t1 = j*32 ( here j = 1 so t1=32 )
Now we are at X[1][1] but we want to go to X[1][1][1] we have to cross 1 integer element size of each element is 4B so t2 = k*4 ( here k = 1 so t2 = 4 )

So option 1 is the correct answer.

Let < M > be the encoding of a Turing machine as a string over ∑ = {0, 1}. Let L = { < M > | M is a Turing machine that accepts a string of length 2014 }. Then, L is

((a))
decidable and recursively enumerable
((b))
undecidable but recursively enumerable
((c))
undecidable and not recursively enumerable
((d))
decidable but not recursively enumerable

Show Answer

Answer: ((b))

undecidable but recursively enumerable

Concept:

Recursive Enumerable (RE):

Using rice’s theorem we can find out whether the problem is decidable or undecidable.

Explanation:

There will be 2 cases for the string of length 2014:

Case 1: String is accepted by Turing machine.

Case 2: It will halt on non-final state or go on a loop.

This is nothing but definition of recursive enumerable.

Rice theorem 1: Any non-trivial property of L(TM) is undecidable.

Given problem is a non-trivial property as there are TM whose language contains such a string and there are TM whose language doesn’t have such a string so given problem is undecidable.

Let L₁ = {w ∈ {0, 1}|w has at least as many occurrences of (110)’s as (011)’s}. Let L₂ = {w ∈ {0, 1}|w has at least as many occurrences of (000)’s as (111)’s}. Which one of the following is TRUE?

((a))
L₁ is regular but not L₂
((b))
L₂ is regular but not L₁
((c))
Both L₁ and L₂ are regular
((d))
Neither L₁ nor L₂ are regular

Show Answer

Answer: ((a))

L₁ is regular but not L₂

DFA of L₁ is possible so L₁is regular.

Suppose string 011011011 in this string number of occurrences of 011 is 3 but number of occurrences of

110 is 2 so if we append 0 at the end then number of occurrences of 110 will also be 3.

So, using this idea, we can construct DFA of L1.

DFA:

In L₂ DFA cannot be constructed and hence L₂ is not regular.

NOTE:

L₂ is context free grammar.

Consider two strings A = ”qpqrr” and B = ”pqprqrp”. Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let 􀝕 be the number of such longest common subsequences between A and B. Then x + 10y = ___.

Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.

Consider the expression tree shown. Each leaf represents a numerical value, which can either be 0 or 1. Over all possible choices of the values at the leaves, the maximum possible value of the

expression represented by the tree is ___.

Consider the following function

double f(double x){

if( abs(x*x – 3) < 0.01) return x;

else return f(x/2 + 1.5/x);

}

Give a value q (to 2 decimals) such that f(q) will return q:_____.

Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the following statements is TRUE with respect to this modified stack?

((a))
A queue cannot be implemented using this stack.
((b))
A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE takes a sequence of two instructions.
((c))
A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction.
((d))
A queue can be implemented where both ENQUEUE and DEQUEUE take a single instruction each.

Show Answer

Answer: ((c))

A queue can be implemented where ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction.

Explanation:

We want to implement queue using stack which has three functions reverse, push and pop.

Example:

Suppose we want to insert a,b in queue using stack then

ENQUEUE item a:

Step 1: reverse (stack)

Step 2: push (a)

Step 3: reverse(stack)

ENQUEUE item b:

Step 1: reverse (stack)

Step 2: push (b)

Step 3: reverse(stack)

After inserting b to stack if we want to DEQUEUE then only pop of top element is sufficient.
So for ENQUEUE takes a sequence of three instructions and DEQUEUE takes a single instruction.
Similarly DEQUEUE (reverse pop reverse) and ENQUEUE ( push ) is also valid for queue implementation.

Hence option 3 is the correct answer.

Consider the C function given below.

int f(int j)

{

static int i = 50;

int k;

if (i == j)

{

printf(“something”);

k = f(i);

return 0;

}

else return 0;

}

Which one of the following is TRUE?

((a))
The function returns 0 for all values of j.
((b))
The function prints the string something for all values of j.
((c))
The function returns 0 when j = 50.
((d))
The function will exhaust the runtime stack or run into an infinite loop when j = 50.

Show Answer

Answer: ((d))

The function will exhaust the runtime stack or run into an infinite loop when j = 50.

Explanation:

Recursion tree:

This will goes into infinite loop and function exhaust the runtime stack, hence option 4 is the correct answer.

In designing a computer’s cache system, the cache block (or cache line) size is an important parameter. Which one of the following statements is correct in this context?

((a))
A smaller block size implies better spatial locality
((b))
A smaller block size implies a smaller cache tag and hence lower cache tag overhead
((c))
A smaller block size implies a larger cache tag and hence lower cache hit time
((d))
A smaller block size incurs a lower cache miss penalty

Show Answer

Answer: ((d))

A smaller block size incurs a lower cache miss penalty

Concept:

Bigger block size implies better spatial locality. Block size doesn’t depend on cache tag. Smaller block

size incurs a lower cache miss penalty.

Explanation:

Bigger block size implies better spatial locality because when a word is requested by CPU then with that word all nearby words should also placed in cache so if block size of main memory is bigger than more number of words will be in the block so there will be better spatial locality.

So option 1 is the wrong.

Block size doesn’t depend on cache tag bits even if we decrease block size tag bits will remain same.

Example:

Virtual address space = 32 bits, Block size = 64 Byte, Cache size = 16 KB using Direct mapping

${\rm{Cache;lines}} = \frac{{{2^{14}}}}{{{2^6}}} = 256$

If block size = 32Byte then cache lines = 512

Tag bits will be same so option 2 is the wrong.

Cache tag overhead will be more in case of smaller block size in above example

When block size is 64 Byte then cache tag (cache lines x Tag bits) is 256 x 18 bits

When block size is 32 byte then cache tag is 512 x 18 bits.

If larger cache tag then cache hit time will also be higher because more possibilities are there and we have to choose one.

Miss penalty is the time to copy data from main memory to the cache this is different from miss rate.
Smaller block size incurs a lower cache miss penalty because less amount of data needs to be taken from the lower level memory so miss penalty will be reduced but not miss rate.

If the associativity of a processor cache is doubled while keeping the capacity and block size unchanged, which one of the following is guaranteed to be NOT affected?

((a))
Width of tag comparator
((b))
Width of set index decoder
((c))
Width of way selection multiplexor
((d))
Width of processor to main memory data bus

Show Answer

Answer: ((d))

Width of processor to main memory data bus

Explanation:

Example:

Virtual address space = 32bits, Block size = 64Byte, Cache size = 4KB using set associative mapping

2 way set associative: ${\rm{Cache;lines}} = \frac{{{2^{12}}}}{{{2^6}}} = {2^6},{\rm{;}}1{\rm{;set}} = 2{\rm{;lines;so;total;}}{2^{5{\rm{;}}}}{\rm{sets;are;here}}$

4 way set associative: ${\rm{Cache;lines}} = \frac{{{2^{12}}}}{{{2^6}}} = {2^6},{\rm{;}}1{\rm{;set}} = 2{\rm{;lines;so;total;}}{2^{4{\rm{;}}}}{\rm{sets;are;here}}$

Changes after doubled associativity:

Set index decoder bits are decreased.
Tag comparator bits are increased.
Width of way selection multiplexor is depending on tag bits so here tag bits is increased so width will also be increased.
Main memory data bus has nothing to do with cache associatively hence option 4 is the correct answer.

The value of float type variable is represented using the single-precision 32-bit floating point format of IEEE-754 standard that uses 1 bit for sign, 8 bits for biased exponent and 23 bits for mantissa. A float type variable X is assigned the decimal value of −14.25. The representation of X in hexadecimal notation is

((a))
C1640000H
((b))
416C0000H
((c))
41640000H
((d))
C16C0000H

Show Answer

Answer: ((a))

C1640000H

Concept:

32-bit floating-point representation of a binary number in IEEE- 754 is

Sign (1 bit)	Exponent (8 bit)	Mantissa bit (23 bits)

In IEEE-754 format, 32-bit (single precision)

(-1)^s× 1.M × 2^{E – 127}

Calculation:

Convert: 14.25 to binary

Step 1: convert 40


2	14
2	7	0
2	3	1
2	1	1
	0	1↑

(14)₂ = (1110)₂

Step 2: convert .25 to binary

0.25 × 2 = 0.5 (0)

0.5 × 2 = 1.0 (1)

Given binary number is

(40.1)₁₀ = (1110.01)₂

(40.1)₁₀ = 1.11001 × 2³

Signed (1 bit) = 1 (given number is negative)

Exponent (8 bit) = 3 + 127 = 130

∴ Exponent = (130)₁₀ = (1000 0010)₂

Mantissa (23 bits ) = 0100 0000 1100 1100 1100 110

Sign (1 bit)	Exponent (8 bit)	Mantissa bit (23 bits)
1	1000 0010	1100 1000 0000 0000 0000 000

(1100 0001 0110 0100 0000 0000 0000 0000)₂ = (C1640000)₁₆

(C2206666)₁₆= C1640000H

In the Newton-Raphson method, an initial guess of x₀ = 2 is made and the sequence x₀, x₁, x₂ …

is obtained for the function

0.75x³ – 2x² – 2x + 4 = 0

Consider the statements

(I) x₃ = 0.

(II) The method converges to a solution in a finite number of iterations.

Which of the following is TRUE?

((a))
Only I
((b))
Only II
((c))
Both I and II
((d))
Neither I nor II

Show Answer

Answer: ((a))

Only I

In Newton-Raphson method

${x_{n + 1}} = {x_n} - \frac{{f\left( {{x_n}} \right)}}{{f'\left( {{x_n}} \right);}};$

Calculation:

f(x) = 0.75x³ – 2x² – 2x + 4 = 0

f'(x) = 2.25×x² – 4x - 2

x₁ = 2 - (0.75× 2³ – 2×2² – 2× 2 + 4) ÷ (2.25 × 2² – 4× 2 - 2)

= 2 - (-2/-1)

= 0

x₂ = 0 - (4 ÷ -2) = 2

x₃ = 0

x = 0 and x = 2 repeatedly and it never converges.

The product of the non-zero eigenvalues of the matrix $\left[ {\begin{array}{*{20}{c}} 1&0&0&0&1\ 0&1&1&1&0\ 0&1&1&1&0\ 0&1&1&1&0\ 1&0&0&0&1 \end{array}} \right]$ is _______

The probability that a given positive integer lying between 1 and 100 (both inclusive) is NOT divisible by 2, 3 or 5 is _____

The number of distinct positive integral factors of 2014 is ________

Consider the following relation on subsets of the set 􀜵 of integers between 1 and 2014. For two

distinct subsets U and V of S we say U < V if the minimum element in the symmetric difference of

the two sets is in U.

Consider the following two statements:

S1: There is a subset of S that is larger than every other subset.

S2: There is a subset of S that is smaller than every other subset.

Which one of the following is CORRECT?

((a))
Both S1 and S2 are true
((b))
S1 is true and S2 is false
((c))
S2 is true and S1 is false
((d))
Neither S1 nor S2 is true

Show Answer

Answer: ((a))

Both S1 and S2 are true

Two distinct subsets U and V of S we say U < V if the minimum element in the symmetric difference of the two sets is in U.

Since: S = {1, 2, 3, ...., 2014}.

Therefore, Subsets {1, 2, 3, …., 2014} and {Ø} of S, so {1, 2, 3, …., 2014} < {Ø} because the minimum element in the symmetric difference (i.e., {1, 2, 3, ...., 2014}) of the two sets is in set {1, 2, 3, ...., 2014}.

Hence, {Ø} is a subset of S that is larger than every other subset. And, {1, 2, 3, …., 2014} is a subset of S that is smaller than every other subset.

Hence, {Ø} is a subset of S that is larger than every other subset.

And, {1, 2, 3, …., 2014} is a subset of S that is smaller than every other subset.

A cycle on n vertices is isomorphic to its complement. The value of n is _____.

The number of distinct minimum spanning trees for the weighted graph below is _____

Which one of the following Boolean expressions is NOT a tautology?

((a))
((a → b) ∧ (b → c)) → (a → c)
((b))
(a ↔ c) → (∼ b → (a ∧ c))
((c))
(a ∧ b ∧ c) → (c ∨ a)
((d))
a → (b → a)

Show Answer

Answer: ((b))

(a ↔ c) → (∼ b → (a ∧ c))

Concept:

Using digital logic concept, we can find out whether Boolean expressions is a tautology or not.

In digital logic, we can write OR as +, AND as . , Negation as complement.
${\rm{p}} \to {\rm{q}} \equiv \sim{\rm{p;V;q}} \equiv {{\rm{p}}^{\rm{'}}} + {\rm{q}}$
${\rm{p}}.{\rm{p'}} \equiv {\rm{FALSE}}$
${\rm{p}} + {\rm{p'}} \equiv {\rm{TRUE}}$
${\rm{p}} + {\rm{q}}.{\rm{r}} \equiv \left( {{\rm{p}} + {\rm{q}}} \right)\left( {{\rm{p}} + {\rm{r}}} \right)$
${\rm{p}} \leftrightarrow {\rm{q}} \equiv \left( {{\rm{p}} \to {\rm{q}}} \right) \cap \left( {{\rm{q}} \to {\rm{p}}} \right)$

Explanation:

Option 1:

$(({{\rm{a}}^{\rm{'}}} + {\rm{b}}).\left( {{\rm{b'}} + {\rm{c}}} \right)) \to \left( {{\rm{a'}} + {\rm{c}}} \right)$

${\left( {{\rm{a'b'}} + {\rm{a'c}} + {\rm{bb'}} + {\rm{bc}}} \right)^{\rm{'}}} + {\rm{a'}} + {\rm{c}}$

$\left( {{\rm{a}} + {\rm{b}}} \right).\left( {{\rm{a}} + {\rm{c}}} \right).\left( {{\rm{b'}} + {\rm{c'}}} \right) + {\rm{a'}} + {\rm{c}}$

$\left( {{\rm{a}} + {\rm{ac}} + {\rm{ab}} + {\rm{bc}}} \right)\left( {{\rm{b'}} + {\rm{c'}}} \right) + {\rm{a'}} + {\rm{c}}$

${\rm{ab'}} + {\rm{ac'}} + {\rm{ab'c}} + {\rm{acc'}} + {\rm{abb'}} + {\rm{abc'}} + {\rm{bcb'}} + {\rm{bcc'}} + {\rm{a'}} + {\rm{c}}$

${\rm{ab'}} + {\rm{ac'}} + {\rm{ab'c}} + {\rm{abc'}} + {\rm{a'}} + {\rm{c}}$

${\rm{a}}\left( {{\rm{b'}} + {\rm{c'}} + {\rm{b'c}} + {\rm{bc'}}} \right) + {\rm{a'}} + {\rm{c}}$

${\rm{a}}\left( {\left( {{\rm{b'}} + {\rm{b}}} \right).\left( {{\rm{b'}} + {\rm{c}}} \right) + ({{\rm{c}}^{\rm{'}}} + {\rm{c}}} \right).\left( {{\rm{c'}} + {\rm{b'}}} \right)) + {\rm{a'}} + {\rm{c}}$

${\rm{a}}\left( {{\rm{b'}} + {\rm{c'}}} \right) + {\rm{a'}} + {\rm{c}}$

${\rm{ab'}} + {\rm{ac'}} + {\rm{a'}} + {\rm{c}} \equiv {\rm{a'}} + {\rm{a}} + {\rm{b'}} + {\rm{c}} \equiv {\rm{T}} + {\rm{b'}} + {\rm{c}} \equiv {\rm{TRUE}}$

Option 1 is tautology.

Option 3:

$\left( {\left( {{\rm{a}}.{\rm{b}}.{\rm{c}}} \right) \to {\rm{c}} + {\rm{a}}} \right) \equiv \left( {{{\left( {{\rm{abc}}} \right)}^{\rm{'}}} + {\rm{c}} + {\rm{a}}} \right) \equiv \left( {{\rm{a'}} + {\rm{a}} + {\rm{c'}} + {\rm{c}} + {\rm{b'}}} \right) \equiv \left( {{\rm{T}} + {\rm{T}} + {\rm{b'}}} \right) \equiv {\rm{TRUE}}$

Option 3 is tautology.

Option 4:

${\rm{a}} \to \left( {{\rm{b'}} + {\rm{a}}} \right) \equiv \left( {{\rm{a'}} + {\rm{a}} + {\rm{b'}}} \right) \equiv \left( {{\rm{T}} + {\rm{b'}}} \right) \equiv {\rm{TRUE}}$

Option 4 is tautology.

Hence option 2 is not tautology.

SQL allows duplicate tuples in relations, and correspondingly defines the multiplicity of tuples in the result of joins. Which one of the following queries always gives the same answer as the nested

select * from R where a in (select S.a from S)

((a))
select R.* from R, S where R.a = S.a
((b))
select distinct R.* from R, S where R.a = S.a
((c))
select R.* from R,(select distinct a from S) as S1 where R.a = S1.a
((d))
select R.* from R,S where R.a = S.a and is unique R

Show Answer

Answer: ((c))

select R.* from R,(select distinct a from S) as S1 where R.a = S1.a

Concept:

IN(1,2,2,3) is same as IN(1,2,3).

Unique keyword doesn’t allow redundant tuples in R.

Explanation:

Example:

select * from R where a in (select S.a from S)

Output of inner query a= (3,2,2,1,1)=(1,2,3)

Final Output:

Option 1:

select R.* from R, S where R.a = S.a

Output:

Option 2:

select distinct R.* from R, S where R.a = S.a

Output:

Option 3:

select R.* from R,(select distinct a from S) as S1 where R.a = S1.a

Output:

Option 4:

select R.* from R,S where R.a = S.a and is unique R

Output: NULL SET

Hence option 3 is the correct answer.

Consider a main memory system that consists of 8 memory modules attached to the system bus, which is one word wide. When a write request is made, the bus is occupied for 100 nanoseconds (ns) by the data, address, and control signals. During the same 100 ns, and for 500 ns thereafter, the addressed memory module executes one cycle accepting and storing the data. The (internal) operation of different memory modules may overlap in time, but only one request can be on the bus at any time. The maximum number of stores (of one word each) that can be initiated in 1 millisecond is ____________

Attempt this paper under real exam conditions

Timed interface, section switching, instant scoring, and question-by-question analytics — free.

Start Timed Attempt