Solution

Solution

Since the numbers are given in the form of ratio that means, their common factor have been cancelled.

Each one’s common factor is HCF, here H.C.F = 12

The numbers are 12, 24, 36.

Solution

Other than 72 remaining all are perfect squares.

Solution

Solution

Solution

Cost price = Rs. 750

Profit = 20% of 750 = Rs. 150

Selling price = 750 + 150 = Rs. 900

Solution

Application is the action of putting something into action.

Supplication is the action of asking something humbly.

Germination is the development of a plant from a seed.

Segregation is the action of setting something or someone apart from others.

Solution

Beating around the bush means not speaking precisely or to the point.

Over the moon means extremely happy or

delighted.

Bite the bullet means to get something over because it's inevitable.

Break a leg means good luck.

Solution

In present tense the sentence is ' The house upon the rock stands firm.'

In the past tense the sentence is ' The house upon the rock stood firm.'

Solution

Solution

const keyword in c doesn’t make any variable as constant but it only makes the variable as read only. With the help of a pointer we can modify the const variable. In this example pointer p is pointing to the address of variable x. In the following line: int * const p=&x; p is constant pointer while content of p i.e. *p is not constant. *p=2*x put the value 50 at the memory location of variable x.

Solution

If you execute the above for loop in an executing C code and print the values of i then the for loop will print the values in following sequence:

100, 33, 11, 3, 1

The 3rd one is 11.

i=i/3

First iteration i=100 will be printed as it is.

100/3 = 33 …….. 2nd iteration

33/3= 11 ……….3rd iteration

11/3= 3 ………...4th iteration

3/1 ……………..5th iteration

Solution

The BST after inserting the elements looks like:

Solution

/* function:bitcount: count 1 bits in x */

// function(3) and function(10) both will return value as 2 hence if is True

If x is odd, then (x-1) has the same bit representation as x except that the rightmost 1-bit is now a 0. In this case, (x & (x-1)) == (x-1).

If x is even, then the representation of (x-1) has the rightmost zeros of x becoming ones and the rightmost one becoming a zero. Anding the two clears the rightmost 1-bit in x and all the rightmost 1-bits from (x-1).

Solution

Among the given choices, queue is the most appropriate for BFS, stack for DFS and heap

for sorting.

Solution

#include <stdio.h>

int lower(int c) {

return (c >= 'A' && c <= 'Z') ? EXPR : c;

}

int main() {

printf("%c\n", lower('A'));

return 0;

}

The ternary expression’s result is returned by lower function.

(c >= 'A' && c <= 'Z') ? EXPR : c;

Ternary operator works like the following:

Condition ? return_this_if_condition_is_true : return_this_if_condition_is_false

Condition here says that if c is greater than ‘A’ (or c’s ASCII is greater than ASCII of ‘A’) and c is less than ‘Z’ => This clearly means that if the character c is Upper case then the LHS part of : will be returned. If the condition is false then c itself is getting returned. From this we can assert that the EXPR is the expression which converts Uppercase character to lower case character.

How to do that?(converting Uppercase character to lower case character)

Eg. c==’A’

To convert ‘A’ to ‘a’ if

c + ’a’ - ‘A’ // this will give we result as ‘a’

Hence b option is correct.

Solution

A string in C is a contiguous sequence of characters in memory, terminated by and including a null character. The characters in strings are accessed through the char data type. There are also wide strings whose characters are accessed through wchar_t objects.

/* The following three lines each define a string containing only a null character */

char *a = ""; /* a points to an empty string */

char b[1] = {0}; /* b is an array of 1 char, containing an empty string */

char c = 0; /* &c points to an empty string */

Solution

Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u v, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG.

3 can not come before 1 and 2

Solution

Based on the example graph, we can claim that both statements are correct.

Solution

A directed graph is strongly connected if there is a path between all pairs of vertices. A strongly connected component (SCC) of a directed graph is a maximal strongly connected subgraph.

The strongly connected components are

1. Time complexity is O(V+E) because using DFS
2. We can find strongly connected components using the Kosaraju algorithm and Trojan’s algorithm. The kosaraju algorithm and Trojan’s algorithm are not required for GATE.

Solution

As per the inversion definition, we have to consider the

21 > 7, 21 > 15 , 21 > 18 → 3 inversions

41 > 22, 41 > 15, 41> 18, 41 > 25 → 4 inversions

22 > 15, 22 > 18 → 2 inversions.

15, 18, 25, 58, 103, 203 are in ascending order, so we won’t get single inversion from these elements.

Total= 3 + 4 + 2

= 9

Key points in inversion array:

1. If the array is already sorted then the inversion count is 0.

2. If the array is sorted in reverse order that inversion count is the maximum.

Time Complexity: Using divide and conquer we will get O(n log n).

Space Complexity: No extra space is required for this algorithm.

Solution

The recurrence relation to get minimum number of scalar multiplications are

We can get a maximum of 5 possible parentheses using standard dynamic programming method (or) using catalan numbers.

Given the matrices A,B,C,D

Assume the dimensions of A=d₀×d₁, etc..,

Below are the five possible parenthesizations of these arrays, along with the number of multiplications:

(AB)(CD) → d₀d₁d₂ + d₂d₃d₄ + d₀d₂d₄ → 300 + 378 + 540 = 1218

((AB)C)D → d₀d₁d₂ + d₀d₂d₃ + d₀d₃d₄ → 300 + 420 + 630 = 1350

(A(BC))D → d₁d₂d₃ + d₀d₁d₃ + d₀d₃d₄ → 210 + 350 + 630 = 1190

A((BC)D) → d₁d₂d₃ + d₁d₃d₄ + d₀d₁d₄ → 210 + 315 + 450 = 975

A(B(CD)) → d₂d₃d₄ + d₁d₂d₄ + d₀d₁d₄ → 378 + 270 + 450 = 1098

→ The minimum number of scalar multiplications are 975 and optimal parenthesization is A((BC)D)

→ The maximum number of scalar multiplications are 1350 and optimal parenthesization is ((AB)C)D

Solution

Step 1:

Step-2:

Step-3:

110100 → M

1100 → I

11011 → T

110101 → H

Solution

The quicksort gives worst case time complexity for two scenarios.

1. If all the elements are in sorted order
2. All elements are having the same number.

According to above scenarios t₁ gives average case time complexity and t₂ also gives worst case time complexity.

→ It would be t₁< t₂

The best and average case time complexity of quick sort is O(nlogn). The worst case time complexity is O(n^2).

Solution

(AB)+ = ABCD

AB is the candidate key. Hence, AB, ABC are super keys.

Solution

The given SQL query can be replaced by “Select name, course_id from instructor natural join teaches”

Solution

• Transaction Ti needs to be undone if the log contains the record <Ti start> but does not contain either the record <Ti commit> or the record <Ti abort>.
• Transaction Ti needs to be redone if log contains record <Ti start> and either the record <Ti commit> or the record <Ti abort>.

Solution

Indexing will be an occupation field because the occupation field lexicographically sorted will be 4, 5, 2, 1, 3.

Solution

Regular expression for even number of a’s (greater than zero) is = aa(aa)*

Now (L*)* = (aa (aa)*)* = (aa)*

The reason is in (aa(aa)*)* if we suppose inner (aa)*=ϵ then (L*)*= (aa)* and (aa)* generates every string present in (aa(aa)*)*.

The minimal DFA is

Solution

If S is the only final state then FA accepts only empty string (as initial state is final state), hence minimal DFA requires two states.. If F is the final state then FA accepts (0+1)*, hence minimal DFA requires only one state..

If F is final state then

The reversal of FA is

Both accepts (0+1)*.

Solution

The grammar is in GNF form. The given CFG is equivalent to

S ⟶ aSbb | a

Which generates the language L={a^(n+1) b^2n | n>=0}. Please note grammar generate string “a” also, hence the option that the grammar generates the language L={a^(n+1) b^2n | n>0} is wrong as it generates minimum string “aabb”. The grammar is not in CNF form.

Solution

A= (a, aab, baaa) -> assume A1= a , A2 = aab, A3= baaa

B= (aaa, bba, aa) -> assume B1= aaa, B2= bba, B3= aa

Option A = (2,3,1)

If we write A2 A3 A1 = aab baaa a

B2, B3, B1 = bba aa aaa

Since the sequence 2,3,1 doesn't match for A and B hence (2,3,1) is not a solution for PCP

Option B: = (2,1,3) It is also not matching

Option C: (1,2,3)

A1 A2 A3: a aab baaa

B1 B2 B3: aaa bba aa

a aab baaa = aaa bba aa

The sequence (1,2,3) matches for A and B hence (1,2,3) is a solution for PCP.

Solution

Solution

As we know (a+b)* = (a*b*)* = (a*+b*)*

R1=R2, both generate same set of strings and both are equal to (a+b)*

R1: (a*b*b*)*

Consider second b*= ϵ

So R1= (a*b*)* which is equal to (a+b)*

R2= (a*b*+b*)*

Consider first b*= ϵ

So R2=(a*+b*)* which is equal to (a+b)*

Solution

G2 is LL(1) hence it cannot be ambiguous

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

Solution

Grammar G is ambiguous as for string “t” it generates two parse trees. Hence it cannot be LL(1) or LR(1).

The two parse trees for string “t” are:

Solution

The first two lines compute the value of a[i] and assigns in temporary t₂. Line 3 makes t₂ an actual parameter for the call of f on line 4. Line 4 calls the function “f” where “1” means number of parameters (here parameter is a[i]) and line 5 multiply 2 into value return by f(a[i]) and line 6 assigns the value of line 5 in “n”.

hence, it is n=f(a[i])*2

Solution

The given grammar is not LL(1) as productions

A-> d and A->SB will go in the same cell of LL(1) parsing table.

The given grammar is not LR(0) as the production B → ϵ will cause shift -reduce conflict in state I₁.

But the given grammar is SLR(1) as B → ϵ will go in follow(B)= {a} only, so there will not be any SR conflict.

Given grammar has productions S->Aa and A -> SB, so it has indirect left recursion.

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 entries = 2^32/4KB = 2^20.

So page table size = (17/8)*2^20 = 2.215MB

Solution

EMAT = (0.75 × (50+2)) + (0.25×(2+50+50)) = 64.5 ns

Solution

Maximum number of units of resource R that ensures deadlock = 1 + 1 + 1 = 3. Therefore, the minimum number of units of resource R that ensures no deadlock = 3 + 1 = 4.

Solution

0 (Miss), 1 (Miss), 0(Hit), 2 (Miss), 3 (Miss), 3(Hit), 0(Hit), 2(Hit) = 4 page faults

Solution

Solution

By binary exponential backoff mechanism, after the collision, if both stations try to send the same frame, their probability of collision will decrease but not guaranteed that collision will never happen. Binary exponential backoff mechanism used in CSMA protocol.

Solution

Since in circuit-switched network before sending any information connection is established. So information about the whole network is needed for starting data transfer.

Solution

• Count to infinity problem occurs when the network gets disconnected but due to updation problem i.e. Before updation of correct information of disconnected node, some other node trying to send data through the disconnected node. So, count to infinity problem cannot happen in the connected network.

• Path vector routing is an enhancement to distance vector routing since instead of relying on the cost reaching a given destination to determine whether each path available is loop-free or not, we rely on the analysis of the path to reach the destination to learn if it is loop-free or not.

Solution

Solution

All the required are 3 digit numbers.

To get distinct digit numbers

FIrst position can be filled with {1-9} in 9 ways as 0 cant be in the first position from left

Second position can be filled with 9 digits(excluding the first digit )

Third position can be filled with 8 ways ( excluding the first two digits)

Intotal 9*9*8 = 648 numbers with distinct digits

Solution

Solution

Solution

Solution

Note: Its given identical groups, so whenever its like (5,1,1), there is chance of a peson repeating in second and third group., thus we divide the 7! /5! With 2!

Solution

Solution

Solution

Two statements are logically equivalent if, and only if, their resulting forms are logically equivalent when identical statement variables are used to represent component statements.

Two statement forms are logically equivalent if, and only if, their resulting truth tables are identical for each variation of statement variables.

All the options are part of Logical equivalences.

Associative law:

(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)

(p v q) v rp v (q v r)

De Morgan’s Law:

~(p ∧ q) ≡ ~p ∨ ~q

~(p ∨ q) ≡ ~p ∧ ~q

Absorption

p ∨ (p ∧ q) ≡ p

p ∧ (p ∨ q) ≡ p

Distributive

p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)

Solution

In a set associative cache the address is divided as three parts...(TAG+SET+OFFSET).

In this question it is given that there are 8192 blocks in the main memory and each block is 128 words size,

so size of the main memory = 8192*128 words = 2^13 * 2^7 = 2^20 words.

So the physical address is 20 bits long.

Block size is 128 words = 2^7 words, OFFSET needs 7 bits.

Cache contains 256 blocks and it is a 4-way set associative cache, so no. of sets = 256/4 = 64= 2^6 sets. So the SET field in the address needs 6 bits.

Out of 20 bits of the address TAG bits = 20 - 6- 7 = 7 bits.

Solution

Instruction Count = 500

CPI = 1.8

Clock Rate or frequency = 2 GHz = 2*10^9

Clock Cycle Time = 1/frequency = 1/(2*10^9)= 0.5 ns

Execution Time of the program = No. of instructions * CPI * Clock cycle time

= 500 * 1.8 * 0.5 ns = 450 ns

Solution

For 4 stages, non-pipelining takes 4 cycles.

So, CPI in non-pipeline = 4 clock cycles.

There were 2 stall cycles for pipelining for 40% of the instructions

So stall frequency = 0.4

CPI-pipeline = (1 + stall Freq * stall cycles) clocks

= (1 + 0.4 * 2) clocks

= 1.8 clock cycles

Speed up =CPI Non-pipeline/CPI Pipeline= 4/1.8 = 2.22

Solution

It is given the hard disk speed is 1000KB/sec

So 2KB can be transferred by this disk in (2/1000)s = 2ms. This is also called data preparation time as the disk keeps the data ready in the I/O buffer for DMA to transfer.

Total cycle required for locking and handling of interrupt after DMA transfer control =(500+200) clock cycle = 700 clock cycles

The speed or frequency of the given processor is 20MHz, so each clock cycle time = 1 / (20 * 10^6) = 0.05 microseconds

Since DMA needs 700 clock cycles to transfer data, time needed= (700 * 0.05 ) = 35 microseconds

Here nothing is mentioned whether DMA works in burst mode or cycle stealing mode, so by default we consider it as burst mode.

In burst mode the fraction of processor time consumed by the disk = DMA transfer time / (DMA transfer time + data preparation time)

= 35 microseconds / (35 microseconds + 2 milliseconds)

= 35 microseconds/ (35 microseconds+2000 microseconds)

= 35 / 2035 = 0.01719. In percentages, it is 1.72%

Solution

Number of sets in cache = 16.

The main memory block numbered 250 will be mapped to set number (250 mod 16) = 10. Since it is a 4-way set associative cache, there are 4 blocks in each set. It is given in the question that the blocks in consecutive sets are sequenced. It means for set-0 the cache lines are numbered 0, 1,2,3 and for set-1, the cache lines are numbered 4,5,6,7 and so on. As the main memory block 250 will be mapped to set (250 mod 16), it will be any one of the cache lines from (250 mod 16)*4 to (250 mod 16)*4+3. So, (250 mod 16)*4 = 40 and (250 mod 16)*4+3 = 43.

Hence the main memory block number 250 will be mapped to set number 10, and within that set the cache line numbers are 40, 41, 42 and 43.

So the main memory block 250 can be mapped to any one of the cache line numbers in 40 to 43.

Solution

2x^2 + 1 · x + 2 = 1 × 8^2 + 5 × 8 + 3

2x^2 + x = 105

Roots = 28/4 or – 30/4

= 7 or – 7.5

Base can never be –ve or decimal point.

∴ Base x is 7.

Solution

Solution

Solution

Solution