Solution

Fourth proportional to 4, 14, 24 be x.

Then, 4:14:24:x

4x=24*14

x=84

Solution

The numbers are 31 x 13 and 31 x 16

∴ Larger number =31 x 16=496

Solution

LCM of 2, 3, 4, 5, 6 and 8 is 120 (2 minutes)

In 44 minutes, they will toll together =44/2+1=23 times

Solution

Solution

Solution

Solution

Succulent means tender and Juicy. Cactus is a type of succulent plant.

The opposite of succulent is dry and hard, which can be seen in wood.

Solution

Offender is a person who commits an illegal act.

Bystander is a person who is present at an event but does not take part.

Defender is a person who protects.

Mender is a person who repairs things.

Solution

“Upon” and “on” are both used as prepositions. Prepositions are used to express the relationship of a noun and a pronoun in the sentence with another word. They can be used interchangeably in many cases.

Solution

‘Meerabai stopped the practice of animal sacrifice and challenged the custom of ‘Sati’. Despite being a young princess who grew up in a male dominated society, she showed how she could resolve matters.’

Solution

Step 1:

Preorder:

Inorder:

Step 2:

Preorder:

Inorder:

Step 3:

Preorder:

Inorder:

Step 4:

Preorder:

Inorder:

Solution

Hashing is an important Data Structure which is designed to use a special function called the Hash function which is used to map a given value with a particular key for faster access of elements. The efficiency of mapping depends on the efficiency of the hash function used.

Solution

Due to the nature of these algorithms, in the case of a graph with moderate number of edges, we should use Kruskal's algorithm. Prim's algorithm runs faster in a graph with many edges as it only compares limited number of edges per loop, where as Kruskal's start by sorting all the edges in the list then going through them again to check if the edge is part of the minimal spanning tree (MST) or not. Hence although both algorithms have similar running time, number of edges in the graph should be the main component when you are deciding between the algorithms. More edges compared to vertices, use Prim's, otherwise, use Kruskal's.

Solution

Check-out the output of the extra print statement added in the code and see the outcome of every iteration output. This will make you understand the recursion and overall handrun of the code.

#include <stdio.h>

int counter = 0;

int calc (int a, int b) {

int c;

counter++;

printf("a=%d, b=%d, counter=%d\n",a,b,counter); //extra print to understand

if (b==3) return (a*a*a) ;

else {

c = calc(a, b/3) ;

return (c*c*c) ;

}

}

int main () {

calc (4, 81);

printf ("%d", counter) ;

}

Output:

a=4, b=81, counter=1

a=4, b=27, counter=2

a=4, b=9, counter=3

a=4, b=3, counter=4

Solution

Since in statement 1, they have said that it root has at least two children then root vertex will act as articulation point and it will disconnect the graph into more than one component. It is true!!

Statement 2:

For BFS in directed graphs, each edge of the graph either connects two vertices at the same level, goes down exactly one level, or goes up any number of levels. For DFS, each edge either connects an ancestor to a descendant, a descendant to an ancestor, or one node to a node in a previously visited subtree. It is not possible to get "forward edges" connecting a node to a subtree visited later than that node.

Solution

The function rearrange() exchanges data of every node with its next node. It starts exchanging data from the first node itself.

Solution

A directed graph G is acyclic (DAG) if and only if a depth-first search of G yields no back edges.

Proof.

1. Direct: Suppose that there is a back edge (u, v). Then vertex v is an ancestor of vertex u in the depth-first forest. There is thus a path from v to u in G, and the back edge (u,v) completes a cycle.
2. Reverse: Suppose that G contains a cycle c. We show that a depth-first search of G yields a back edge. Let v be the first vertex to be discovered in c, and let (u,v) be the preceding edge in c. At time d[v], there is a path of white vertices from v to u. By the white-path theorem, vertex u becomes a descendant of v in the depth-first forest. Therefore (u,v) is a back edge.

Three possible scenarios of edge classification:

Fig. Edge classification with DFS. In the case of scenario (a), the discovery sequence is a, b, d, e, f, c, g, h. When we reach node d from a, we characterize edge (a.d) as a forward edge because d is already discovered (from node b). The same applies for node f. When examining the outgoing edges of e we characterize edge (e,a) as a back edge, since a is already discovered and is an ancestor of e. Edges (c,d), (c,e) are cross edges because d and e are already discovered and have no ancestor-descendant relation with c. The same applies for edges (g,b) and (h,d).

Solution

The logical representation of the given graph is:

Applying BFS algorithm on above graph starting from vertex 5,

Solution

After adding all edge weights of every given circuit, The option C forms a negative weight cycle.

Option A: B-A, A-F, F-D, A-D, A-C, C-B → 30+(-17)+16+12+(-15)+(-16) → 10

Option B: B-A, A-C, C-B → 30+(-15)+(-16) → -1

Option C: B-A, A-F, F-D, D-C, C-B → 30+(-17)+16+(-16)+(-16) → -3

Option D: B-A, A-D, D-C, C-B → 30+12+(-16)+(-16) → 10

Solution

The above code is nothing but n/x means n=7 and x=3 then we get 2 because we are considered as integer values.

The number of digits in the base x representation of n.

The time complexity of the above code segment is O(⌊(log_xn)+1⌋) = O(logn)

Solution

The Floyd Warshall algorithm is used to find all the pairs of shortest distances in a graph using dynamic programming

Solution

Two possible Shortest paths:

Solution

Given elements : 16, 25, 28, 37

(x+1) mod 6

(16+1) mod 6 = 17 mod 6 → Slot 5 [ No collision ]

(25+1) mod 6 = 26 mod 6 → Slot 2 [ No collision ]

(28+1) mod 6 = 29 mod 6 → Slot 5 [ Collision ]

(37+1) mod 6 = 38 mod 6 → slot 2 [ Collision ]

2x mod 6

2*16 mod 6 → 32 mod 6 → Slot 2 [ No collision ]

2*25 mod 6 → 50 mod 6 → Slot 2 [ Collision ]

2*28 mod 6 → 56 mod 6 → Slot 2 [ Collision ]

2*37 mod 6 → 74 mod 6 → slot 2 [ Collision ]

x mod 6

16 mod 6 → slot 4 [ No collision ]

25 mod 6 → slot 1 [ No collision ]

28 mod 6 → slot 4 [ Collision ]

37 mod 6 → slot 1 [ Collision ]

(2x+1) mod 6

(2*16+1) mod 6 → 33 mod 6 → Slot 2 [ No collision ]

(2*25+1) mod 6 → 51 mod 6 → Slot 2 [ Collision ]

(2*28+1) mod 6 → 57 mod 6 → Slot 2 [ Collision ]

(2*37+1) mod 6 → 75 mod 6 → slot 2 [ Collision ]

Solution

Given elements : 32,56,87,23,65,26,93

x mod 7

32 mod 7 → 4

56 mod 7 → 0

87 mod 7 → 3

23 mod 7 → 2

65 mod 7 → 2 [ collision ]

(65 mod 7)+1 → 3 [ collision ]

(65 mod 7)+2 → 4 [ collision ]

(65 mod 7)+3 → 5 [ No collision ]

26 mod 7 → 5 [ collision ]

(26 mod 7)+1 → 6 [ No collision ]

The final content is given below table and index starts from 0.

Input array for Bubble sort 56, 93, 23, 87, 32, 65, 26

After first pass: 56, 23, 87, 32, 65, 26, 93

Except 56 elements every element has changed their order.

So, the final answer is 6.

Solution

If language is not regular then its complement must be non-regular. As regular language is closed under complement hence if L is regular then L' must be regular. If L is non-regular (only CFL) then L' must be non-regular.

So if L is CFL but not regular then L' must be non-regular but it can be CFL also.

L' must be CSL (as we can assume L as CSL and CSL is closed under complement so L' must be CSL.

So if L is CFL but not regular then L' must be non regular and L' must be CSL but L' may or may not be CFL.

Solution

The grammar is S→AB & A→aAb |ab & B→bBc |ab

The strings in L are {abbc, aabbbc, abbbcc, aabbbbcc, ………… ….}

Hence, the language is L={a^n b^k c^m | k=n+m & n,m >0}, also equivalent to L={a^n b^(n+m) c^m | n,m >0}.

Solution

The regular expression for given language

a(a+b)*bb

The strings in language are

{abb, aabb, abbb, ………..}

The minimal DFA is

Solution

The given TM accepts only one string “a” hence the language accepted by TM is finite as well as regular.

The TM will go to an infinite loop for the input string “ab”.

Solution

The Turing machine corresponding to recursively enumerable language will always halt for any string present in language and may or may not halt for string not in language.

The Turing machine for a recursive language is a halting Turing machine, i.e., TM for recursive language will always halt for any input.

Since TM accepts ∑* (universal language), hence it must halt if run with empty string as input, as epsilon is present in ∑*.

Consider below TM

The given TM accepts only one string “a” hence the language accepted by TM is finite as well as regular.

The TM will go to an infinite loop for the input string “ab”.

Hence, a Turing machine accepting a finite language may or may not halt for some string w which is not present in language.

Solution

The string “aabb” has two parse trees using LMD.

Tree1: S->aSb -> aaSbb-> aabb

Tree 2: S-> aSb-> aabSb->aabb

The grammar is ambiguous, as string ab (length two) has two parse trees.

Tree1: S->aSb -> ab

Tree 2: S-> abS-> ab

The grammar will always generate an even length string.

Solution

Since the number of states in LR(0) and LALR(1) is the same, the goto part of both tables must be the same and hence the shift entries of both tables are also the same.

Every LR(0) must be LALR(1) but every LALR(1) need not be LR(0).

Solution

Consider the expression “x-y-z”, if precedence is “<” then “y-z” will be evaluated first, hence it is right associative.

Solution

If I is the set of one item {[ E’→.E]}, then CLOSURE(I) contains the set of items I₀

Solution

An annotated parse tree is a parse tree showing the values of the attributes at each node. The process of computing the attribute values at the nodes is called annotating or decorating the parse tree. The drawback for quadruple representation of 3-address code is it requires more space compared to triple notation. The drawback of triples is that, in triples form statements cannot be moved, whereas it is indirect triples which has the drawback that it requires two memory accesses.

Solution

(AB)+ = ABCDE

Candidate key = AB

Prime attributes = A, B

Non prime attributes = C, D, E

• The functional dependencies C->D and BD->E are transitive dependencies.
• Hence, R is in 2NF but not in 3NF.

Solution

Syntax for NOT BETWEEN is:

SELECT column-names

FROM table-name

WHERE column-name NOT BETWEEN value1 AND value2;

Solution

• The recovery system reads the logs backwards from the end to the last checkpoint.
• It maintains two lists, an undo-list and a redo-list.
• If the recovery system sees a log with <Tn, Start> and <Tn, Commit> or just <Tn, Commit>, it puts the transaction in the redo-list.
• If the recovery system sees a log with <Tn, Start> but no commit or abort log found, it puts the transaction in undo-list.

All the transactions in the undo-list are then undone and their logs are removed. All the transactions in the redo-list and their previous logs are removed and then redone before saving their logs.

Solution

Consider two schedules S1 and S2 each consisting of two transactions T1 and T2.

Schedules S1 and S2 are called view equivalent if the following three conditions hold true for them-

1. Initial readers must be the same for all the data items.
2. Write-read sequence must be the same.
3. Final writers must be the same for all the data items.

Solution

SJF schedule P1, P2, P3, P5, P4

Waiting time = 0+2+ (6‐3)+(8‐6)+(14‐4)=17,

Average = 17/5 = 3.4ms.

Solution

On successful fork(), 0 is returned to the child and any positive integer >0 is returned to the parent. In the above code,

1st iteration = 2 processes, 2 numbers printed

2nd iteration = 4 processes, 4 numbers printed

3rd iteration = 8 processes, 8 numbers printed

…

nth iteration = 2^n processes 2^n numbers printed

Total numbers printed = 2+4+8+ … +2^n = 2^(n+1)‐2

In each iteration half of the numbers are 0, so rest are non‐zero numbers, (2^n)‐1 non zero numbers.

Solution

The SJF algorithm minimizes the average waiting time of a set of running processes.

The Swapped‐Out states are used to temporarily move some processes in the Ready or Waiting states to the corresponding Swapped‐Out states on disk. Peterson’s solution does not require special hardware support.

Solution

All the processes run the for loop and wait in the while loop if all the resources are not available. Since the processes acquire the lock in sorted order, the deadlock is not possible.

Solution

Virtual address 7 = 0000 (page number) + 0111 (offset) = logical page 0. TLB hit.

Virtual address 20 = 0001 0100 = logical page 1. TLB miss.

Virtual address 70 = 0100 0110 = logical page 4. TLB miss. MMU accesses the page table and discovers it is an invalid entry. MMU raises a trap to the OS.

Virtual address 80 = 0101 0000 = logical page 5. TLB miss. MMU accesses page table and discovers page not present. MMU raises a page fault to the OS.

Solution

Connection requests should be (1, 0) and reply would be (1, 1).

Solution

Given IP address 168.17.07.255 is DBA and its class B.

In DBA HID part is all 1's

Therefore, 168.17.00000111.11111111

NID HID

For Netmask, NID part is all 1's and HID part is all 0's

Since the number of bits in NID or HID is not given, we can take any length for NID.

So the last 11 bits can be HID (bcz DBA contains all 1's in HID).

Similarly the last 10 bits can be HID, or 9 bits or 8 bits.

Depending on the number of bits Subnet Mask will vary.

The range of Netmask can be 255.255.248.0 to 255.255.255.0

Solution

The only SMTP is used for sending emails. The receiver uses POP3 or IMAP4 for receiving the mail from the mail server.

Solution

Solution

The probabilty that atleast one of them completes the assignment = 1-probability of none of them completing the assignment.

1- ½ * ⅘*⅚ = 1-⅓ = ⅔

Solution

Minor is obtained by eliminating the row and column of a particular element.

The

is obtained by eliminating ‘6’.

Remaining minors are not obtained by eliminating a row and column of the same element.

Solution

The row reduction of the matrix does not yield any zero row. Thus the rank is 3

Solution

For a contradiction the result must be False for all inputs.

Solution

Solution

Trees are acyclic graphs so they have no odd cycles. They are therefore bipartite

Clearly if a graph has a spanning tree it is connected. Suppose that G is connected on n vertices. If |E(G)| = n−1, then G is a tree because it has the minimum number of edges possible in a connected graph. If |E(G)| > n −1, then G is not a tree. So G must contain a cycle. Choose any edge e on a cycle of G and remove it. Now G −e is either a tree and so a spanning tree of G, or G −e contains a cycle. We continue removing edges from cycles until we produce the spanning tree we are after.

A bipartite graph can be colored with only 2 colors. There is not requirement of the third color.

Other than this statement, rest are theorems. Make a note of them.

Any graph can be colored with n colors.

Solution

Pigeonhole Principle : If k is a positive integer and k + 1 objects are placed into k boxes, then at least one of the boxes will contain two ore more objects.

We require minimum K+1 pigeons to have atleast two pigeons in a case. ITs possible only with k+1, k+2 out of the given options

Solution

Solution

It is given that the program starts at address 200. Before executing the program, PC will get assigned to this address, so PC value will be 200 at the beginning of execution of this program. Each instruction is of size 32 bits = 4 Bytes, so PC can get incremented by 4 memory locations at a time. So a legal PC value has to be a multiple of 4. From the given options 215 is not a multiple of 4 hence it is not a valid address.

Solution

A is false because RISC processors have hard-wired control units

B is true as CISC processors have microprogrammed control units

C and D are true as RISC processors are pipelined whereas CISC processors are not pipelined in general.

Solution

Physical address in a set associative cache has three fields: (tag bits + set number + block offset).

Number of Blocks =512K / 32 = 2^19 / 2^5 = 2^14

Number of sets = 2^14 / 2 = 2^13

No. of bits needed for set number = 13

Blocksize = 32 Bytes = 2^5 Bytes, so block offset = 5 bits

So number of bits for set number + block offset = 13+5 = 18 bits

Solution

The device transmits 6400 bits in 1 second, which is the same as 800 Bytes in 1 second.

Each character is 1 byte in size, so the device is transmitting 800 characters in one second.

Then the time taken by the device for 1 character = 1 / 800 second.

The processor speed is 1 MIPS (=10^6 instructions per second).

Two instructions are needed to transfer 1 character. The processor speed in terms of transferring characters to the memory = 1/2 million characters per second = 0.5 * 10^6 characters per second.

DMA works at the speed of the processor, so the time taken by the DMA to transfer 1 character= 1 / (0.5 * 10^6) seconds = 2 microseconds.

Since it is a cycle stealing mode when the I/O device is preparing the second character the DMA will transfer the first character at the same time.

Out of (1 / 800) seconds the DMA uses 2 microseconds of processor time to transfer the data and at this time the processor can’t do other operations.

The fraction of processor slow down = (2*10^-6) / (1 / 800) = 1600*10^-6 = 16*10^-4

The % of processor slow down = (16*10^-4) * 100 = 0.16 %

Solution

Set associative cache:

Block size = 64B = 26B, block offset = 6 bits.

Number of cache lines = 64KB / 64B = 1K = 210.

Number of sets = 210/4 = 28

SET number needs 8 bits.

Since the address is 32 bits.

No. of TAG bits = 32 - 8 - 6 = 18 bits

A 4-way set associative cache needs two kinds of multiplexers.

In set associative cache we need two kinds of MUXs. One type for set selection(decoder) and the other for OR gate which is also called way selection multiplexer. If it is a k-way set associative cache then we need one k-to-1 MUX which is also called as the way selection multiplexer. As we are given the latency of the 4-to-1 MUX as 0.8ns we consider it, and since there is no information about the set selection multiplexer we ignore it.

Apart from the way-selection MUX delay there is also delay of the comparator.

There are 18 tag bits so we need comparators of size 18 bits. Delay due to the comparators = 18/5 ns

H1 = 18/5 + 0.8 ns = 3.6 + 0.8 ns = 4.4 ns

Direct mapped cache:

Block offset = 6 bits

As there are 2^10 blocks in the cache, BLOCK number will need 10 bits in the direct mapped cache.

So, out of 32 bit address no. of TAG bits = 32 - 10 - 6 = 16 bits.

In the direct mapped cache here we need only the MUX used in decoder. Just as we ignored the delay of MUX used in decoder in set associative cache in the direct mapped cache also we are ignoring the delay of the MUX used in decoder.

So H2 = 16/ 5 nsec = 3.2 nsec

Difference = H1 + H2 = 4.4 + 3.2 = 7.6 nsec

Solution

Every digit in base 16 (i.e 2^4 ) requires 4 bits in base 2.

So, a 10 digit hexadecimal requires 4x10= 40 bits.

Solution

It is possible to construct a synchronous MOD 2^n counter by using n flip-flops and (n-2) AND gates.

Solution

Solution

For a neutral function, the number of minterms is equal to the number of maxterms.

Odd function is a neutral function because for exactly half of the input combinations, the number of 1s is odd(or even).

Solution

A + CD + CB= A+ C(D+B)