Solution

Total distance =6010=600 km

New speed =600/4=150 km/hr

Increase in speed =150-60=90 km/hr

Solution

Speed in downstream =12+4=16 kmph

Solution

6:1=x:12

x=72

Solution

900 ㅡ 100

100 ㅡ ?

100 x 100 / 900=11.11%

Solution

We have, 16, 25, 36, 49, 64, 81 as perfect squares from 11 to 99.

Total numbers from 11 to 99 is 89.

Probability =6/89

Solution

Solution

The usual way to form comparatives and superlatives of adjectives is to add -er and -est: great, greater, greatest.

Solution

A pitcher is a handled container for holding and pouring liquids that usually has a lip or a spout.

Solution

Plants are green in color because they contain the green pigment chlorophyll.

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

cursor = cursor->link()

Here cursor-> link() moves the cursor to the next node and that was assigned to cursor itself, hence now it is pointing to the next pointer.

Solution

The elements pushed in the stack are d-o-o-d-l-e-s one after the other by first while loop.

In the 2nd while loop the TOP of the stack will be printed until the stack gets empty hence from top to ‘s’ to ‘d’ all characters will be printed. Hence ‘seldood’ will be the answer.

Solution

Solution

Here ptr is array not pointer.

Solution

#include <stdio.h>

typedef struct { int k; int l; int a[2]; } T;

typedef struct { int i; T t; } S;

T x = {.l = 43, .k = 42, .a[1] = 19, .a[0] = 18 };

// x initialized to {42, 43, {18, 19} }

int main(void)

{

S l = { 1, // initializes l.i to 1

.t = x, // initializes l.t to {42, 43, {18, 19} }

.t.l = 41, // changes l.t to {42, 41, {18, 19} }

.t.a[1] = 17 // changes l.t to {42, 41, {18, 17} }

};

printf("l.t.k is %d\n", l.t.k); // .t = x sets l.t.k to 42 explicitly

// .t.l = 42 would zero out l.t.k implicitly

}

Solution

Perfect Binary Tree: A Binary tree is a Perfect Binary Tree in which all internal nodes have two children and all leaves are at the same level.

18

/ \

15 30

/ \ / \

40 50 100 40

A Perfect Binary Tree of height h (where height is the number of nodes on path from root to leaf) has (2^h) – 1 node.

Solution

Pointer Variable can also Store the Address of the Structure Variable.

Pointer to Array of Structure stores the Base address of the Structure array.

Pointer Is Declared and initialized as —

struct Cricket *ptr = match

Here the address of match[0] is stored in pointer Variable ptr

Solution

In c,

a [1][2]

=*(a [1] +2)

=*(*(a+1) +2)

=2[a [1]]

=2[1[a]]

Now, a [1] [2] means 1*(4) +2=6th element of an array

staring from zero i.e. 21.

Solution

P: Yes, Topologically sort the vertices of G can be completed in linear time. It takes O(V+E) time.

Q: At the top level, roughly n work is done to merge all n elements. At the next level,there are two branches,each doing roughly n/2 work to merge n/2 elements. In total, roughly ‘n’ work is done on that level. This pattern continues on through to the leaves, where a constant amount of work is done on n leaves, resulting in roughly n work being done on the leaf level.

Solution

→ All pair shortest pair paths by repeatedly running Bellman Ford algorithm from each vertex will take O(V^4)

Solution

From the recurrence relation, we note that the branching factor a=5. At level 0, there is only one problem. For every subsequent level, the number of subproblems is multiplied by a. Therefore, at the 7th level of recursion, the total number of subproblems is given by:

a^7 = 5^7 = 243.

Solution

The first move occurs when the number of elements is 2^(k-1), and the ith move occurs when the number of elements is 2^(k-i). Total number of movements is k, and total cost is ∑0_j=k-1 2^j = 2^k-1= Θ(2^k) = Θ(n)

Solution

Finding the correct slot in a hash table takes O(1). In the worst case, all n items will hash to the same slot. Since chaining is implemented using a heap, inserting an element into the heap and heapify() takes O(log n) time.

Solution

Solution

The NFA does not accept string “ba” so (a+b)* is wrong. The NFA does not accept string “abb” so (a+b)*b is wrong. The NFA accepts epsilon so a*b is wrong. Hence a*+a*b is correct.

Solution

DFA in option b is not a DFA hence wrong. Option C DFA does not accept string “abab” hence wrong. Option D DFA does not accept “aba” hence wrong.

Solution

r₁: (a*b*)* = (a+b)*

The strings in L(r₂) ={ϵ, b, a, bb, aa, ba, bbb, aaa, bba,….}

The strings in L(r₃) ={b, ba, baa, baaa, baaaa, ….}

The strings which are common in L(r₂) and L(r₃) {b, ba, baa, baaa, baaaa, ….}

Hence the regular expression for (L(r₁) ∩ L(r₂) ∩ L(r₃) ) is ba*

Solution

L(G) = a*b* so L(G) is a regular language. Grammar G is not linear as in productions it has Two non terminals in RHS. L(G) is not cofinite as complement of L(G) is not finite. Similarly, If x ϵ L(G) and y ϵ L(G) then xy may or may not belong L(G) is also a true statement, as string “ab” belong to L(G) and string “aab” belong to L(G) but string “abaab” doesn’t belong to L(G).

Solution

L2 is complement of L1 is false statement. As L₁ (complement) will include two things.

1. “x” is a string <M,w> such that M is a TM and M don’t accept “w”

2. “x” is a string which don’t satisfy <M,w> condition. i.e., the “x” don’t contain encoding of any TM.

Hence, L₁ (complement) = { x | x ≠ <M,w> for any TM M and string “w” } U {M is a TM that doesn’t accept string “w” }

Hence L2 is not the complement of L1.

L₁ is recursively enumerable, as “M is a TM that accept w” is nothing but Halting problem of Turing machine, which is recursively enumerable but not recursive.

Although L₂ is not complement of L₁ , but L₂ is proper subset of complement of L₁, so we can use the idea of complementation.

If L₁ is recursively enumerable, but not recursive, so complement of L₁ cannot be recursively enumerable. According to theorem, if L and L’ both are recursively enumerable then L must be recursive. Since already it is proved that L₁ is not recursive, so as per theorem its complement cannot be recursively enumerable and hence L₂ (proper subset of complement) cannot be recursively enumerable language.

L1 ∩ L2 =∅ as no strings are common in L1 and L2.

Solution

A prefix of string s is any string obtained by removing zero or more symbols from the end of s. For example, ban, banana, and ϵ are prefixes of banana.

Prefix of string “GATE2021” are

{ϵ, GATE2021, GATE202, GATE20, GATE2, GATE, GAT, GA, G }

A suffix of string s is any string obtained by removing zero or more symbols from the beginning of s. For example, nana, banana, and ϵ are suffixes of banana.

Suffix of string “GATE2021” are

{ϵ, GATE2021, ATE2021, TE2021, E2021, 2021, 021, 21, 1 }

A subsequence of s is any string formed by deleting zero or more not necessarily consecutive positions of s. For example, baan is a subsequence of banana.

A substring of s is obtained by deleting any prefix and any suffix from s. For instance, banana, nan, and ϵ are substrings of banana.

Hence prefix(S) is a subset of substring(S).

Solution

The grammar is operator grammar (as it satisfy the operator grammar conditions)

1. No two non terminals together
2. No null production

The grammar is ambiguous as we have two parse trees for string “a+a+a”

The grammar has only one parse tree for string “a+a”

The grammar is not LL(1).

Solution

The grammar is CLR(1) and LALR(1) but not SLR(1). Hence grammar is unambiguous.

CLR(1) Canonical item set.

No state differs only from look ahead so this is CLR(1) as well as LALR(1)

Solution

a linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions and language generated by linear grammar is known as a linear language.

The grammar for L1 = { w | w ϵ {a,b}* & number of (a) in w = number of (b) in w}

S ⇾ aSbS | bSaS | ε

The grammar is not linear, hence L1 is not a linear language.

Solution

In L1 , since n <10 so comparison between “a” and “c” is finite and since n is finite so comparison m>n is also done by FA. So L1 is regular.

The NFA can be

L2 is based on viable prefixes. The entire SLR parsing algorithm is based on the idea that the LR(0) automaton can recognize viable prefixes and reduce them appropriately. So in LR(0) automata if we make reducing state as final state then the automata will accept all the viable prefixes. Hence L2 is a regular language

Solution

Do not enter a value in the foreign key field of a child table if that value does not exist in the primary key of the parent table.

Solution

If R has m tuples and S have n tuples, then the maximum size of join is: mxn

Solution

Schema I:

Registration (rollno, courses)

rollno → courses

· For the given schema Registration ‘rollno’ is a primary key.

· Left-side of the functional dependency is a superkey so, Registration is in BCNF.

Schema II:

Registrstion (rollno, courseid, email)

rollno, courseid → email

email → rollno

· From the given schema the candidate key is (rollno + courseid).

· There is no part of the key in the left hand of the FD’s so, it is in 2NF.

· In the FD email→rollno, email is non-prime attribute but rollno is a prime attribute. So, it is not a transitive dependency. No transitive dependencies so, the schema is in 3NF.

· But in the second FD email→rollno, email is not a superkey. So, it is violating BCNF.

· Hence, the schema Registration is in 3NF but not in BCNF.

Schema III:

Registration (rollno, courseid, marks, grade)

rollno, courseid → marks, grade

marks → grade

· For the schema the candidate key is (rollno + courseid).

· There are no part of the keys are determining non-prime attributes. So, the schema is in 2NF.

· In the FD marks → grade, both the attributes marks and grade are non-prime. So, it is a transitive dependency. The FD is violating 3NF.

· The schema Registration is in 2NF but not in 3NF.

Schema IV:

Registration (rollno, courseid, credit)

rollno, courseid → credit

courseid → credit

· The candidate key is (rollno + courseid).

· In the FD, courseid → credit, courseid is part of the key (prime attribute) and credit is non-prime. So, it is a partial dependency. The schema is violating 2NF.

Solution

Solution

Memory for storing single-level page table = number of pages × number of bits for representing frame.

No.of frames = 512MB/4KB => 17 bits. (so, 17 bits entry)

No.of pages = 2^32/2^12=>20 bits

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

So page table size = (20+4/8)*2^17 =384KB.

Solution

A total of 13 page faults occurs for Optimal page replacement algorithm.

Solution

The sufficient condition for no deadlock to occur : The sum of all max needs is < m+n.

Solution

770 = 512 + 256 + 2 = 00000011 00000010 = page 3, offset 2

Solution

The number of levels = ceil (48 - 13)/(13 - 2) = 4, and the split is 2, 11, 11, 11 and rest of 13 bits out of 48 bits is for offset.

Solution

Solution

Solution

Solution

Solution

1. Select 2 men from 8 i.e. in 8c2 ways.

Select 2 women such that they are not the wives of the selected men.i.e. in 6c2 ways.

Among the selected 4 we can have 2 combinations. Thus

8c2*6c2*2 = 28 * 15*2 = 840

Solution

Solution

Solution

Euler's formula: For any connected planar graph G V, E, the following formula holds V + F - E = 2 where F stands for the number of faces

v=4, e=6

4+F-6=2

F=4

Solution

Solution

Solution

Classification of linear systems:

Given a linear system in n variables, precisely on the the following three is true:

(a) The system has exactly one solution (consistent system).

(b) The system has infinitely many solutions (consistent system).

(c) The system has NO solution (inconsistent system)

Two systems of linear equations are called equivalent, if they have precisely the same set of solutions.

Solution

Solution

Each instruction has 32 bits. To support 200 instructions, the opcode must contain 8-bits. Register operand1 requires 7 bits, since the total registers are 100, Register operand 2 also requires 7 bits. So, 32 - (8+7+7) = 10 bits are left over for immediate operand. We know with 10 bits, the maximum possible value for the immediate operand is 2^10 - 1 = 1023.

Solution

Cache size = 16KB

Block size =32B

Total no. of Blocks in the cache =16KB / 32B = 512

Memory block Number = Byte address / Block Size = 4800/32 = 150

In Direct Mapped cache,

Cache block Number = Memory block Number mod(Total Number of block in cache)

= 150 mod 512 = 150

Solution

Consider a k-way set associative cache with n blocks and each having size m words.

Number of sets in the cache = n/k

Cache size = n*m words

We know in a set associative cache the physical address is divided into 3 parts as (TAG, SET, OFFSET).

Let number of TAG bits in the physical address = t

SET = log(n/k) bits

OFFSET = log(m) bits

The TAG directory size = n*t bits

When the block size is reduced to half the latest block size = m/2 words

Since it is given that the cache size remains the same, so the number of lines in the cache will be doubled. So the number of sets in the cache also gets doubled.

The new number of lines n’ = 2*n

The new number of sets = 2*n/k

But the number of bits in the tag field of physical address will remain the same because even though the OFFSET bits reduces by 1, the SET number bits will increase by 1. So the second statement is true.

The latest TAG directory size = n’ * t = 2*n*t, this is double the initial TAG directory size. So the 1st statement is false.

Keeping the cache size and block size same, if the associativity is doubled from k to 2*k:

OFFSET will remain the same log(m) because the block size is unchanged.

The initial number of sets = n/k, the latest number of sets = n/(2*k)

SET = log(n/(2*k)) = log(n/k) - 1, so the SET number bits will reduce by 1.

So, correspondingly the number of bits in the TAG field of the physical address increases by 1. So the 3rd statement is true.

Also the overall TAG directory size will also increase. So, the 4th statement is false.

Solution

Instruction is of size 32-bits.

All possible binary combinations = 2^32

There are 32 registers, so no. of bits needed to identify a register = 5

I-type instruction has (Opcode + Register-1 + Register-2 + 7 bit immediate value).

There are 64 distinct I-type instructions.

All the binary combinations possible with the I-type instructions are = 64 * 2^5 * 2^5 * 2^7= 2^23

R-type instructions have 1 register operand, which takes 5 bits and two 8-bit immediate values.

R-type instruction has (Opcode+Register-1+8-bit immediate value+8-bit immediate value).

Let x be the number of R-type instructions.

All the possible binary combinations of R-type instructions = x * 2^5 * 2^8 * 2^8 = x * 2^21

The sum of I-type and R-type binary combinations should be equal to 2^32, as the instruction is 32 bits long.

x*2^21 + 2^23 = 2^32

2^21 (x+2^2) = 2^32

x+4 = 2^11

x = 2048 - 4 = 2044

Solution

Consider this pipeline

(V1) --> (V2) --> (V3)

Let the stage delay of 1st stage V1 be X, so V1=X

We are given V1 = 4*V2/9,

4 * V2 / 9 = X

V2 = 9*X/4

Similarly, 3*V3 = X

V3 = X / 3

The pipeline now becomes,

(X) --> (9X/4) --> (X/3)

Largest stage is stage 2 with 9X/4 seconds time required. This is the speed of the processor.

Frequency given is 4GHz, which means the processor can execute 4Giga clock cycles.... in 1 second.

Or

1 clock cycle .....in (1/4Giga) secs

But we know that stage latency of the largest stage in the pipeline limits the time of 1 clock cycle. Hence

9X/4 = 1 clock cycle = (1/4Giga) secs

X =(4/9) * (1 / 4Giga) secs = (1 / 9Giga) secs

Now largest stage that is stage 2 is split into 3 stages of equal latency , so new pipeline is

(X)-->(3X/4)-->(3X/4)-->(3X/4)-->(X/3)

Now largest stage is X seconds

Hence,

In X seconds we can do 1 clock cycle

In 1 second we can do 1/X clock cycles

But X = (1/9Giga) seconds

So in 1 second we can do 1/X = 9 GHz.

Solution

The term xz is an implicant because xz is a product term.

The implicant xz is a prime implicant because xz is not completely covered by any other prime implicant.

The implicant xz is not an essential prime implicant because xz is not covering any minterm which is not covered by any other prime im implicant.

Solution

G(x,y) assumes true value whenever F(x,y) does. So, G covers H.

Solution

M = 111100011000

Append “0” at LSB

ADD -1

SUB -2

Solution

f(w,x,y,z)= wx’ + wy’ + yz’

Expand the above expression such that each term contains the variables “y” and “z”, either in true form or complement form.

f(w,x,y,z)= wx’ + wy’ + yz’

= wx’(y+y’)(z+z’) + wy’(z+z’) + yz’

= wx’yz + wx’yz’ + wx’y’z + wx’y’z’ + wy’z + wy’z’ + yz’

= wx’yz + (wx’+1)yz’ + (wx’+w)y’z + (wx’+w)y’z’

= wx’yz + (wx’+1)yz’ + (wx’+w)y’z + (wx’+w)y’z’

= wx’yz + yz’ + w y’z + w y’z’

I₃= wx’ , I₂= 1, I₁= w, I₀= w.

Solution

The number of minterms of the function f(x,y,z) is k= 4.

Number of input combinations= 2^3= 8.

Number covering functions= 2^(8-4)= 24 = 16.