Solution

Solution

The number of possible pairs of letters that can appear in the first two positions is 26 · 26 = 676. Thus, by the Pigeonhole Principle, any set of 677 or more words must have at least two words with the same pair of letters at the beginning of the word.

Solution

The minor Mijof a matrix is the determinant formed by removing ithrow and jthcolumn of matrix,

Solution

Solution

Solution

A binary operation ∗ on set G is associative if (a ∗ b) ∗ c = a ∗ (b ∗ c)

Solution

For each toss, we get either Head or Tail. I.e.2 mutually exclusive outcomes

The sample space of this event of tossing 10 times is 2*2*2*...2= 2^10 = 1024.

I.e. There are 1024 number of possible outcomes from this experiment

The prob of HHHHHHHHHH = ½*½*...½= (1/2()^10

The prob of HTHTHTHTHT = ½*½*...½= (1/2()^10

The prob of TTTTTTTTTT = ½*½*...½= (1/2()^10

All these have same probability

Solution

Solution

Solution

一 一 一 一

The first place can be filled with ‘10’ people, the second with 9, third with 8, and last with 7.

So, we can arrange in 10987=5040

Solution

Solution

The existential quantifier distributes over disjunction, but not conjunction.

Solution

A Hamiltonian cycle is a closed loop on a graph where every node (vertex) is visited exactly once.

The total number of hamiltonian cycles in a complete graph are

(n-1)!/2, where n is the number of vertices.

= (8-1)!/2 = 2520

Solution

We can select 11 from 16 in 16C₁₁ combinations.

Solution

We can color this graph with just two colors

Solution

Solution

(AB)^-1 = B^-1 A^-1

It is the inverse property of multiplication of two invertible matrices

Solution

Physical layer accepts data or information from the data link layer and converts it into hardware-specific operations so as to transfer the message through physical cables. Some examples of the cables used are optical fibre cables, twisted pair cables and co-axial cables.

Solution

Channel coding is the function of the physical layer. Datalink layer mainly deals with framing, error control and flow control. Datalink layer is the layer where the packets are encapsulated into frames.

Solution

Piggybacking is a technique in which the acknowledgement is temporarily delayed so as to be hooked with the next outgoing data frame. It saves a lot of channel bandwidth as in non-piggybacking system, some bandwidth is reserved for acknowledgement.

Solution

Given Bandwidth (B) = 50 Kbps = 50 x 103 bps

Bitrate for each host (b) = 512 / 25 = 20.48 b/s

In slotted ALOHA,

Number of stations N = (0.368 * Bandwidth) / Bitrate of each station.

= (0.368 x 50 x 103) / 20.48

= 898.4 stations

Solution

Solution

Listen: Used on server-side, cause a bound TCP socket to enter the listening state.

Connect: It assigns a free local port number to a socket. In case of TCP socket, it causes an attempt to establish a new TCP connection.

Bind: Associates a socket with socket address structure.

Accept: Accepts a received incoming attempt to create a new TCP Connection from the remote client.

Solution

We know that for selective repeat ARQ = 2^(n -1) = 128, n = 8

Sequence numbers: 0 to 255, 0 to 255, …. So on.

256 + 99 (Sequence number) = 355

Solution

Solution

There are 10 different control fields each with their own control lines. At a time there can be only one control line active from each field.

We need to have all the 10 control fields.. Within a control field Ci out of the ni distinct control lines we need to identify one control line which is active. To do this we can apply vertical microprogramming and use log(ni) bits.

So the number of bits needed for each control field can be summarized as below:

Here for C7 there is only one control line that needs to be represented, so for that we are taking 1 bit. Without even using 1 bit we can’t represent whether the control line is active or not. So for this case alone we are not applying log(1) = 0.

So the total size of the control field = 2+1+2+4+4+4+3+1+3+5 = 29

Solution

Clock period (CP) = max stage delay + overhead

So CP_P1=Max(2,1,3,1,4)=4ns

CP_P2=Max(1.5,2.5,1,3)=3ns

CP_P3=Max(1,2,0.5,1.6)=2ns

CP_P4=Max(1.5,0.4,0.5,1,1)=1.5ns

As frequency ∝ 1/CP, so least clock period will give the highest peak clock frequency.

Since P4 has the least clock period, it will have the highest frequency.

Solution

It is given that instruction size is 2 words, and its starting address is X.

When executing the present instruction program counter gets incremented to the address of the next instruction.

So, the latest value in PC = X+2.

In the instruction operand value is Y, which is used as an offset for the effective address calculation.

So, Effective address= Program counter + Offset.

Here Program counter= X+2, Offset = Y

Effective address= X+Y+2

Solution

S1: In auto-increment addressing mode the amount of increment depends on the data item accessed. So S1 is false.

S2: PC relative addressing mode can be used to write position independent code. So S2 is true.

Solution

The system has the word size of 32 bits. So one word is 4 bytes.

Here the IO device speed is 4MBPS.

In one second, the IO device sends 4MB of data, when we convert 4MB into the number of words, 4MB/4B = 1M = 2^20 words.

In Programmed I/O, the CPU issues a command and waits for I/O operations to complete.

Here, the CPU will wait for 1 sec to transfer 2^20 words of data.

The time taken to transfer 1 word in programmed IO = (1/2^20) seconds.

Here 2^20 can be approximately taken as 10^6 because in general we take the approximations as 2^10 ~= 10^3, 2^20 ~= 10^6 and 2^30 ~= 10^9 etc.

So, the time taken to transfer 1 word ~= (1/10^6) = 1 microsecond.

In the interrupt driven mode, there is one interrupt for every byte. It is given that the overhead for every interrupt is 0.5 microseconds.

So the time taken to transfer one byte in interrupt driven mode = interrupt overhead + actual data transfer from buffers to memory. Since the registers to CPU or memory transfer time is negligible, we take only the overhead time of 0.5 microseconds for the interrupt driven case. The performance gain = 1 / 0.5 = 2

Solution

The Main memory size is 1MB = 2^20 and the given physical addresses of the words are 5 digits of hexadecimal numbers.

So it is a byte addressable memory and we are given the address of each byte in the memory.

Block size is given as 16 Bytes. So block offset needs 4 bits.

The cache size is 4KB. Number of blocks in the cache = 4KB/16B = 256 = 2^8. The LINE number needs 8 bits.

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

The given physical addresses are in hexadecimal format and each has 5 digits. Each hexadecimal digit needs 4 binary bits.

Let the four physical addresses be A = 0x30243, B = 0x41246, C = 0x14324, D = 0x14326

If you convert these four physical addresses into binary,

A = 0x30243 = 0011 0000 0010 0100 0011. Here the least significant 4 bits are OFFSET bits(0011) and the next 8 bits which are in bold are the LINE number(0010 0100)

B = 0x41246 = 0100 0001 0010 0100 0110. Here the LINE number is (0010 0100)

C = 0x14324 = 0001 0100 0011 0010 0100. Here the LINE number is (0011 0010)

D = 0x14326 = 0001 0100 0011 0010 0110. Here the LINE number is (0011 0010)

Here the physical addresses A and B are mapped to the same cache line (0010 0100) but they are completely different addresses as we can see the TAG bits of them are not matching. TAG bits of A are 0011 0000 and the TAG bits of B are 0100 0001.

First the block corresponding word A will come and will go to cache. When B is accessed it will evict A from the cache as B is also mapped to the same cache line.

In the next iteration A will replace B from the 1st iteration, and when B comes it will replace A. This will keep going on for all the 50 iterations.

So, both A and B will result in cache misses for all the 50 iterations, which will give cache 50*2 = 100 misses.

But the physical addresses C and D belong to the same block as they both have the same LINE numbers and same TAG bits also.

So after accessing C the first time it results in a miss and the corresponding block is fetched from main memory into cache. When D is accessed first time that will result in a cache hit, as D is also in the same block as C. From then on all the accesses to both C and D will be hit for all the 50 iterations. So all the accesses to D are hits including its 1st access.

Out of 50 iterations C and D together cause only 1 cache miss.

That's why total cache misses are 100+1 = 101.

Solution

It is given that cache size = 512 KB

Cache block size = 64 Bytes

So, number of blocks in the cache = 512K / 64 = 8 K

It is a 2-way set associative cache. Each set has 2 blocks.

So, the number of sets in cache = 8 K / 2 = 4 K = 2^12.

So, 12 bits are needed for accessing a set.

Since cache block size is 64 bytes, block offset needs 6 bits.

Out of 32 bit address, no. of TAG bits = 32 - 12 - 6 = 32-18 = 14

So, the number of bits in the tag field of an address is 14.

Here the extra 2 valid bits and 1 modified bit are present in the tag directory associated with each cache line in the cache. But in the address the tag bits are only 14.

Solution

A. By increasing the cache line size we can fetch more words at the same time. That will reduce the compulsory misses.

B. By increasing the cache size, it can accommodate more cache lines increasing the cache capacity. This will reduce the capacity misses which result due to lack of cache capacity.

C. By increasing the cache associativity we can accommodate more cache lines within a cache set. This will avoid the cache lines trying to evict one another and hence reduces the conflict misses.

D. A cache miss can either be compulsory miss or capacity miss or conflict miss. It can’t belong to more than one type. Hence D is also true.