Solution

In the given word “INDEPENDENCE”, we treat the vowels “IEEEE” as one letter.

Thus, we have NDPNDNC (IEEEE).

→ Now, we have to arrange 8 letters, out of which N occurs thrice and D occurs twice.

Solution

Solution

Solution

Solution

Solution

Solution

Scrumptious meaning

(of food) - very tasty, delicious

(of Person) - very attractive

Solution

The questions could be as follows

When do you have to go to school?

Why did you wear a raincoat?

How did you go to school?

Whose raincoat was that?

So ‘Why’ would be the right word to use to get the answer ' because it was raining'.

Solution

Ladder and stairs refer to something used for climbing. So what can be used other than feathers to fly? The answer is Wings. Feathers and Wings refer to something used for flying.

Solution

The jowl is the fleshy part of the lower jaw, so the idiom cheek-by-jowl is similar in meaning to cheek-to-cheek - that is, it means very close together.

Solution

A minimum spanning tree has (V – 1) edges where V is the number of vertices in the given graph.

Solution

Since there is no break statement, all the statement after case’Q’ are executed.

Solution

strlen(arr) give the length of the string, that is 4 and sizeof(arr) gives the size of array arr

that is 10.

Solution

Print is a recursive function that has one parameter which is an integer value

called a. The function prints a & followed by a-1 number of @ symbols.

Solution

Postorder Traversal -ECKAHBGDF

Since the tree is:

Solution

Solution

For a value of i, the for loop iterate from i, then i-1, i-2… 0, and hence it will do sum of total i+1 number

Example:

i=3

sum=0+a[3]

sum=0+4=4

i=2

sum=4+a[2]=4+3=7

i=1

sum=7+a[1]=7+2=9

i=0

sum=9+a[0]=9+1=10

∴ For i=3

Sum will sum up a total of 4 elements starting from the 0th index of array.

Solution

A[20, 10]

W = 4 words

Base (A) = 100

A [11, 5] → in row major m x n

Location of a[i][j]=>

loc [ a [i] [j] ] = base (a) + w [n [i – lbr] + ( j – lbc)

Where,

W = Number of bytes occupied by each element

N = Number of columns

lbr = lower bound of row

Lbc = lower bound of column

lbr=lbc = 0 by default and as it is not mentioned in question we will consider default value

= 100 + 4 [10 (11) + 5]

= 100 + 4[110+5]

=100 + 115 *4

= 560

Solution

Prim’s algorithm → It solves the MST and follows a greedy approach.

Floyd Warshall algorithm → It solves the all pair shortest path problem and follows dynamic programming.

Huffman coding → It solves the compression problems and follows the greedy approach.

Dijkstra’s algorithm → It solves the single source shortest path problem and follows a greedy approach.

Solution

Apply the quick sort algorithm on the given letters

Given the last element as pivot.

So, here ‘E’ is the pivot element.

After first pass the position of pivot element E is 3.

Solution

The number of spanning trees possible for n vertices is = n^(n-2)

=5^3

=125

Solution

If you're using matrix format then we can find the easy way to get the solution.

We can also follow the standard format but in this question, the given table is easy to find the solution.

From above solution

Order is A B C F H D E G

Total cost is 28.

Solution

I. T(n) = 2T(n/2) + nlogn

Apply master’s theorem

a = 2, b= 2, k = 1, p = 1

case a = b^k and p >= 0

T(n) = O(n log^2 n)

II. T(n) = 16 T(n/4) + n

Apply master’s theorem

a = 16, b = 4, k = 1 p = 0

case a > b^k

T(n) = O(n^2)

III. T(n) = 6 T(n/3) + n^2logn

Apply master’s theorem

a = 6, b= 3, k = 2 p = 1

case a<b^k and p>= 0

T(n) = O(n^2logn)

IV. T(n) = T(n /2) + n/logn

Apply master’s theorem

a = 1, b = 2, k = 1, p = -1

case a<b^k and p<0

T(n) = O(n^k)

= O(n)

Solution

If n is odd then initialize min and max as the first element.

If n is even then initialize min and max as minimum and maximum of the first two elements respectively.

For the rest of the elements, pick them in pairs and compare their maximum and minimum with max and min respectively.

→ Minimum number of comparisons required to find the min and max element from the n elements in the array where n is odd 3(n-1)/2

→ Minimum number of comparisons required to find the min and max element from the n elements in the array where n is even (3n/2)-2

→ Time complexity to find maximum element in O(n) using binary search tree, if the tree is right/left skewed.

→ If we are merging two sorted lists of sizes m and n into a sorted list of size m+n then how many comparisons are required in worst case is m+n-1

Solution

L1={ϵ,aa, aaaa, aaaaaa, ……….}

A prefix of string S is any string obtained by removing zero or more symbols from the end of S. For example, GATE, GAT, and ϵ are prefixes of GATE. In Proper prefix, we exclude ϵ and string S, i.e., proper suffix we consider only non trivial prefix. For ex: {GAT, GA, G } are the proper prefixes of the string “GATE”. Hence

L2={a, aa, aaa, aaaa, …………….}

So L1 ⊂ L2 (because L1 contains ϵ also) and L2 ⊂ L1 are false. But L1 U L2=∑* =a*

Solution

The strings in language are {abbabb, abbaababb, abbaabaababb,………..}

The min DFA is

Solution

Solution

Solution

If M is LBA then L(M) is CSL which is recursive also, So M accept or reject “w” is decidable.

But whether L(M) is empty (L(M)= Φ) is undecidable for CSL.

Solution

The objects created using malloc and calloc function get allocated space in heap memory. Hence the statement “The objects created using malloc and calloc function get allocated space in stack memory” is false. Rest all statements are true.

Solution

(b*c) and (e-f) are at the lowest level so they have highest priority. Hence (a-(b*c))-(d*(e-f)) is the correct expression.

Solution

None of the regular expressions generate the string “bab” hence no one is correct. The correct regular expression which generates language containing all strings with even number of b’s and exactly one “a” is:

(bb)*a(bb)* + (bb)*bab(bb)*

Solution

G2 is LL(1) hence it is unambiguous. Since every LL(1) is CLR(1) also hence G2 is CLR(1) also.

LL(1) parsing table for G2

Follow(B)=Follow(A)= {x,$}

G1 is not LL(1) grammar as it has left factoring.

Solution

The correct SDT is

E→ E+T { print ‘+’ }

E→T { }

T→ T*F { print ‘*’ }

T→F { }

F→(E) { }

F→ id { print id }

For example: For input a+b*c, the given SDT produce output abc*+ (which is the postfix of the given expression).

Solution

A common use of the check clause is to ensure that attribute values satisfy specified conditions, in effect creating a powerful type system.

Solution

Unknown means NULL value.

• TRUE OR NULL=TRUE
• FALSE OR NULL=NULL
• NULL OR NULL=NULL

Solution

Given relation schema r(A, B, C, D, E) and FD set:

{A → BC, CD → E, B → D, E → A}

Given r is to be decomposed into r₁(A, B, C) and r₂(A, D, E).

FDs under r₁(A, B, C) will be {A → BC}.

So, the key for r₁ is {A}.

FDs under r₂(A D, E) will be {E → A}. So, the key for r₂(A, D, E) is ED.

∴ Decomposition of r(A, B, C, D, E) into r₁(A, B, C) and r₂(A, D, E) is lossless since the common attribute of r₁ and r₂ i.e., A is key for r₁.

So, I is correct.

Here the final FD set we obtained after decomposition is { A→BC, E→A}.

The decomposition is not FD preserving since the FDs CD→E and B→D which are there in original FD set are not covered by final FD set ( (CD)+ = CDEAB in original FD set but in final FD set (CD)+ = CD and also (B)+ in original FD set is BD but (B)+ in final FD set is B). Therefore we can say that given decomposition is not FD preserving.

So II is not correct.

Solution

Option (a) → 1, 10 will come if transactions are executed in order T₁, T₂, T₃

Option (b) → 2, 5 will come if transactions are executed in order T₁, T₃, T₂

Option (c) → 7, 0 will come if transactions are executed in order T₃, T₂, T₁

Option (d) → 12, 0 will come if transactions are executed in order T₃, T₁, T₂

Solution

Atomic operations like compare and swap and test and set are implemented in hardware.

The user cannot disable interrupts, the kernel has to disable interrupts.

SRTF is not suited for hard real-time systems.

RR scheduling may have high context switch overhead leading to less throughput compared to FCFS.

Solution

LRU does not suffer from Belady's anomaly. Therefore, an increase in memory size increases the hit rate.

A TLB is used for faster address resolution. It is independent of the cache mapping technique

Solution

Each page must certainly generate a fault (the first time that the page is referenced). Thus, the minimum is n. The worst thing that could happen is that every single reference generates a page fault. Thus, the maximum is p.

Solution

Threads share the code and data segments and the heap, but they don't share the stack.

The fork() system call creates an exact copy of the parent process virtual address space.

All the instructions in the kernel's code are privileged. Therefore, the instructions are run in kernel mode.

Solution

The data 2000 is returned when both the processes are executed serially ie, P1 followed by P2. Also, 0 can be returned if p2 executes x=data, and then p1 sets ready =1, then x contains the old value of data (0) which is then returned.

Solution

Speed of light in fiber and copper = 200 km/msec.

For a 20-km line, the delay is 100 μsec one way and 200 μsec round trip.

A 1 KB packet has 8192 bits.

If the time to send 8192 bits and get the acknowledgement is 200 μsec, the transmission and propagation delays are equal.

If B is the bit time, then

8192 = 2 x 10-4 sec.

Data rate, 1 / B = 40 Mbps. (approx)

Solution

Solution

Solution

a - 3, b - 4, c - 1

Solution

• d, a, b, c, f, b, a, g is a path, but it is not a simple path, because the edge {a, b} occurs twice in it.
• c, g, a, d, g, f has repeated vertex, its not a path.

Solution

Given that ‘A’ is a square matrix observing the condition

will result

which is a scalar matrix.

Solution

Solution

Draw D ₃₆ , it has 12 edges

Solution

Let's solve this through integration by parts

Solution

If |A|=m, |B|=n

Function from A➝B are

1. If m<n then n!/(n-m)!
2. If m=n then m!
3. If m>n then ‘0’ then one-one function.

If there are no elements in B, then no element in A can be mapped, thus its not one one, infact its not even a function

Solution

Solution

Maximum Matching: A matching, M, of G is a subset of the edges E, such that no vertex in V is incident to more than one edge in M. Intuitively we can say that no two edges in M have a common vertex.

In the above graph the maximum matching can be { (2,3), (4,8),(5,7) }.

Note: if you consider (1,3) you should eliminate (2,3) from above matching. Similarly with other edges.

Solution

Since the memory is 16K X 16, the word size is 16 bits long. So we have 16K words in the memory. To access one word we need 14 bits as 16K = 2^14.

Solution

The overflow flag in any operation is decided by the XOR operation of carry-in and carry-out from the most significant bits.

Solution

In general in the pipeline we assume each instruction takes 1 clock cycle.

But here it is given there are 50% ALU instructions, 20% branch instructions and 30% memory instructions and the corresponding clock cycles needed are also given.

So the updated CPI = 0.5*3+0.2*4+0.3*5 = 1.5+0.8+1.5 = 3.8 cycles.

So, the time taken for one instruction = CPI * clock time = 3.8*12ns = 45.6ns

From this we can calculate the throughput as = 1/(45.6*10^-9) = 21.93 MIPS

Solution

Main memory is 256MB in size. So the physical address is 28 bits long.

Block size is 1KB, block offset = 10 bits as it is a byte addressable memory.

Cache size = 64KB

Number of blocks in the cache = 64KB/1KB = 64 = 2^6

It is a direct mapped cache, so we need 6 bits to identify a cache line.

In the physical address we need 6 bits for the LINE number.

Since in all the options we are asked about LINE numbers of the given addresses, we need to find the LINE number to which each of the given physical addresses is mapped to.

In the direct mapped cache the physical address is divided into 3 parts as (TAG, LINE, OFFSET).

The least significant 10 bits are used as OFFSET and the next significant 6 bits are used as LINE number and the remaining 12 bits are used as the TAG bits.

P1 = 0x45246B4, can be written in binary as (0100 0101 0010 0100 0110 1011 0100). From this the highlighted six digits (0100 01) represent the LINE number.

P2 = 0x2648B48, can be written in binary as (0010 0110 0100 1000 1011 0100 1000). From this the highlighted six digits (1000 10) represent the LINE number.

P3 = 0x82A8A1C, can be written in binary as (1000 0010 1010 1000 1010 0001 1100) . From this the highlighted six digits (1000 10) represent the LINE number.

P4 = 0x36E5380 can be written in binary as (0011 0110 1110 0101 0011 1000 0000). From this the highlighted six digits (0101 00) represent the LINE number.

So P2, P3 are mapped to the same cache LINE.

Solution

It was given in the question that each array element occupies 4 words and each cache block is 8 words size. So there are 2 array elements in one cache block. Whenever there is a cache miss one entire cache block is loaded from the main memory into the cache. So 2 array elements are loaded into the cache at a time. When the first element A[0] is not found in the cache, then A[0] and A[1] are loaded into the cache. Hence when accessing A[1] there will not be a cache miss because it is already in cache.

The given array has 111 elements. It requires a total of 56 blocks to fill all the array elements where 55 blocks have two elements each and the last block is filled with only a single element because the array has an odd number of elements.

In the given statement A[i] = A[i]*4 each element A[i] is accessed twice, once for reading and when the value of A[i]*4 is calculated then the result is stored back into A[i].

Within one cache block holding 2 elements the total memory accesses are 4 as below:

A[0]-read , A[0]-write

A[1]-read , A[1]-write

Out of these 4 accesses only A[0]-read is a miss and all the remaining 3 accesses are hits.

This is the case for the 55 blocks. So, total accesses for the 55 blocks = 55*4 = 220.

There are 55 misses for the 55 blocks and the number of hits for the 55 blocks= 55*3 = 165

For the last block since it holds only a single element it requires only 2 accesses one for reading and the other for writing it. In these two accesses the read operation is a cache miss and write operation is a cache hit. So the overall cache hits = 165 hits for the 55 blocks +1 hit for the last block = 166.

Number of cache accesses = 220 accesses for the 55 blocks + 2 accesses for the last block= 222.

Hit ratio = 166 / 222 = 0.7477, in % it is 74.77%

Solution

(9.A)₁₆ - (1000.0001)₂

=(9.A)₁₆ - (8.1)₁₆

= (1.9)₁₆

Solution

Level 1: 64/4= 16

Level 2: 16/4= 4

Level 3: 4/4= 1

Total+ 21

Solution

(2124)₅ = 2*5^3 + 1*5^2 + 2*5^1 + 4

= 250+25+10+4

= (289)₁₀.

Log_{2) ^}289 = 8.17.

Minimum number of binary bits needed to represent 289 is 9.

Solution

f(g(x))= f(x’)

= (x’)’ + 1

= x+1.

g(f(x))= g(x’+1)

= (x’)’ -1

= x-1

Solution

T= 1/F

= 1 / (0.25GHz)

= 4 ns