Solution

Solution

Second row element = First row element - Third row element

54 - 42 = 12

76 - 46 = 30

63 - 12 = 51

Solution

Solution

• The second train has travelled 72 km more than the first train because the speed of the second train is 12 km/hr more than the first.
• Time taken by second train to cover 72 km with surplus 12 km/hr = 72/12 = 6 hours

Then the time taken by both trains before meeting is 6 hours.

• So, relative speed = 36 + 48 = 84
• Total distance covered by both trains = 84 × 6 = 504 km
• Distance between A & B = 504 km

Solution

From I, II, III, we get

K : L : M = (120000×8) : (80000×12) : (X*9)

Since M’s investment is not given, the above ratio cannot be given.

∴ Data adequate.

Solution

All the numbers in the series are alternative prime numbers. So the missing term is 23.

Solution

The words 'pain' and 'pane' 'plain' and 'plane' are homophones: they sound alike but have different meanings. Therefore you need to understand the context of the sentence to use the write word.

The above sentence is in relation with rain hitting against a window pane. Pane refers to the glass sheet of a window.

Solution

The relationship here is about the character of the person and the person.

The word tyrant means a cruel or oppressive Ruler.

Therefore the character disciplinarian best suits teacher in the options given.

Solution

The words Banquet, Carnival and Merry - making are synonyms of Feast. Whereas the word Ravenous means hunger for food. Therefore Ravenous is the odd word here.

Solution

In the passage it is given ‘Exercise regularly to improve blood circulation and to release the feel-good hormone - endorphins.’

Solution

Postorder traversal of the given binary tree will give the following sequence: 4 5 2 6 7 3 1.

Now comparing the sequence with p q – r s * + we get 1 = +, 2 = -, 3 = *, 4 = p, 5 = q, 6 = r and 7 = s.

So, option (A) is correct.

Solution

The C preprocessor will literally substitute all instances of x for 4+1, resulting in the following code:

i = 3+2*3+2*3+2;

Since * has precedence over +, this evaluates to:

i = 3+6+6+2;

and i gets the 17 value .

Solution

We try to keep the tree balanced and increase height as much possible in each iteration.

Max height = 3

Solution

In adjacency matrix, dimension is nn.

To find all neighbours we need O(n) operations.

∴ Tight bound = O(n^2)

Solution

f(b) < f(c), but b is not ancestor of c.

Solution

Last value in post order is root.

∴ E is root.

All values before E in preorder would be in left subtree.

H, F, I will be in left subtree.

∴ Answer: 3

Solution

The correct options are correct statements!

Solution

The bitwise XOR operator can be used to swap two variables. The XOR of two numbers x and y returns a number which has all the bits as 1 wherever bits of x and y differ. For example XOR of 10 (In Binary 1010) and 5 (In Binary 0101) is 1111 and XOR of 7 (0111) and 5 (0101) is (0010).

Solution

Let P(w) is the maximum profit obtained with weight w.

P(0) = 0

P(1) =30 (Item 3)

P(2)=Max⁡(64+P(0),30+P(1) )

=Max⁡(64,60)

=64(Item 1)

P(3)=Max⁡(81+P(0),64+P(1),30+P(2) )

=Max⁡(81+0,64+30,30+64)

=Max⁡(81,94,94)

=94(Item 1,3)

P(4)=Max⁡(64+P(2),81+P(1),30+P(3) )

=Max⁡(64+64,81+30,30+94)

=Max⁡(128,111,124)

=128(2 number of Item 1's)

P(5)=Max⁡(64+P(3),81+P(2),30+P(4),25)

=Max⁡(64+94,81+64,30+128,25)

=Max⁡(158,145,158,25)

=158(2 number of item 1 &1 number of item 3)

So,total profit is 158.

Solution

FALSE: Multiplying all edge weights by a positive number does not change the graph’s minimum spanning tree.

TRUE: A graph can have more than one shortest path between two vertices

FALSE: A graph where all edge weights are distinct can have more than one shortest path between two vertices.

Even if no two edges have the same weight, there could be two paths with the same weight. For example, there could be two paths from s to t with lengths 3 + 5 = 8 and 2 + 6 = 8. These paths have the same length (8) even though the edges (2, 3, 5, 6) are all distinct.

FALSE: Inserting an element into a binary search tree takes O(h) time, where h is the height of the tree. If the tree is not balanced, h may be much larger than log n (as large as n − 1).

Solution

Solution

Initially table is

When we try to insert 103, it should be put at slot 3(since 103 mod 10 = 3). Since already 23 are present at slot 3 we will move to the next slot and in the next slot also 34 is present. So, we will put 103 at slot 5. Therefore the number of collisions after inserting 103 is 2.

Final hash table is

Now when we try to insert 33, collisions will happen between 33 and 23, 34, 103, 6, 7, 48, 19. So, finally it will be placed at slot 0.

Here the number of collisions after inserting 33 is 7.

Solution

TotalIn insertion sort the worst case passes are (n-1). So, asymptotically O(n).

In each pass we need to find the search time and move (or) shift the elements of an array.

= Search time + Moving or shifting the elements of an array

= O(logn)+O(n)

= O( Time complexity = Total number of passes * Each pass time.

= O(n)*O(n)

= O(n^2)

Solution

The given Bob() function is a variant of selection sort.

If all elements are already in sorted order, then the condition k!=i always falls and no swap will be performed.

There are zero swaps in the best case of the above Bob()function.

O(1) swaps are the best case.

Solution

Finite automata has finite memory, actually FSM memory is limited by its number of states. Every Moore machine can be converted into corresponding Mealy machine. Every regular grammar is also CFG and hence we can convert it into CNF. But the resulting grammar will not be regular.

For example: Consider a regular grammar

S-> aS | a

The corresponding CFG in CNF form will be

S-> SA |a

A->a

Solution

Start with “a”: a(a+b)*

Product Automata:

Min DFA: State BP and BQ are equivalent

End with “b”: (a+b)*b

Solution

The equivalence of DCFL and regular is a decidable problem. But equivalence of regular language and CFL (NPDA) is undecidable. Hence S1 is correct but S2 is false.

Solution

The given FA accept ((a+b)(a+b))*

Which is equivalent to (aa+ab+ba+bb)*

Reg expr: (aa+bb)* + (ab+ba)* does not generate string “aaab” hence it cannot be correct.

Reg expr: a((a+b)(b+a))* a+ b((a+b)(b+a))*b + ϵ does not generate string “ab” hence it cannot be correct.

Solution

The TM first changes the “a” into “x” and then skip all next a’s (and y’s) and convert the corresponding “b” into “y”. If the number of a’s and b’s are equal then at the end all a’s has converted into “x” and all “b’s” has converted into “y’s” at state q0.

Suppose TM start from q0 with input “βaabbβ” on reaching q2 , the input will be

“βxaybβ”, head is at “y” , now on q2 (y,y,L ), head will be on “a” {string-> “βxaybβ}, using (a,a,L) on q2, it will be (βxaybβ) . Now P must be (x,x,R) because again we have to convert next “a” into “x”.

In the second iteration suppose second “a” is also converted into “x” and second “b” is converted into “y” at state q2 like -> {βxxyyβ} suppose head is at “y” on q2. Using transition P (x,x,R) , it will reach to state q0 and head is on first “y” like -> {“βxxyyβ}. So on state if head is on “y” means all “a’s are over and we need to move on q3 and hence the transition Q will be (y,y,R) and on q3 self loop (y,y,R) will lead to “β” at end (iff number of a’s and b’s are equal) and on reaching β (blank) means number of a’s and b’s are equal hence accept.

Solution

The string “1111” can be derived by the following ways.

1. Using S->S1 four times (it can be done in only one way)

2. using S->1S1 two times (it can be done in only one way)

3. Using one S-> 1S1 and two S->S1 (it can be done in three ways)

So Total 5 ways

Solution

The given grammar is ambiguous, as it has two parse trees for string “1111”. So, none of the above is true.

Solution

In S-attributed SDT , semantic action can be written only at the end of the production in RHS.

S-attributed SDT uses Bottom up parser.

S-attributed SDT is also known as postfix SDT.

Solution

It is not S-attributed as A.val (in P1) is an inherited attribute. It is not L-attributed as A.val is depending on B₁.val, since in L-attributed definition is:

Each attribute must be either

1. Synthesized

2. Inherited, but with the rules limited as follows. Suppose that there is a production A→ X₁ X₂…X_n and that there is an inherited attribute X_i.a computed by a rule associated with this production. Then the rule may use only:

a. Inherited attributes associated with the head A.

b. Either inherited or synthesized attributes associated with the occurrences of symbols X₁, X₂,. . . , X_i-1 located to the left of X_i.

Production 2 follows both S attributed as well as L attributed definition, as in L attributed only synthesized is also allowed and P2 has synthesized attribute.

Solution

r₁: (a*b+ b*a)* = (a+b)* , as we can assume a* and b* as epsilon, which will give (a+b)* and since (a+b)* is superset of all possible language over {a,b} hence

(a*b+ b*a)* == (a+b)* .

r₂: Similarly (aa*+bb*)* = (a+b)* , if we assume a* and b* as epsilon.

So r1=r2=(a+b)* and their intersection is also equal to (a+b)* which is also equal to (a*+b*)*

Solution

Responsibilities of transaction management are:

· Ensures that the database remains in a consistent state despite Power failures

· Ensures that the database remains in a consistent state despite Operating system crashes

· Ensure the consistency of the database during interaction among the concurrent transactions

· Ensure consistency of database by orchestrating all access requests issued by the transactions

Solution

CHECK constraints enforce domain integrity

UNIQUE constraints enforce the uniqueness of the values in a set of columns

Solution

The natural of r1 and r2 will have 7 tuples.

Solution

Both the following queries will return the employees with years of experience greater than at least one employee in the Accounts department:

a) SELECT distinct E.name FROM employee AS E, employee AS F WHERE E.years_exp > F.years_exp AND F.dept_name& = 'Accounts';

b) SELECT name FROM employee WHERE years_exp > SOME ( SELECT years_exp FROM employee WHERE dept_name = 'Accounts');

Solution

strlen(); is a function (user defined or library), which does not invoke a system call directly in its definition.

Solution

A system call always requires OS support. Therefore, a running process will be context switched with the OS kernel module. Rest of them may not always result in a context switch.

Solution

The fork system call returns 0 to child and any integer > 0, to the parent. On fork the entire code is cloned in the child. If part is executed by the parent after fork, and else part is executed by the child. The parent makes a=60 and closed file descriptor. The child however has a=50, which is printed after execution. As the file descriptor (fd) is also copied during the fork, the child can use it even though the parent has closed it.

Solution

Gantt chart :

Solution

Valid and present bits in a page entry of the page table indicates that the page is valid and present in the main memory. Therefore, a page fault cannot occur. We cannot say a TLB hit or miss occurs, as the page entry may or may not be loaded into TLB

Solution

Solution

Solution

• Loss of ACK from client does not effect on termination of connection because client use timeout timer, after it expire it send “ACK” and goes in closed state, where if server does not receive “ACK” then its timer expire and send FIN segment one more time and termination of connection. So True

• Client moves FIN-Wait-1 → FIN-Wait-2 → Timeout → Closed. So False

• Loss of ACK from the server does not affect since when the client receives FIN from the server, then the client understands that “ACK” was lost. So False

Solution

= 2^48 / (2^32 x 500 ) = 131.07 = 131

Solution

Its already announced that its a black card, so the sample space is 26 ( there r 26 black cards). Out of which the clubs are 13.

Thus prob = 13/26 = 1/2

Solution

The first woman can be joined with 1 out of 6 men (i..e in 6 ways).

Second woman in 5 ways, and third 4, last woman has 3 ways.

In total 6x5x4x3 = 360 ways the pairs can be formed

Solution

The product of the eigenvalues is the Determinant of the matrix.

Out of the given options, 18*1*-9 = -162, -81*-1*-2 = -162

Solution

Solution

Solution

A lattice should have GLB, LUB. With the given set ‘A’, we get three lower bounds {a,b,d}, {a,b,x}, {a,b,z}. Out of the given options either {a} or {b} or {a,b} can make a complete lattice.

Solution

Solution

The number of ways of forming a 5 distinct letters word out of 8 distinct is 8P5 = 6720

Solution

By definition, in a vectored interrupt the interrupting device provides the starting address of the ISR. Hence option A is true.

Solution

We can take each task mentioned here is one instruction.

It is given that each task takes 72ns in the non-pipelined execution.

Time taken for 100 tasks in the non-pipelined execution = 100*72ns

In a pipeline with k stages, time taken to execute a program of n instructions = k+n-1 clock cycles

Here k = 6 and n = 100

So time in the pipeline = 6+100-1 = 105 clock cycles

Each clock cycle time = 12ns

Time in the pipeline = 105*12 ns

Speed up = Time without pipeline / Time with pipeline = 100*72 / 105*12 = 5.71

Solution

In the immediate addressing mode, the operand is provided in the instruction itself, so it doesn’t require a memory access to load the operand.

Direct addressing mode has the effective address of the operand in the instruction, it requires one memory access to get the operand.

Indirect addressing requires two memory accesses the operand as the address of the address is given in the instruction.

Implied addressing mode doesn’t require a memory access to load the operand as it is a basic operation on special registers, ex: INCA (to increment the accumulator), CLA (Clear accumulator) etc

Hence out of all the given options Indirect addressing mode requires more memory accesses.

Solution

1. Option A is false as memory mapped I/O has same address space for memory and I/O.
2. Option B is true as memory-mapped I/O uses the same set of read, write control lines for both memory and I/O transfers.
3. Option C is true as isolated I/O has distinct input, output instructions.
4. Option D is false memory mapped I/O has same input and output instructions.

Solution

Cache size = 8 blocks

In a 2-way set associative cache there will be 2 blocks in each set.

Number of sets in the cache = 8/2=4

We can place the block in the set given by (blocknum)%(number of sets).

0, 4, 9, 5, 16, 13, 15, 19, 25, 63, 24, 57, 30

From the given options main memory block 15 is not in the cache at the end of the access as it got replaced by 63

Solution

From the figure,

f(A,B,C)= AB’ C’ + AB.1

= AB’C’ + ABC’ + ABC

= m₄ + m₆ + m₇

f(A,B,C)= M₀M₁M₂M₃M₅.

Solution

In a neutral function, the number of minterms is equal to the number of maxterms. The functions XOR and XNOR are neutral functions.

Solution

Solution

It is a cyclic K-map.

f₁+f₂= a’b’ + ac + bc’

or

f₁+f₂= a’c’ + b’c + ab

Solution

A₀= A

A₁= A ⊕ A= 0

A₂= A⊕A⊕A= A.

A₃= A⊕A⊕A⊕A= 0.

A_n= 0; if n is odd.

A_n= A; if n is even.

B₀= B

B₁= B ⊙ B = 1

B₂= B ⊙ B ⊙ B= B

B₃= B ⊙ B ⊙ B ⊙ B= 1

Bn= 1 if n is odd.

Bn= B if n is even.

A_n ⊕ B_n= 0 ⊕ 1 if n is odd.

A_n ⊕ B_n= A ⊕ B if n is even.