Solution

Solution

Solution

The given series is in a pattern of

1 x 2, 2 x 3, 3 x 4, 4 x 5, 5 x 6, 6 x 7, 7 x 8, 8 x 9

The correct series is: 2, 6, 12, 20, 30, 42, 56, 72.

Solution

Solution

Solution

Solution

Deduction 1 can't be taken because in the statements it's given some toys are Cows, some are Rabbits, there is nothing said about the remaining toys, it could be anything but no information is given.

Deduction 2 cannot be taken because Cows and Rabbits are separate entities.

Solution

Here the relationship is between larva form of the insect to the insect. The larva form of Butterfly is known as Caterpillar. The larva form of Cockroach is known as Nymph.

Solution

Moulding is the process of shaping liquid or pliable raw material into a frame.

Solution

To take the bull by the horns means to tackle a difficult or challenging situation bravely.

Solution

Option ‘(cursor = cursor->link())’ is not a boolean expression; it is an assignment; hence it is straight away discarded. If the cursor is pointing to the tail node or last node then there is no node after the tail node. In other words (cursor->link( ) == NULL). Hence this is the correct answer.

Solution

QMNPRO

Solution

Before deleting the parent node we should delete its children first, hence if do post-order traversal the leave nodes will be covered before the root and hence it will be useful.

Solution

Check out the following C code with extra printf and comments which let you understand how the code is working:

#include<stdio.h>

void main()

{int a=3,b=6;

float x=4.5;

//if(a*b>x*x)

printf("linkon:%d:%f\n", a*b, x*x);

//else if(a*b>(int)x*x)

printf("lily:%d:%f\n",a*b,(int)x*x);

//else if(a*b>(int)x*(int)x)

printf("logan:%d:%f\n",a*b,(int)x*(int)x);

}

Output:

linkon:18:20.250000

lily:18:18.000000

logan:18:18.000000

Solution

Putting rounding braces based on precedence and associativity can be given by

((a + (b × c)) ­ (d ^ (e ^ f )))

Hence postfix expressions will be given by abc × + def ^ ^

Solution

Check the following code and the output:

#include <stdio.h>

int main()

{

int i = 524;

for (; i; i >>= 1)

printf("fan i = %d\n",i);

return 0;

}

Output:

fan i = 524

fan i = 262

fan i = 131

fan i = 65

fan i = 32

fan i = 16

fan i = 8

fan i = 4

fan i = 2

fan i = 1

Solution

As the recursive call is calling b--, a post-decrement, the 10 will not decremented immediately.

f1(b--);

this means:

f1(b);

b--;

Hence f1(10) calls f1(10) again and again.hence infinite loop.

Solution

#include<stdio.h>

void main()

{

char arr[]="\0";

printf("%d",printf("%s",arr)); // inner printf %s will have value as NULL which is nothing and hence returns 0 and hence outer printf will print 0.

if(printf("%s\t",arr)) //%s will print nothing here, just like above but because of \t printf will return 1, hence if(1) means true which executes if block and not else.

printf("Good\n"); // this will be executed

else

printf("Nice\n");

}

Output:

0 Good

Solution

LCS of X = bcadsce and Y = csadesg

Note: If string length is small better to go for brute force method, and start with tracing X array. We can also follow row major order or column major order.

X = bcadsce

Y = csadesg

So, the total length is 4 and the string is cade.

The optimal substructure of the LCS problem gives the recursive formula

Solution

We sort the objects based on profit/Weight Ratio in descending order and place it accordingly in the knapsack.

The objects are in sorted order according to their profits are: V,Q,X,R,P,S,T,W

Object V, Knapsack Capacity = 60-4=56, Profit=15

Object Q, Knapsack Capacity = 56-10=46, Profit=25

Object X, Knapsack Capacity = 46-8=38, Profit=18

Object R, Knapsack Capacity = 38-15=23, Profit=30

Object P, Knapsack Capacity = 23-20=3, Profit=36

Object S, Knapsack Capacity = 3-3=0, Profit=5.4

Weight of the object s is greater than Knapsack capacity. So, just add a part of object s is 3.

The profit will be 1.8*3=5.4

The Knapsack bag capacity=0

Then the total profit= 15+25+18+30+36+5.4=129.4

Solution

=Θ(n^4)

let c1=2 and c2=3

Solution

Time complexity of merge sort = O(n log n) = an log n

where c is some constant

It is given that for n = 64,

cn log n = 30

c × 64 log 64 = 30

c × 64 × 6 = 30

c = 5/64

Now, the value of n for

c n log n = 360

5/64 × n log n = 360

n log n = 360×64/5

= 72 × 64 = 2^9 × 9

So for n = 2^9, it satisfies.

So, n = 2^9 = 512

Solution

You can traverse either left or right but be in a min-heap.

Solution

(i) TRUE: A complete Binary Tree in a min heap tree if every parent node is minimum compared with its children.

(ii) FALSE: A complete Binary tree is a min heap tree if every parent node is greater than its left child and less than or equal to its right child.

(iii) TRUE: Heap sort is an inplace sorting technique because the space complexity is O(1).

(iv) FALSE: Heap sort is not stable

Solution

From transition table we can FA:

The FA accepts {a, aa, aaa, ……, b, bb, ….., c, cc, ccc, ……., ac, bc, abc, ……..}

Hence the FA accepts L=a*b*c*

We can see that for strings ending with “a” and whose length <= 2021, the FA will accept

{a, aa, aaa, ……………………, a2021 }. Hence FA will accept 2021 strings which is ending with “a” and having length less than equal to 2021.

Solution

L1 is a language which contains set of all strings ending with “ab” and L2 is a language which contains set of all strings ending with “b”. Clearly L1 is subset of L2, as all strings of L1 is already present in L2.

Hence L3= L2

The min DFA for L2

Solution

Solution

a*b* generate strings {∈, a, aa, aaa, ………, b, bb, bbb, ……., ab, aab, abb, aabb,……….}

The complement will have all strings which is not in a*b* such as {ba, aba, abab, bba, ……….}

b*a* generates strings which is present in a*b* for example {∈, b, bb, .., a, aa..} hence it is wrong.

b(a+b)* generates string {b, bb, ………} hence wrong.

b(a+b)*a cannot generate string “aba” which should be present in complement hence wrong.

Solution

Halting problem statement

"Whether a Turing machine M halts on w" this is halting problem and it is undecidable (recursive enumerable but not recursive).

So if it is undecidable for any "w" hence it is also undecidable for w =empty string.

Membership problem for CSL is decidable but emptiness problem for CSL is undecidable.

Whether a halting Turing machine rejects empty string is decidable, since it is given that “halting Turing machine” so it will always halt and hence decidable.

Equality problem for DCFL is decidable but subset problems for DCFL is undecidable.

Solution

The DFA for a(a+b)*

The complemented DFA

Hence L(complement)= b(a+b)* + ∈

Solution

Every regular language is accepted by deterministic finite automata and we can convert DFA into right linear grammar, which will always be LL(1).

Since the FA is deterministic so the grammar will never contain left factoring i.e, now two productions begin with the same symbol in RHS.

Every regular language is accepted by deterministic finite automata and we can convert DFA into left linear grammar, which will always be LR(0).

For ex:

S->Sa | ∈

This is LR(0) grammar.

If grammar contains null production then it cannot be LR(0), it is a false statement as aforementioned grammar contains null production and still it is LR(0).

Any grammar will never have shift-shift conflict for any parser.

Solution

Since * is having more precedence than + so E should derive + and T should derive *

Hence the correct SDT

E→ {print ‘+’;} E1+T

E→ T

T→{print ‘*’ ;} T1*F

T→F

F→(E)

F→id {print id.lexval ;}

Consider the string a*b+c and its prefix will be +*abc

Solution

If # is * (multiplication operator) then after evaluating (a*b) we need to save this value into memory and then evaluate c*d before performing the + operation. Hence in case of #=* we need to save a*b value into memory and then perform c*d and then fetch back a*b from memory and add into (c*d) value in register. But if #= + or – then we can perform

Step 1: t1= a*b

Step 2: t2= t1+c

Step 3: t3= t2 (+ or −) d

Hence in case of (+ or −) no need to save any intermediate value into memory.

Solution

variable “u” is used in statement 2 so it is live there, but “u” is not live in statement 1 (as it is assigned by 0) and also not live in statement 3 (as the value of “u” at statement 2 is not used in statement 3 and it is reassigned in statement 4).

“W” is live in statement 3 and 6 as it is used in these statements.

“V” is not live in statement 5 and it is reassigned in statement 2.

Solution

NULL is used if a column in a table is optional, we can insert a new record or update an existing record without adding a value to this column.

Solution

If T1, T2 and T3 are transactions with p, q and r operations respectively

Number of concurrent schedules

=(p+q+r)!/p!q!r!=(2+3+4)!/2!3!4!=9!/(2×6×4!)=(9×8×7×6×5)/(2×6)=63×20=1260

Solution

According to 2PL, if lock conversion is allowed, then upgrading of locks must be done during the expansion phase, and degrading of locks must be done in the shrinking phase.

∴ S2 is true.

Lock upgradation is not allowed in the shrinking phase therefore S1 is False.

Solution

Given relation R(MNPQT) and FD set

F₁ = {M → TN, P → QM} and

F₂ = {M → N, P → Q, P → MT, MN → T}

F₁ and F₂ are equivalent if F₁ can cover F₂ and F₂ can cover F₁

Check whether F₂ can cover F₁:

In F₁ first FD is M → TN

∴ find (M)+ in F₂

⇒ (M)+ = MNT

∴ M → TN can be covered by F₂

Second FD is P → QM

find (P)+ in F₂

(P)+ = PQMNT

∴ P → QM can be covered by F₂

∴ We can say that F₂ can cover F₁ → (1)

Check whether F₁ can cover F₂:

In F₂ first FD is M → N

∴ find (M)+ in F₁

⇒ (M)+ = MNT

∴ M → N can be covered by F₁

Second FD is P → Q

find (P)+ in F₁

(P)+ = PQMNT

∴ P → Q can be covered by F₁

Third FD is P → MT

find (P)+ in F₁

(P)+ = PQMNT

∴ P → MT can be covered by F₁

Fourth FD is MN → T

find (MN)+ in F₁

(MN)+ = MNT

∴ MN → T can be covered by F₁

∴ We can say F₁ can cover F₂ → (2)

From (1) & (2) we can say that F₁ and F₂ are equivalent.

So, (a) is correct answer.

∴ We can say that F₂ can cover F₁ → (1)

Solution

RR schedule P1(2ms),P2(3ms), P3 (2ms),P4(3ms),P2(1ms),P5(3ms),P4(3ms),P5(3ms),P4(7ms)

Waiting time = 0+(2+5)+(5‐3)+((7–4)+4+3)+((10‐6)+4)=27/5=5.4ms

Solution

Entry section:flag[i] = TRUE; turn = j; while (flag[j] && turn == j);

Exit section: flag[i] = FALSE;

Solution

Entries in inverted page table = 2^29/2^12 = 2^17 = 128K.

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 child after fork, and else part is executed by the parent. The parent makes count=1. In child however count=0, which is printed after execution. The parent has no printf statement to execute, and hence does not print anything.

Solution

Solution

In order to avoid the hidden terminal problem, each station send RTS (request to send) before sending a data frame for request reserve the channel and CTS (clear to send) frame receives so that channel is reserved by telling every other station that channel is reserved. So true.

• 802.11 frame uses 32-bit CRC not checksum.

• 802.11 uses exponential backoff algorithm if two or more station sends channel busy.

Solution

Token bucket generally allows bursty traffic at a regulated maximum rate. Rather it is a leaky bucket which shapes bursty traffic into fixed-rate traffic by averaging the data rate.

• Leaky buckets are more restrictive as compared to the token bucket. It doesn’t take into account the time when the host was idle.

• Choke packet are the packets that are sent by a node to the source to inform it of congestion and hence is a congestion control policy.

Solution

Solution

Solution

Any divisor set with divides operation is distributive

Solution

Solution

Pen colors correspond to Pigeon holes.

We have two pigeon holes(red, blue)

That person could select 10 red pens in a row, then the person needs to select 4 more blue pens. So, it should be 14 selections, which can ensure that remaining 4 are blue pens.

Solution

Determinant of singular matrix is 0.

|A|=0

1(7x-4)-2(7-3)+3(4-3x)=0

7x-4-8+12-9x=0

-2x-12+12=0

x=0

Solution

Solution

Solution

For all x>5, x^2 is always greater than 18. Just consider any x value that's >5, let x=6 then x^2=36 >18. Thus its true

Any number x>8 is a real number, it's also true as the domain x>8 is part of real numbers

There exists no number less than 0 for |x|. Thus its false

There exists x=5,y=5 which makes x^2+y^2=50, thus its true

Solution

Solution

All the three given are I/O transfer modes employed in transferring I/O data.

Solution

Assuming the starting address of the program is 1000,

instruction i is at address 1000,

instruction i+1 is at address 1002

instruction i+2 is at address 1004,

instruction i+3 is at address 1006,

and the next address is 1008.

The instructions are executed in the sequence, i, i+1, i+2 and then i+3. When the execution of i+3 is going to start the value of PC gets incremented to 108. As the instruction i+3 is a branch instruction and it is given in the question that branch target is i, we need to update the PC from 1008 to address of i. That is, offset = 1000-1008 = -8.

Solution

Since there are 16 flags we need log(16) 4 bits.

There are 50 control signals, out of which group-1 has 30 and group-2 has 20.

It has to generate one or none of the 30 signals of group-1. So, we can use vertical microprogramming for these and use log(30) = 5 bits for them.

At most 20 of the group-2 can be active. So for them we need to use horizontal microprogramming here and need 20 bits.

So, in total for the control signals we need 5+20 = 25 bits.

Solution

In a direct mapped cache the physical address is divided into three fields as (TAG, LINE, OFFSET)

Cache block size is 64B, so OFFSET needs 6 bits.

Number of blocks in the cache = 2KB/64B = 32, so LINE number needs 5 bits.

The physical address is 16 bits long.

TAG bits = 16 - 5 - 6 = 5

The given word addresses are:

28 = (00000 00000 11100). So this is mapped to LINE number-0 in the cache. It is a miss.

144 = (00000 00010 010000) . It is mapped to LINE number-2 as(00010 is equal to 2 in decimal) in the cache. It is a miss.

2176 = (00001 00010 00000). This is also mapped to LINE number-2 (00010 is equal to 2 in decimal). But this is a different block as compared to the block for address 144, because the TAG bits for them are different. It is a miss.

2180 = (00001 00010 000100). This is mapped to LINE number-2 in the cache(00010 is equal to 2 in decimal). But this belongs to the same block as that of word address 2176, as they both have the same TAG bits also. So, this is a hit.

128 = (00000 00010 00000). This is mapped to LINE number-2 in the cache, but it is a miss and it has to replace the block which is already there.

2180 = (00001 00010 000100). This is mapped to LINE number-2 and it is a miss and has to replace the block corresponding to word address 128.

2185 = (00001 00010 001001). This is mapped to LINE number-2 and it is a hit as it belongs to the same block as that of address 2180.

Solution

In fetching the instructions, for every word we need one memory access.

1st instruction size = 1 word, to fetch this we need 1 memory accesses = 1*2 = 2 clock cycles

2nd instruction size = 2 words, to fetch this we need 2 memory accesses = 2*2 = 4clock cycles

3rd instruction size = 2 words, to fetch this we need 2 memory accesses = 2*2 = 4clock cycles

4th instruction size = 3 words, to fetch this we need 3 memory accesses = 3*2 = 6 clock cycles

5th instruction size = 1 word, to fetch this we need 1 memory accesses = 1*2 = 2 clock cycles

6th instruction size = 1 word, to fetch this we need 1 memory accesses = 1*2 = 2 clock cycles

For the execution,

1st instruction needs 1 memory accesses = 1*2= 2 cycles

2nd instruction needs 1 memory access+ 1 ALU access to add 100, R1 = 2cycles + 1 cycle = 3 cycles

3rd instruction needs 1 memory access and ALU access for ADD = 2+1 = 3 cycles

4th instruction needs 2 memory accesses as it uses indirect addressing mode to access the second operand and 1 ALU access for DIV= 2*2+1 = 5 cycles

5th instruction needs 1 memory access = 2 cycles

So total time needed = 2+ 4+4+6+2+2+2+3+3+5+2 = 35 cycles. Hence the answer is 35 cycles.

Solution

Output of MUX= I₀ Y’ + I₁ Y

X ⊗Y= X’Y’+XY

I₀=X’ , I₁= X

Solution

1024 = 2^10 =(1 0000 0000 00)₂.

Number of binary bits needed to represent 1024 is 11.

Solution

A XNOR B= AB+A’B’ ← AND-OR realization.

OR-AND realization can be easily converted into NOR-NOR realization.

= (A+B’)(A’+B) ← OR-AND realization

Solution

A Full Adder takes 3 inputs and produces two outputs, Sum and Carry.

A Decoder of size 3x2^3 is needed which takes 3 inputs and it has 23 output lines.

The ROM circuit for Full Adder is shown below.

Solution

The terms wx, xy’ and xz are Essential Prime Implicants.

wxy and wxz’ are implicants but NOT Prime Implicants.