Search Previous Year Questions

Floyd’s warshall algorithm is used find the shortest path between every pair of nodes. It is used for all pair shortest path problem.

Algorithm:

N= w.rows

D⁰ = w

For k = 1 to n

Let D^k = d_ij^k be new n × n matrix

For i = 1 to n

For j = 1 to n

D_ij^k = min (d_ij^k-1, d_ik^k-1 + d_kj^k-1)

Returns Dⁿ.

So, in Floyd warshall to calculate the shortest path three for loops are used which goes upto n, so time complexity will be Θ(n³).

Here mutex = 1

first, take Process 1, that is, P₁

P(mutex);

CS

V(mutex);

This code will run. mutex = 0 and P₁ will move into the critical section.

After this, try to enter the P₈ in the critical section, it will run the code :

V(mutex);

CS

V(mutex);

In this case, it will changes mutex into 1, and P₈ will enter into the critical section. After this, exit the P₈ from the critical section, it will change mutex to 2. Then again enter P₈. In this way, it increases the mutex value always.

In this way, if Mutex becomes 8 then all the 8 processes can simultaneously enter the critical section.

So, the maximum number of processes that can be present in the critical section at any point in time = 8.

Given declaration is:

int * (*P) (char * Q[]);

This expression states that:

P is a pointer to a function that accepts an argument which is an array of character pointers and returns a pointer to an integer.

Concept:

Class B has 16 bits for network id part and 16 bit for host id part.

Explanation:

Given that, organization have 60 departments and has a class B network. As class B network has 16 bits for network id, so, for subnet mask all 16 bits for network id will be 1.

Now 60 departments will require 6 bits for subnet.

First 16 bits are 1. We take first 6 bits of third octet in class B network and make them 1 for subnet mask.

So, subnet mask will be: 11111111.11111111.11111100.00000000

i.e. 255. 255. 252. 0

A cache is a hardware or software component that stores data so future requests for that data can be served faster.

Write-through approach:

Using this approach, data is written to the cache and memory store location at the same time. It is not compulsory here that in which order it happens. Main point is that i/o completion is only confirmed once the data has been written to both places. It ensures fast retrieval while making sure the data is in the backing store.

Write back approach:

Using this approach, data is written to the cache and then i/o is confirmed. In this updates are made only in the cache and it minimizes memory writes.

LRU replacement algorithm can be used in associative and set associative mappings.

So, here option 1) is incorrect.

Network security provides the following services:

Message authentication:

It ensures that message has been sent by a genuine identity and not by an imposter. In this, receiver needs to be sure of the sender’s identity. It is a service beyond message integrity.

Message integrity:

It means that data must arrive at the receiver exactly as they were sent. There must be no changes during the transmission, neither accidentally nor maliciously.

Message non- repudiation:

It means that a sender must not be able to deny sending a message that he or she in fact did send. For example, when a customer sends a message to transfer money from one account to another, the bank must have proof that the customer actually requested this transaction.

Message confidentiality:

It means that the sender and the receiver expect confidentiality. The transmitted message must make sense to only the intended receiver. To all others, message must be garbage.

Entity integrity constraint:

It states that primary key value cannot be NULL. This is because the primary key value is used to identify individual rows in relation and if the primary key has a NULL value, then we cannot identify those rows.

Cardinality ratio:

It is a concept that describes binary relationship set and its types. It is about the maximum number of entities of one entity set that are associated with the maximum number of entities of other entity set.

Foreign key constraint:

A foreign key joins a table to another table by referencing its primary key. A foreign key constraint specifies that the key can only contain values that are in the referenced primary key and ensures the referential integrity of data that is joined on the two keys.

Participation constraint:

It specifies the presence or existence of an entity when it is related to another entity in a relationship type. It is also called as minimum cardinality constraint.

Topological sorting for directed acyclic graph (DAG) is a linear ordering of vertices such that for every directed edge <v, w>, vertex v comes before vertex w in the ordering.

There can be more than one topological sorting for a graph.

Algorithm to find topological sort:

1. Use a temporary stack

2. recursive call topological sort for all the adjacent vertices one by one

3. then push them to the stack.

4. Finally print the content of the stack.

Consider an example:

Topological sort for this one: 1 2 3 4 5

Another topological sort possible: 1 2 3 5 4

Concept:

Addressing modes refers to the way in which the operand of an instruction is specified. They specify a rule for modifying the address field of an instruction before the operand is executed.

Explanation:

Register addressing mode:

It is the simplest addressing mode in which the source or destination is a data register or an address register. Content of the register provides the operand. Here, only one register reference is required to access the data.

Displacement addressing mode:

In this content of indexed register is added to the address part of the instruction to obtain the effective address of the operand.

Effective address = base value + displacement

Auto increment mode:

Effective address of the operand is the contents of a register specified in the instruction. After accessing the operand, contents of register are automatically incremented to point to next memory location. Useful in a loop.

Index mode:

The address of the operand is obtained by adding to the contents of the general register (index register) a constant value. Index mode is used to access an array whose elements are in successive memory locations.

Concept:

Hamming distance is for comparing two binary data strings. Hamming distance is the number of bit positions in which the two bits are different.

Explanation:

It can be calculated by performing XOR operation on two binary strings and then count the number of 1’s in the result.

Take two pairs one by one and find hamming distance between them.

1. take data word “00” and “01”

00111 XOR 01001 = 01110, hamming distance = 3

2. take data word “00” and “10”

00111 XOR 10101 = 10010, hamming distance = 2

3. take data word “00” and “11”

00111 XOR 11100 = 11011, hamming distance = 4

4. take data word “01” and “10”

01001 XOR 10101 = 11100, hamming distance = 3

5. take data word “01” and “11”

01001 XOR 11100 = 10101, hamming distance = 3

6. take data word “10” and “11”

10101 XOR 11100 = 01001, hamming distance = 2

As, we have checked all the possibilities, so minimum hamming distance for given coding scheme = 2