Solution

In divisibility poset, least element means an element which divides every element.

Here, $3$ does not divide $5$, so $3$ is not the least element.

Similarly, no other element divides all elements of the set.

So, least element does not exist.

Greatest element means an element which is divisible by every element.

Here, $45$ is not divisible by $24$.

Also, no other element is divisible by all elements of the set.

So, greatest element does not exist.

Therefore, there does not exist a greatest element and a least element.

Solution

Let the number of balls in four distinguishable bins be $x_1,x_2,x_3,x_4$.

Then,

$x_1+x_2+x_3+x_4=8$

Here, balls are indistinguishable and bins are distinguishable.

So, the number of non-negative integral solutions is

${}^{n+r-1}C_{r-1}$

Here, $n=8$ and $r=4$.

So,

${}^{8+4-1}C_{4-1}={}^{11}C_{3}$

$=\dfrac{11 \times 10 \times 9}{3 \times 2 \times 1}$

$=165$

Solution

Total length of bit string is $10$.

Let $A$ be the set of bit strings starting with $1$.

So, first bit is fixed and remaining $9$ bits are free.

$n(A)=2^9=512$

Let $B$ be the set of bit strings ending with $00$.

So, last two bits are fixed and remaining $8$ bits are free.

$n(B)=2^8=256$

Now, strings which start with $1$ and end with $00$:

First bit is fixed as $1$ and last two bits are fixed as $00$.

Remaining $7$ bits are free.

$n(A \cap B)=2^7=128$

Therefore,

$n(A \cup B)=n(A)+n(B)-n(A \cap B)$

$=512+256-128$

$=640$

Solution

Given,

$V=6$

Each vertex has degree $4$.

So, sum of degrees is

$6 \times 4=24$

By handshaking theorem,

$2E=24$

$E=12$

For a connected planar graph, Euler’s formula is

$V-E+R=2$

Substitute $V=6$ and $E=12$.

$6-12+R=2$

$R=8$

Solution

In a complete bipartite graph $K_{m,n}$, vertices are divided into two parts.

A Hamilton circuit must visit every vertex exactly once and return to the starting vertex.

In a bipartite graph, every cycle alternates between the two parts.

So, for a Hamilton circuit to include all vertices, both parts must have the same number of vertices.

Therefore,

$m=n$

Also, a cycle needs at least $2$ vertices in each part.

So,

$m,n \ge 2$

Hence, $K_{m,n}$ has a Hamilton circuit when

$m=n,\ m,n \ge 2$

Solution

Given statement is

$[(p \vee q)\wedge[p \to q]]$

We know that

$p \to q \equiv \neg p \vee q$

So,

$[(p \vee q)\wedge[p \to q]]=(p \vee q)\wedge(\neg p \vee q)$

Now truth table se false cases:

When $p=0,\ q=0$, expression false hoti hai.
Corresponding maxterm is

$p \vee q$

When $p=1,\ q=0$, expression false hoti hai.
Corresponding maxterm is

$\neg p \vee q$

Therefore, PCNF is

$(p \vee q)\wedge(\neg p \vee q)$

Hence, correct PCNF is $(p \vee q)\wedge(\neg p \vee q)$.

Solution

A standard deck has

$13$ hearts

and

$52-13=39$ non-heart cards.

To guarantee at least $3$ hearts, consider the worst case.

First, we may select all $39$ non-heart cards.

Then, we may select only $2$ hearts.

So, cards selected without guaranteeing $3$ hearts:

$39+2=41$

Now, the next card must be a heart.

So, required number of cards is

$41+1=42$

Solution

First,

$p \to q \equiv \neg p \vee q$

So,

$(a) \rightarrow (iv)$

Now,

$\neg p \to q \equiv p \vee q$

So,

$(b) \rightarrow (iii)$

Now,

$q \to \neg p \equiv \neg q \vee \neg p$

Therefore,

$\neg(q \to \neg p)=\neg(\neg q \vee \neg p)$

Using De Morgan’s law,

$\neg(\neg q \vee \neg p)=q \wedge p$

$=p \wedge q$

So,

$(c) \rightarrow (i)$

Now,

$\neg(p \to q)=\neg(\neg p \vee q)$

Using De Morgan’s law,

$\neg(\neg p \vee q)=p \wedge \neg q$

So,

$(d) \rightarrow (ii)$

Therefore, the correct matching is

$(a)-(iv);\ (b)-(iii);\ (c)-(i);\ (d)-(ii)$

Solution

Given matrix is

$A=\left[\begin{array}{ccc}1 & 0 & 1\\0 & 1 & 0\\1 & 1 & 0\end{array}\right]$

From the matrix, the relation contains:

$1 \to 1,\ 1 \to 3,\ 2 \to 2,\ 3 \to 1,\ 3 \to 2$

Now, since $1 \to 3$ and $3 \to 2$, therefore $1 \to 2$ must be added.

Also, since $3 \to 1$ and $1 \to 3$, therefore $3 \to 3$ must be added.

So, the transitive closure matrix is

$\left[\begin{array}{ccc}1 & 1 & 1\\0 & 1 & 0\\1 & 1 & 1\end{array}\right]$

Hence, the correct answer is Option 1.

Solution

Given objective function is

$\text{Max } Z=2x_1-x_2+2x_3$

In the objective function, the positive coefficient of $x_3$ is $2$.

Taking $x_3$ as the entering variable, we apply the minimum ratio test.

From the constraints:

$2x_1+x_2\le 10$

$x_1+2x_2-2x_3\le 20$

$x_1+2x_3\le 5$

Only the third constraint has positive coefficient of $x_3$.

So,

$2x_3=5$

$x_3=\dfrac{5}{2}$

At the first iteration,

$x_1=0,\ x_2=0,\ x_3=\dfrac{5}{2}$

Now,

$Z=2x_1-x_2+2x_3$

$Z=2(0)-0+2\left(\dfrac{5}{2}\right)$

$Z=5$

Solution

In implied addressing mode, the operand is already implied in the instruction.

So, there is no need to specify any operand address separately.

Therefore, implied addressing mode requires the least number of memory references.

Solution

Content addressable memory is also called associative memory.

In this memory, data is searched by content instead of address.

Register $A$ contains the bit pattern and register $K$ decides which bits are to be compared.

Since this memory supports parallel searching by data association, it is called content addressable memory.

Solution

For a Boolean function of $n$ variables, the number of possible input combinations is

$2^n$

For each input combination, the output can be either $0$ or $1$.

So, total number of Boolean functions is

$2^{2^n}$

Solution

In a micro-program control unit, diagnostic tools help in detecting faults by observing and maintaining important internal states.

These internal states include flags, registers and counters.

Flags store status information, registers store intermediate data and counters help in tracking sequence or control steps.

Therefore, fault diagnosis becomes easier by maintaining the contents of flags, registers and counters.

Solution

When one counter is followed by another counter, the total number of states is the product of their mod values.

Here,

First counter is $MOD-2$

Second counter is $MOD-5$

So, total number of states is

$2 \times 5=10$

Solution

Seek latency is the time taken by the disk arm to move the read/write head to the required track.

The arm does not move with uniform speed throughout the seek operation.

It takes time to start moving and also takes time to stop at the required track due to inertia.

Because of this starting and stopping inertia, seek latency is not linearly proportional to the seek distance.

Solution

For $5$ bus arbiters, we need at least $3$ bits because

$2^2=4<5$

and

$2^3=8\ge 5$

So, the priority encoder must handle $8$ inputs and produce $3$ outputs.

Thus, priority encoder size is

$8 \times 3$

The decoder will take $3$ inputs and produce $8$ outputs.

Thus, decoder size is

$3 \times 8$

Solution

Given equation is

$(146)b+(313){b-2}=(246)_8$

Now,

$(146)_b=1\cdot b^2+4\cdot b+6$

$=b^2+4b+6$

Also,

$(313)_{b-2}=3(b-2)^2+1(b-2)+3$

$=3(b^2-4b+4)+b-2+3$

$=3b^2-12b+12+b+1$

$=3b^2-11b+13$

Now,

$(246)_8=2\cdot 8^2+4\cdot 8+6$

$=128+32+6$

$=166$

So,

$b^2+4b+6+3b^2-11b+13=166$

$4b^2-7b+19=166$

$4b^2-7b-147=0$

Now factorizing,

$4b^2-28b+21b-147=0$

$4b(b-7)+21(b-7)=0$

$(b-7)(4b+21)=0$

So,

$b=7$

Solution

Memory capacity is

$16K \times 16$

Here, $16K$ means number of memory locations.

$16K=16 \times 1024$

$=2^4 \times 2^{10}$

$=2^{14}$

So, number of address lines required is

$14$

Each memory location stores $16$ bits.

So, number of data lines required is

$16$

Therefore, address lines and data lines are

$14,\ 16$

Solution

Total execution time is

$100$ seconds

Time taken by multiplication operation is

$80$ seconds

Time taken by other operations is

$100-80=20$ seconds

Now, the program is required to run $4$ times faster.

So, new execution time should be

$\dfrac{100}{4}=25$ seconds

Other operations still take

$20$ seconds

So, time left for multiplication operation is

$25-20=5$ seconds

Originally multiplication operation takes

$80$ seconds

Now it should take

$5$ seconds

So, required improvement in multiplication speed is

$\dfrac{80}{5}=16$

Hence, multiplication operation must be improved by $16$ times.

Solution

Given loop invariant is

$m \times x^k=p^n$

At the end of the while loop, condition becomes false.

So,

$k=0$

Putting $k=0$ in invariant,

$m \times x^0=p^n$

Since,

$x^0=1$

Therefore,

$m=p^n$

Solution

Given that structure $S$ takes $32$ bits.

So,

$32\text{ bits}=4\text{ bytes}$

Now,

$p$ points to $B[4]$

$q$ points to $B[5]$

Since $p$ and $q$ are pointers of type $S$, pointer subtraction gives the difference in number of structures.

So,

$q-p=1$

Therefore,

$M=1$

Now, union $U$ contains $unsigned\ char\ a$ and $unsigned\ short\ b$.

Size of union $U$ is $2$ bytes.

After union $U$, variable $c$ is stored.

So, offset of $c$ from the beginning of structure is $2$ bytes.

Therefore,

$N=2$

Hence,

$(M,N)=(1,2)$

Solution

Here, the class has a method

$equals(Good\ n)$

This method does not override the original $equals(Object)$ method of Java because the parameter type is $Good$, not $Object$.

For Line 1:

$m1.equals(m2)$

Here both are objects of class $Good$, so $equals(Good\ n)$ is called.

Both values are $22$, so output is

$True$

For Line 2:

$s1.equals(s2)$

Here $s1$ and $s2$ are declared as $Object$ type.

So, Java calls $Object$ class $equals()$ method, which compares references.

Since both are different objects, output is

$False$

For Line 3:

$m1.equals(s2)$

Here $s2$ is of type $Object$, so $equals(Good\ n)$ is not called.

It calls $equals(Object)$, so reference comparison is done.

Output is

$False$

For Line 4:

$s1.equals(m2)$

Here $s1$ is of type $Object$, so again $Object$ class $equals()$ method is called.

Output is

$False$

Therefore, output is:

$True,\ False,\ False,\ False$

Solution

The expression $n$ bitwise AND $1$ checks the last bit of $n$.

If the last bit is $1$, then $b$ increases by $1$.

After that, $n$ is shifted right by one bit.

So, the loop checks each bit of $n$ one by one.

Therefore, $b$ counts the total number of $1$'s in the binary representation of $n$.

Solution

Statement $P$ is true.

JavaScript is dynamically typed. In JavaScript, variables can store values of different types at different times.

So, types are associated with values, not fixed permanently with variables.

Statement $Q$ is false.

Images can also be shown on a web page using CSS background images, SVG, canvas, object tag, embed tag, etc.

So, it is possible to show images without using the <img> tag.

Therefore, only $P$ is true.

Solution

Statement $P$ is true.

An XML document with correct syntax is called a well-formed XML document.

Statement $Q$ is also true.

If an XML document is validated against a DTD, then it is well formed and valid.

Statement $R$ is false.

An XML declaration must follow the proper XML declaration format. Without the required question-mark based syntax, it is not syntactically correct.

Therefore, only $P$ and $Q$ are true.

Solution

Resolution of raster system is

$640 \times 480$

Total number of pixels is

$640 \times 480=307200$

Each pixel requires $12$ bits.

So, total memory required is

$307200 \times 12=3686400$ bits

Convert bits into bytes:

$\dfrac{3686400}{8}=460800$ bytes

Now,

$1\text{ KB}=1024\text{ bytes}$

So,

$\dfrac{460800}{1024}=450\text{ KB}$

Solution

Given matrix is

When this matrix is applied on point $(x,y)$, then the point becomes $(x,-y)$.

This means the sign of $x$ remains same and the sign of $y$ changes.

So, this represents reflection about the $X$-axis.

Therefore, statement $S1$ is true.

But reflection about the $X$-axis is not a rotation matrix.

Therefore, statement $S2$ is false.

Hence, the correct answer is Option 2.

Solution

Orthographic transformation preserves parallelism.

So, parallel lines remain parallel after orthographic projection.

Therefore, statement $P$ is true.

Orthographic transformation is also an affine transformation because it preserves points, lines and parallelism.

Therefore, statement $Q$ is also true.

Solution

In the Phong reflectance model, specular reflection depends on how close the viewer direction is to the reflected light direction.

If the reflected vector and the view vector are close to each other, the specular highlight becomes stronger.

So, the strength of the specular highlight is determined by the angle between the reflected vector and the view vector.

Solution

Relational algebra has the same expressive power as relational calculus only when relational calculus expressions are restricted to safe expressions.

Safe expressions ensure that the query result is finite and depends only on the database.

So,

Relational algebra is equivalent to domain relational calculus restricted to safe expressions.

Also,

Relational algebra is equivalent to tuple relational calculus restricted to safe expressions.

Therefore, $(c)$ and $(d)$ are correct.

Solution

In relational algebra, some operations are based on mathematical set theory.

Intersection is a set operation.

Cartesian product is also a set operation.

Join and project are relational algebra operations, but they are not basic mathematical set theory operations.

So, the operations included for mathematical set theory are:

$(b)$ Intersection

$(c)$ Cartesian product

Solution

If a relation is in $BCNF$, then it is also in $3NF$.

Also, if a relation is in $3NF$, then it is already in $2NF$.

So, if $R$ is in $BCNF$, then $R$ must be in $2NF$ and $3NF$.

Solution

A foreign key is used to create a relationship between two tables.

A foreign key in one table generally refers to the primary key of another table.

This ensures referential integrity between the two tables.

Solution

A candidate key must uniquely identify each tuple in a relation.

So, uniqueness is a property of candidate key.

Also, a candidate key must be minimal. It means no proper subset of it can uniquely identify tuples.

This property is called irreducibility.

Therefore, both $P$ and $Q$ are true.

Solution

A candidate key must uniquely identify each tuple in a relation.

So, uniqueness is a property of candidate key.

Also, a candidate key must be minimal. It means no proper subset of it can uniquely identify tuples.

This property is called irreducibility.

Therefore, both $P$ and $Q$ are true.

Solution

Hadoop ecosystem includes several tools used for big data storage and processing.

Map Reduce is used for distributed data processing.

HBase is a NoSQL database used in the Hadoop ecosystem.

Hive is used for querying large datasets stored in Hadoop.

Therefore, the common Hadoop tools are Map Reduce, HBase and Hive.

Solution

In the relational database model, data is stored in the form of relations or tables.

Complex data-types are not directly supported in the basic relational model because values are generally atomic.

Multivalued attributes are also not directly stored in a single attribute; they are usually represented by creating another relation.

Generalization relationships are mainly part of the ER model or enhanced ER model.

But associations between entities can be represented using relations, primary keys and foreign keys. Multiplicity like one-to-one or one-to-many can also be represented using constraints.

Therefore, the supported feature is associations with multiplicities.

Solution

Deleting tuple $(20,40)$ means employee id $20$ is deleted.

Since $Manager_id$ is a foreign key referencing $Employee_id$ with on-delete cascade, all tuples having $Manager_id=20$ must also be deleted.

So, tuple $(35,20)$ must be deleted.

Now, deleting employee id $35$ will again affect tuples having $Manager_id=35$.

So, tuple $(30,35)$ must also be deleted.

No tuple has $Manager_id=30$, so the cascade stops here.

Therefore, the other tuples that must be deleted are

$(35,20)$ and $(30,35)$

Solution

Cluster $C1$ contains the points

$(3,3),(5,5),(7,7)$

Centroid of $C1$ is

$\left(\dfrac{3+5+7}{3},\dfrac{3+5+7}{3}\right)$

$=(5,5)$

Now, Manhattan distance between $(4,4)$ and $(5,5)$ is

$|4-5|+|4-5|$

$=1+1$

$=2$

Solution

Using shortest seek time first policy, the head always moves to the nearest request.

Initial head position is

$50$

Request sequence in SSTF order will be:

$50 \to 34 \to 20 \to 19 \to 15 \to 10 \to 7 \to 6 \to 4 \to 2 \to 73$

Now, total head movement is

$|50-34|+|34-20|+|20-19|+|19-15|+|15-10|+|10-7|+|7-6|+|6-4|+|4-2|+|2-73|$

$=16+14+1+4+5+3+1+2+2+71$

$=119$

Since $1$ cylinder movement takes $1$ ms,

Total time taken is

$119$ ms

Solution

Disk is related to file system because files are stored and managed on disk.

So,

$(a) \rightarrow (iii)$

CPU is related to thread because a thread is the basic unit of CPU scheduling.

So,

$(b) \rightarrow (i)$

Memory is related to virtual address space.

So,

$(c) \rightarrow (iv)$

Interrupt is related to signal because signals are software-level notifications similar to interrupts.

So,

$(d) \rightarrow (ii)$

Therefore, correct matching is

$(a)-(iii);\ (b)-(i);\ (c)-(iv);\ (d)-(ii)$

Solution

Threads of the same process share resources like address space, code section, data section and other process resources.

But each thread has its own stack.

Also, each thread has its own register set because the CPU state of each thread must be stored separately.

So, stack and registers are not shared by threads of the same process.

Solution

Given reference string is

$1,2,1,3,7,4,5,6,3,1$

Number of frames is

$3$

Using LRU page replacement, total page faults are

$9$

Using optimal page replacement, total page faults are

$7$

Therefore, required difference is

$9-7=2$

Solution

Let the processes be $P_1,P_2,P_3$.

$P_1$: arrival time $0$, burst time $10$
$P_2$: arrival time $2$, burst time $20$
$P_3$: arrival time $6$, burst time $30$

At time $0$, $P_1$ starts executing.

At time $2$, $P_2$ arrives, but remaining time of $P_1$ is $8$, which is less than $20$. So, $P_1$ continues.

At time $6$, $P_3$ arrives, but remaining time of $P_1$ is $4$, which is less than $30$. So, $P_1$ continues.

$P_1$ completes at time $10$.

Then context switch occurs from $P_1$ to $P_2$.

$P_2$ completes at time $30$.

Then context switch occurs from $P_2$ to $P_3$.

So, total context switches are

$2$

Solution

Initial value of semaphore is

$7$

Each $P$ wait operation decreases the semaphore value by $1$.

So, after $20$ $P$ operations:

$7-20=-13$

Each $V$ signal operation increases the semaphore value by $1$.

So, after $15$ $V$ operations:

$-13+15=2$

Therefore, resulting value of semaphore is

$2$

Solution

The minimum number of page frames required depends on the maximum number of pages that may be referenced by a single instruction.

This depends on the instruction format and addressing modes.

Therefore, it is determined by the instruction set architecture.

Solution

Total tape drives are

$6$

Each process may need maximum $2$ tape drives.

For deadlock free condition:

$R \ge n(m-1)+1$

Here,

$R=6$ and $m=2$

So,

$6 \ge n(2-1)+1$

$6 \ge n+1$

$n \le 5$

Therefore, maximum value of $n$ is

$5$

Solution

In an $m \times n$ transportation problem, a basic feasible solution is called non-degenerate when it has exactly $m+n-1$ occupied cells or allocations.

These allocations should be in independent positions, means they should not form a closed loop.

So, the required blanks are $m+n-1$ and independent.

Solution

Maximum memory supported is

$4GB=2^{32}$ bytes

One word is

$2$ bytes

Since memory is word addressable, number of addressable words is

$\dfrac{2^{32}}{2}=2^{31}$

So, number of address lines required is

$31$

Solution

$x_1=1000,\ x_2=500$

Now,

$x_1+2x_2=1000+2(500)=2000\le 2000$

$x_1+x_2=1000+500=1500\le 1500$

$x_2=500\le 600$

Also,

$z=x_1+x_2=1000+500=1500$

So, all constraints are satisfied.

Solution

To select files with extension $.c$ and $.h$, we use the pattern

star dot bracket ch bracket

Here, bracket ch bracket means either $c$ or $h$.

So, it selects files ending with $.c$ and $.h$.

Then, the output is passed to $wc-l$ to count the number of lines.

Therefore, the correct command is:

cat star dot bracket ch bracket pipe wc hyphen l

Solution

$AB+A\overline{B}+\overline{A}C+AC$

Take $A$ common from first two terms:

$A(B+\overline{B})+\overline{A}C+AC$

Since,

$B+\overline{B}=1$

So,

$A(1)+\overline{A}C+AC$

$=A+\overline{A}C+AC$

Now,

$A+AC=A$

So,

$A+\overline{A}C$

Using identity $A+\overline{A}C=A+C$

Therefore, the simplified expression is:

$A+C$

The final expression does not contain $B$, so it is unaffected by the value of $B$.

Solution

Statement $P$ is false.

Defects discovered earlier are generally less expensive to fix. Defects found in later phases become more costly to correct.

Statement $Q$ is true.

A good software design should have high cohesion and low coupling.

So, only $Q$ is true.

Solution

In the poset $(Z^+,/)$, the relation is based on divisibility.

Here,

$GLB=$ greatest common divisor $($GCD$)$

$LUB=$ least common multiple $($LCM$)$

For set $A={3,9,12}$:

$GLB(A)=GCD(3,9,12)=3$

$LUB(A)=LCM(3,9,12)=36$

For set $B={1,2,4,5,10}$:

$GLB(B)=GCD(1,2,4,5,10)=1$

$LUB(B)=LCM(1,2,4,5,10)=20$

So,

$A(GLB-3,\ LUB-36)$

and

$B(GLB-1,\ LUB-20)$

Solution

Statement $P$ is false.

Defects discovered earlier are generally less expensive to fix. Defects found in later phases become more costly to correct.

Statement $Q$ is true.

A good software design should have high cohesion and low coupling.

So, only $Q$ is true.

Solution

Relation $R$ is defined as:

$(a,b)\in R$ if $a$ is a brother of $b$.

Symmetric:

If $a$ is brother of $b$, then it is not necessary that $b$ is brother of $a$.

For example, $b$ can be female. So, $b$ will not be brother of $a$.

Therefore, $R$ is not symmetric.

Transitive:

If $a$ is brother of $b$ and $b$ is brother of $c$, then $a$ is also brother of $c$.

Therefore, $R$ is transitive.

Equivalence relation:

For equivalence relation, relation must be reflexive, symmetric and transitive.

Here, $R$ is not symmetric and not reflexive.

So, $R$ is not an equivalence relation.

Partial order relation:

For partial order relation, relation must be reflexive, antisymmetric and transitive.

Here, $R$ is not reflexive.

So, $R$ is not a partial order relation.

Solution

Statement $P$ is correct.

If all paths are covered, then all statements will also be covered.

Statement $Q$ is correct.

Path coverage is stronger than statement coverage, so it generally detects more faults.

Statement $R$ is NOT correct.

Branch coverage is stronger than statement coverage, so statement coverage generally cannot detect more faults than branch coverage.

Therefore, only $R$ is not correct.

Solution

Using Kruskal’s algorithm, arrange all edges in increasing order of weight:

$2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8$

Now select the minimum weight edges without forming a cycle.

Selected edges are:

$2,\ 3,\ 4,\ 6$

Here, edge $5$ is skipped because it forms a cycle.

So, total weight of minimum spanning tree is:

$2+3+4+6=15$

Solution

Software reuse means using already existing software components, artifacts, designs, code, libraries or knowledge to develop new software.

It saves time, reduces cost and improves reliability.

Option 1 and Option 4 are related to reverse engineering.

Option 3 is related to software re-engineering.

Solution

Total number of vertices:

$V=2n+3n+n=6n$

For a tree,

$E=V-1=6n-1$

Sum of degrees:

$2n(1)+3n(2)+n(3)$

$=2n+6n+3n=11n$

By handshaking theorem,

$2E=\text{sum of degrees}$

$2(6n-1)=11n$

$12n-2=11n$

$n=2$

So,

$V=6n=6(2)=12$

$E=V-1=12-1=11$

Solution

Git is used to track changes in source code during software development.

It allows multiple developers to work on the same project and maintain different versions of files.

Git is distributed because every user has a complete copy of the repository.

Therefore, Git is a distributed version control system.

Solution

For a set with $n$ elements, total ordered pairs are:

$n^2$

Here,

$n=4$

So, total ordered pairs:

$4^2=16$

For a reflexive relation, all diagonal pairs must be present.

Number of compulsory diagonal pairs:

$4$

Remaining pairs:

$16-4=12$

Each remaining pair can be either selected or not selected.

So, number of reflexive relations:

$2^{12}$

Solution

Likelihood of repelling an attack is

$30%=0.30$

So, likelihood of not repelling an attack is

$1-0.30=0.70$

Threat probability is

$25%=0.25$

Now,

$Risk=Threat\ probability \times Attack\ success\ probability$

$Risk=0.25 \times 0.70$

$Risk=0.175$

Integrity is

$1-Risk$

$=1-0.175$

$=0.825$

Solution

Time taken by non-pipelined system for $100$ tasks:

$100\times 30=3000\ ns$

For pipeline,

Number of stages:

$k=4$

Number of tasks:

$n=100$

Clock cycle time:

$10\ ns$

Pipeline time:

$(k+n-1)\times \text{clock cycle time}$

$=(4+100-1)\times 10$

$=103\times 10$

$=1030\ ns$

Speed up:

$\dfrac{3000}{1030}=2.91$

Solution

Waterfall model is suitable when requirements are clear and well understood. Automating a manual student record maintenance system is a clear and structured requirement.

So,

$(a) \rightarrow (iv)$

Incremental development is used when basic functionality is developed first and advanced features are added later.

So,

$(b) \rightarrow (i)$

Prototyping is useful when the system is complex and requirements need to be understood through a working model. A virtual reality simulation system is suitable for prototyping.

So,

$(c) \rightarrow (iii)$

RAD means Rapid Application Development. It is suitable when software needs to be developed quickly within a short time.

So,

$(d) \rightarrow (ii)$

Therefore, the correct matching is

$(a)-(iv);\ (b)-(i);\ (c)-(iii);\ (d)-(ii)$

Solution

Memory size is $512K$ words.

$512K=512\times 1024=2^9\times 2^{10}=2^{19}$

So, address part requires $19$ bits.

There are $2$ addressing modes, direct and indirect.

So, addressing mode part requires:

$\log_2 2=1$ bit

There are $256$ registers.

So, register code part requires:

$\log_2 256=8$ bits

Total instruction size is $32$ bits.

Opcode bits:

$32-(1+8+19)$

$=32-28$

$=4$

So, bits are:

$1,4,8,19$

Solution

Adaptive maintenance is done when software needs to adapt to a changed environment.

For example, if the software must run on a new operating system, new hardware or new platform, adaptive maintenance is required.

So, the correct reason is that customers need the product to run on new platforms.

Solution

Each subfield $F1$ and $F2$ has $15$ microoperations.

To represent $15$ operations, we need:

$\lceil \log_2 15 \rceil=4$ bits

So,

$F1=4$ bits

$F2=4$ bits

Condition field $CD$ has $4$ options/status bits:

$\log_2 4=2$ bits

Branch field $BR$ has $4$ options:

$\log_2 4=2$ bits

Address space is $128$ memory words:

$\log_2 128=7$ bits

Total size of microinstruction:

$4+4+2+2+7=19$ bits

Solution

Risk monitoring is used to track risks during a software project.

It checks whether predicted risks actually occur.

It also checks whether risk avoidance or risk reduction steps are being applied properly.

It also collects risk-related information so that it can be used in future risk analysis.

Therefore, all $P,Q,R$ are correct.

Solution

Convert each number into decimal form.

$(142)_b=1\cdot b^2+4\cdot b+2$

$=b^2+4b+2$

Now,

$(112)_{b-2}=1\cdot (b-2)^2+1\cdot (b-2)+2$

$=(b-2)^2+(b-2)+2$

$=b^2-4b+4+b-2+2$

$=b^2-3b+4$

Also,

$(75)_8=7\cdot 8+5=56+5=61$

Now,

$(142)b+(112){b-2}=(75)_8$

$(b^2+4b+2)+(b^2-3b+4)=61$

$2b^2+b+6=61$

$2b^2+b-55=0$

$2b^2+11b-10b-55=0$

$b(2b+11)-5(2b+11)=0$

$(b-5)(2b+11)=0$

So,

$b=5$

Solution

Software validation checks whether the software specification actually satisfies the user's real requirements.

It answers the question:

Are we building the right product?

So, validation mainly checks inconsistencies between detailed specifications and user requirements.

Solution

Initially, accumulator register is cleared by instruction $CLA$.

So,

$AC=0000$

Next instruction is:

$ADD\ 016$

At location $016$, data is:

$C1A5$

So,

$AC=0000+C1A5=C1A5$

Next instruction is:

$BUN\ 014$

So, control goes to location $014$.

At location $014$, instruction is:

$AND\ 017$

At location $017$, data is:

$93C6$

Now,

$AC=C1A5\ AND\ 93C6$

Convert into binary:

$C1A5=1100\ 0001\ 1010\ 0101$

$93C6=1001\ 0011\ 1100\ 0110$

Now perform bitwise AND:

$1100\ 0001\ 1010\ 0101$

$AND$

$1001\ 0011\ 1100\ 0110$

$=1000\ 0001\ 1000\ 0100$

Now convert back to hexadecimal:

$1000\ 0001\ 1000\ 0100=8184$

So, final content of accumulator is:

$AC=8184$

Solution

Prim's algorithm has time complexity:

$O(E\log V)$

So,

$(a)\rightarrow(iii)$

Dijkstra's algorithm has time complexity:

$O(V^2)$

So,

$(b)\rightarrow(iv)$

Faster all-pairs shortest path algorithm has time complexity:

$O(V^3\log V)$

So,

$(c)\rightarrow(i)$

Edmonds-Karp algorithm has time complexity:

$O(VE^2)$

So,

$(d)\rightarrow(ii)$

Therefore, the correct matching is

$(a)-(iii);\ (b)-(iv);\ (c)-(i);\ (d)-(ii)$

Solution

Outer loop runs for:

$i=0,1,2,3,4$

Inner loop runs only when $j<i$.

But inside inner loop, there is a $break$ statement, so inner loop executes only one time for each valid value of $i$.

For $i=0$:

$j<0$ is false, so inner loop does not execute.

For $i=1$:

$x=x+(1+0-1)=0+0=0$

For $i=2$:

$x=x+(2+0-1)=0+1=1$

For $i=3$:

$x=x+(3+0-1)=1+2=3$

For $i=4$:

$x=x+(4+0-1)=3+3=6$

So, final value of $x$ is:

$x=6$

Solution

Heapsort is an in-place sorting algorithm.

Insertion sort is also an in-place sorting algorithm.

But merge sort is not considered in-place because it requires extra memory for merging.

So, heapsort sorts in place like insertion sort, but unlike merge sort.

Therefore,

$(P,Q)=(Insertion\ sort,\ Merge\ sort)$

Solution

In protected inheritance:

Public members of base class become protected members in derived class.

Protected members of base class also remain protected in derived class.

Private members of base class are not directly accessible in derived class.

So, member functions of class $B$ can access public and protected members of class $A$.

But object of class $B$ cannot access public base class data directly, because it becomes protected after protected inheritance.

Solution

We have,

$45=3^2\times 5$

So, prime divisors of $45$ are $3$ and $5$.

Using Euler's phi function,

$\phi(45)=45\left(1-\dfrac{1}{3}\right)\left(1-\dfrac{1}{5}\right)$

$=45\times \dfrac{2}{3}\times \dfrac{4}{5}$

$=24$

Solution

<script>

    // JavaScript code

</script>

Solution

The numbers are in the range

$0$ to $n^2-1$

Using radix sort with base $n$, each number can be represented using $2$ digits.

Radix sort takes

$O(d(n+b))$

Here,

$d=2$ and $b=n$

So,

$O(2(n+n))=O(n)$

Hence, the best running time is $O(n)$.

Solution

Solution

Depth-first search is used in topological sorting of directed acyclic graphs.

DFS is also used in finding strongly connected components, such as in Kosaraju's algorithm and Tarjan's algorithm.

So, both topological sort and strongly connected components are applications of DFS.

Solution

Solution

In double hashing, the difference between the first and second probe is decided by $h_2(k)$.

Here,

$m=701$

So,

$n=m-1=700$

Now,

$h_2(k)=1+($remainder when $123456$ is divided by $700)$

$123456=700\times 176+256$

So, remainder is $256$.

Therefore,

$h_2(k)=1+256=257$

Solution

Original image size is:

$1024 \times 768$

New width is:

$640$

Since aspect ratio remains same,

$\dfrac{\text{New Height}}{\text{New Width}}=\dfrac{\text{Original Height}}{\text{Original Width}}$

So,

$\dfrac{h}{640}=\dfrac{768}{1024}$

$h=\dfrac{768}{1024}\times 640$

$h=480$

Solution

Statement $S_1$ is true.

Class $P$ is closed under complement. Also, $P\subseteq NP$.

So,

$P\subseteq CO-NP$

Statement $S_2$ is also true.

If $P=NP$, then since $P$ is closed under complement, we would get

$NP=CO-NP$

But the statement says $NP\ne CO-NP$.

Therefore, $P\ne NP$.

Hence, both $S_1$ and $S_2$ are correct.

Solution

In DBMS, the query optimizer is responsible for choosing the most efficient way to execute a query.

It performs tasks like:

Rearranging operations

Choosing proper order of operations

Removing redundant operations

Using efficient algorithms and indexes

So, the required component is:

$query\ optimizer$

Solution

Both dynamic programming and greedy algorithms use the idea of optimal substructure.

So, characterizing the structure of an optimal solution is common to both.

Therefore, $S_1$ is common.

But computing the value of an optimal solution in bottom-up fashion is mainly a dynamic programming approach.

It is not a necessary step in greedy algorithms.

So, $S_2$ is not common.

Solution

Tables are:

$R1(x,y)$ has $50$ tuples

$R2(y,z)$ has $30$ tuples

Natural join will be performed on the common attribute:

$y$

Maximum number of tuples will occur when every tuple of $R1$ matches with every tuple of $R2$ on attribute $y$.

So, maximum number of tuples:

$50 \times 30=1500$

Solution

Property $P_1$ is the skew-symmetry property of flow.

So, $P_1$ is correct.

Property $P_2$ represents flow conservation, but in a flow network, flow conservation holds for all vertices except the source and sink.

The statement says it holds for all $u\in V$, which is not correct.

So, $P_2$ is false.

Solution

The query first selects employees whose department number is either $D1$ or $D2$.

Then,

$group\ by\ DEPTNO$

means employees are grouped department-wise.

After that,

$having\ count(*)>5$

means only those department groups will be displayed whose employee count is greater than $5$.

So, the query displays the total number of employees of departments $D1$ and $D2$ only if their count is greater than $5$.

Solution

Statement $S_1$ is true by Euler's theorem.

If $a\in Z_n^*$, then $a$ and $n$ are relatively prime.

So,

$a^{\phi(n)}\equiv 1\ (\text{mod }n)$

Now consider $S_2$.

For prime $p$, Fermat's theorem gives

$a^{p-1}\equiv 1\ (\text{mod }p)$

for $a\in Z_p^*$.

But $S_2$ says

$a^p\equiv 1\ (\text{mod }p)$

This is not generally true.

Actually,

$a^p\equiv a\ (\text{mod }p)$

So, $S_2$ is false.

Solution

In the given ER diagram:

Entity $R_1$ has attributes $A$, $B$, and $C$.

Here, $B$ is shown as a double oval, so $B$ is a multivalued attribute.

A multivalued attribute requires a separate table.

So, for $R_1$:

One table for entity $R_1$

One separate table for multivalued attribute $B$

Entity $R_2$ has attributes $X$ and $Y$.

So, one table is required for $R_2$.

The relationship between $R_1$ and $R_2$ is $1:M$.

For a $1:M$ relationship, no separate relationship table is required. We can add the primary key of the $1$ side as a foreign key in the $M$ side table.

Total number of tables:

$1$ table for $R_1$

$1$ table for multivalued attribute $B$

$1$ table for $R_2$

Total:

$1+1+1=3$

Solution

A compiler stores information about variables, functions, identifiers and their attributes in a symbol table.

Attributes may include name, type, scope, address and value.

Therefore, the data structure used for managing variables and their attributes is symbol table.

Solution

Initial value of semaphore:

$S=8$

Each wait $()$ operation decreases semaphore value by $1$.

After $3$ wait $()$ operations:

$S=8-3=5$

Each signal $()$ operation increases semaphore value by $1$.

After $4$ signal $()$ operations:

$S=5+4=9$

Solution

Given expression is

$(ij)+(e+f)(a*b+c)$

Count each arithmetic operation:

$i*j$ gives $1$ operation.

$e+f$ gives $1$ operation.

$a*b$ gives $1$ operation.

$a*b+c$ gives $1$ operation.

$(e+f)(ab+c)$ gives $1$ operation.

Finally,

$(ij)+[(e+f)(a*b+c)]$ gives $1$ operation.

Total operations:

$1+1+1+1+1+1=6$

Solution

An encryption algorithm mainly needs:

Plain message

Key

Encryption method

After encryption, it produces ciphertext.

But user details are not required for the encryption algorithm.

Solution

Constant folding is a compiler optimization technique.

In this technique, constant expressions are evaluated at compile time.

Here,

$4*2.14=8.56$

So, replacing $4*2.14$ by $8.56$ is constant folding.

Solution

Linux operating system supports preemptive priority scheduling.

Linux also supports time-sharing CPU scheduling for normal user processes.

So, both preemptive priority scheduling and time-sharing CPU scheduling are supported by Linux.

Solution

A shift-reduce parser uses an input buffer to read the input string.

It uses a stack to store grammar symbols during parsing.

In table-driven shift-reduce parsing, a parse table is also used to decide shift and reduce actions.

Therefore, shift-reduce parser consists of input buffer, stack and parse table.

Solution

TLB access time $=20$ ns

Memory access time $=80$ ns

Hit ratio $=80%=0.8$

Miss ratio $=20%=0.2$

For TLB hit:

Effective time $=20+80=100$ ns

For TLB miss:

First TLB is checked, then page table is accessed from memory, then actual memory is accessed.

Effective time $=20+80+80=180$ ns

Now,

Effective memory access time:

$EAT=0.8(100)+0.2(180)$

$EAT=80+36$

$EAT=116$ ns

Solution

The regular expression is

$a^*b(a+b)$

It means:

Any number of $a$'s, followed by one $b$, followed by either $a$ or $b$.

So, strings accepted are like:

$ba,\ bb,\ aba,\ abb,\ aaba,\ aabb$

Minimum DFA states needed:

State $q_0$: Initial state, reads any number of $a$'s.
State $q_1$: After reading required $b$.
State $q_2$: Final state after reading last symbol $a$ or $b$.
State $q_d$: Dead state for extra or invalid symbols.

Thus, total minimum states are

$4$

Solution

Solution

For $(a)$:

$L_3$ is a recursive language.

Complement of a recursive language is also recursive.

So,

$\overline{L_3}$ is recursive.

Also, $L_4$ is recursively enumerable.

Union of a recursive language and a recursively enumerable language is recursively enumerable.

Therefore,

$\overline{L_3}\cup L_4$ is recursively enumerable.

So,

$(a)\rightarrow(ii)$

For $(b)$:

$L_2$ is context-free language.

Every context-free language is recursive.

So, complement of $L_2$ is also recursive.

Also, $L_3$ is recursive.

Union of two recursive languages is recursive.

Therefore,

$\overline{L_2}\cup L_3$ is recursive.

So,

$(b)\rightarrow(iii)$

For $(c)$:

$L_1$ is regular.

Regular languages are closed under Kleene star.

So,

$L_1^*$ is regular.

Intersection of a regular language and a context-free language is context-free.

Therefore,

$L_1^*\cap L_2$ is context-free.

So,

$(c)\rightarrow(i)$

Hence, correct matching is

$(a)-(ii);\ (b)-(iii);\ (c)-(i)$

Solution

Co-operating processes can communicate with each other using two main IPC models:

Shared memory model

Message passing model

In shared memory, processes communicate by sharing a common memory area.

In message passing, processes communicate by sending and receiving messages.

So, interprocess communication can be done using both shared memory and message passing model.

Solution

To decide whether a context-free language is finite or infinite, we can convert the CFG into a non-redundant CFG in CNF.

Usually, the CNF grammar is considered for $L-{\Lambda}$.

After converting into CNF, we check whether there is any recursive derivation or cycle among variables.

If such a recursive structure exists, then the language is infinite.

If no such recursive structure exists, then the language is finite.

So, the correct construction is given in statement $(c)$.

Solution

Time quantum $=2$ ms

Gantt chart:

$P1(0-2),\ P2(2-4),\ P1(4-5),\ P2(5-7),\ P3(7-9),\ P3(9-11),\ P3(11-12)$

Completion time:

$CT(P1)=5$

$CT(P2)=7$

$CT(P3)=12$

Turnaround time:

$TAT=CT-AT$

For $P1$:

$TAT=5-0=5$

For $P2$:

$TAT=7-2=5$

For $P3$:

$TAT=12-5=7$

Average turnaround time:

$\dfrac{5+5+7}{3}=\dfrac{17}{3}=5.66$

Waiting time:

$WT=TAT-BT$

For $P1$:

$WT=5-3=2$

For $P2$:

$WT=5-4=1$

For $P3$:

$WT=7-5=2$

Average waiting time:

$\dfrac{2+1+2}{3}=\dfrac{5}{3}=1.66$

Solution

Given grammar is

$S\to XY$

$X\to YaY\mid a$

$Y\to bbX$

Since $S\to XY$, the string contains one part from $X$ and one part from $Y$.

Now, $X$ can generate at least one $a$.

Also, $Y\to bbX$, so $Y$ also contains one $X$, which again gives at least one $a$.

Therefore, every string generated by $S$ has at least two $a$'s.

So, statement $(c)$ is true.

Also, every use of $Y$ contributes $bb$, that is $2$ occurrences of $b$.

So, the number of $b$'s is always in multiple of $2$.

Therefore, statement $(d)$ is true.

The grammar contains $bb$, so alternate $a$ and $b$ condition is false.

Also, consecutive three $a$'s are not necessarily produced.

Solution

Parameters can be passed to the operating system through system calls using different methods.

Registers can be used, but registers are limited in number.

For passing any number of parameters, better methods are:

Block or table in main memory

Stack

So, any number of parameters can be passed using block in main memory and stack.

Solution

Statement $(a)$ is decidable because emptiness of a context-free grammar is decidable.

Statement $(b)$ is also decidable in this form, because recursively enumerable languages are closed under union, and the condition can be satisfied by suitable Turing machines.

Statement $(c)$ is decidable because the tape usage is bounded by $2^{|\omega|}$. With bounded tape, the number of configurations becomes finite, so we can decide whether $M$ accepts $\omega$ within this bound.

Therefore, all three statements are decidable.

Solution

JVM executes Java bytecode.

For execution, JVM mainly needs:

Class loader to load the class files

Java Interpreter to interpret and execute bytecode

So, JVM needs class loader and Java interpreter.

Solution

A recursive language is decided by a Turing machine that halts on every input.

If $\omega\in L$, then the machine halts and accepts $\omega$.

If $\omega\notin L$, then the machine halts and rejects $\omega$.

Rejecting means it halts without reaching an acceptable state.

Therefore, the correct condition is:

If $\omega\notin L$, then $M$ halts without reaching an acceptable state.

Solution

In this restaurant ordering system, the minimum important objects are:

Customer

Menu

Order

Kitchen

Bill

Messages are exchanged among these objects during order placement, food preparation, serving, bill generation and payment.

So, at least $5$ objects are required in the sequence diagram.

Solution

In a fully connected network, every pair of nodes has a direct link.

So, the number of direct links is equal to the number of ways of choosing $2$ nodes from $n$ nodes.

Therefore,

${}^{n}C_2=\dfrac{n(n-1)}{2}$

Solution

An activity chart represents a project schedule as a directed graph.

In project scheduling, the critical path is the longest path in the project network.

It contains dependent tasks because one task depends on the completion of another task.

The critical path defines the total project duration.

So, the correct sequence is:

$Activity,\ Longest,\ Dependent,\ Duration$

Solution

RARP stands for Reverse Address Resolution Protocol.

It is used when a client knows its MAC address but wants to find its IP address.

The client sends a broadcast request with its MAC address and receives the corresponding IP address in reply.

Solution

We have to find:

$7^{17}\bmod 561$

Now,

$7^2=49$

$7^4=49^2=2401$

$2401\bmod 561=157$

So,

$7^4\bmod 561=157$

Now,

$7^8\bmod 561=157^2\bmod 561$

$157^2=24649$

$24649\bmod 561=526$

So,

$7^8\bmod 561=526$

Now,

$7^{16}\bmod 561=526^2\bmod 561$

$526^2=276676$

$276676\bmod 561=103$

So,

$7^{16}\bmod 561=103$

Now,

$7^{17}\bmod 561=7^{16}\times 7\bmod 561$

$=103\times 7\bmod 561$

$=721\bmod 561$

$=160$

Solution

Propagation delay is given by

$\text{Propagation delay}=\dfrac{\text{Distance}}{\text{Propagation speed}}$

Here,

Distance $=800$ km

Speed $=200000$ km/second

So,

$\text{Propagation delay}=\dfrac{800}{200000}$

$=0.004$ seconds

$=4$ milliseconds

Solution

A clique in an undirected graph is a subset of vertices in which every pair of distinct vertices is connected by an edge.

That means if we take any two vertices from $V'$, there must be an edge between them.

So, a clique forms a complete subgraph.

Solution

Class B default mask is

$255.255.0.0$

or

$/16$

We need at least $500$ subnets.

$2^8=256<500$

$2^9=512\ge 500$

So, we need to borrow $9$ bits for subnetting.

New prefix length is

$16+9=25$

So, subnet mask is

$/25=255.255.255.128$

Host bits left:

$32-25=7$

Usable hosts per subnet:

$2^7-2=126$

This satisfies about $100$ usable hosts.

Solution

In an unsorted array implementation of priority queue:

For Insert operation, we can insert the new element directly at the end of the array.

So, worst case time for Insert is:

$\theta(1)$

For Extract-min operation, the array is unsorted, so we must search the entire array to find the minimum element.

So, worst case time for Extract-min is:

$\theta(n)$

Solution

Loopback addresses belong to the $127.0.0.0/8$ range.

This range belongs to class A, not class B.

So, statement $P$ is false.

Loopback address is used by a host to send packets to itself for testing and internal communication.

So, statement $Q$ is true.

Solution

In a B-tree of order $M$:

Number of keys $=M-1$

Memory used by keys:

$(M-1)\times 32=32M-32$

Number of branches in non-leaf node $=M$

Memory used by branches:

$M\times 4=4M$

Total memory requirement:

$(32M-32)+4M$

$=36M-32$

Solution

In the OSI model, encryption and decryption are generally associated with the presentation layer.

But in the TCP/IP model, there is no separate presentation layer.

Its functions are included in the application layer.

Therefore, encryption and decryption are functions of the application layer in TCP/IP model.

Solution

Let,

$m=\lg n$

So,

$n=2^m$

Also,

$\sqrt n=2^{m/2}$

Now define:

$S(m)=T(2^m)$

Then recurrence becomes:

$S(m)=4S(m/2)+m^2$

Using Master Theorem:

$a=4,\ b=2$

$m^{\log_b a}=m^{\log_2 4}=m^2$

Here,

$f(m)=m^2$

So,

$S(m)=\theta(m^2\lg m)$

Now put $m=\lg n$:

$T(n)=\theta((\lg n)^2\lg(\lg n))$

So,

$T(n)=\theta(\lg^2 n\lg\lg n)$

Solution

At the link layer, the data unit is called a frame.

So, statement $P$ is true.

At the network layer, the data unit is generally called a packet or datagram.

A segment is used at the transport layer.

So, statement $Q$ is false.

Solution

In shortest path relaxation:

$d[v]=\min(d[v],d[u]+w[u,v])$

Given:

$d[v]=29$

$d[u]=15$

$w[u,v]=12$

So,

$d[u]+w[u,v]=15+12=27$

Now,

$d[v]=\min(29,27)$

$d[v]=27$

Solution

Class C addresses start with bits $110$.

So, first $3$ bits are fixed.

Remaining bits are

$32-3=29$

Total class C addresses are

$2^{29}$

Total IPv4 addresses are

$2^{32}$

So, fraction of class C address space is

$\dfrac{2^{29}}{2^{32}}=\dfrac{1}{8}$

Now,

$\dfrac{1}{8}\times 100=12.5%$

Solution

Dijkstra's algorithm finds the shortest path based on minimum total weight.

It does not necessarily choose the path with the least number of vertices.

A path with more vertices can have smaller total weight than a path with fewer vertices.

Dijkstra's algorithm also requires all edge weights to be non-negative.

So, the statement “Shortest path always passes through least number of vertices” is not true.

Solution

IP spoofing means creating IP packets with a false or forged source IP address.

It is used to hide the real sender or impersonate another system.

Therefore, injecting packets with a false source address is called IP spoofing.

Solution

Using the Fast Fourier Transform $($FFT$)$ method, polynomial multiplication can be done faster than the normal multiplication method.

Normal polynomial multiplication takes:

$\theta(n^2)$

But FFT based polynomial multiplication takes:

$\theta(n\lg n)$

Solution

In RSA, a message can be encrypted using the private key and verified or decrypted using the public key.

This proves that the message was created by the holder of the private key.

This property is used in digital signatures.

Solution

In $G_2$, productions are:

$S\rightarrow aSb\mid bSa\mid SS\mid \lambda$

In $G_4$, productions are:

$S\rightarrow aSb\mid bSa\mid SS\mid SSS\mid \lambda$

The only extra production in $G_4$ is:

$S\rightarrow SSS$

But this production is already possible using $S\rightarrow SS$ again and again.

For example:

$S\rightarrow SS\rightarrow SSS$

So, $SSS$ does not generate anything extra.

Hence, $G_2$ and $G_4$ generate the same language.

Solution

The root node is a $MAX$ node.

In minimax method:

$MAX$ node selects the maximum value from its children.

$MIN$ node selects the minimum value from its children.

From the left subtree, the minimum level gives values such that the final value of the left side becomes

$7$

From the right subtree, the available minimum values make the right side value less than or equal to $5$.

Now, root is a $MAX$ node, so it selects maximum of left and right subtree values.

$\max(7,\le 5)=7$

Hence, the value of the root node is

$7$

Solution

Given language is:

$L={a^n b^{n-3}\mid n>2}$

When $n=3$:

$a^3b^0=aaa$

When $n=4$:

$a^4b^1=aaaab$

When $n=5$:

$a^5b^2=aaaaabb$

So, every string starts with at least three $a$ symbols.

After that, for every extra $a$, one $b$ is added at the end.

Grammar:

$S\rightarrow aaaA$

$A\rightarrow aAb\mid \lambda$

If $A\rightarrow \lambda$, then string is:

$aaa$

If $A\rightarrow aAb$, then it generates:

$aaaab,\ aaaaabb,\ldots$

So, this grammar generates $a^n b^{n-3}$ for $n>2$.

Solution

Greedy best-first search selects the node with minimum heuristic value.

So,

$(a)\rightarrow(ii)$

Lowest cost-first search selects the node with minimum path cost.

So,

$(b)\rightarrow(iii)$

$A^*$ algorithm selects the node using cost plus heuristic value.

So,

$(c)\rightarrow(i)$

Therefore, the correct matching is

$(a)-(ii);\ (b)-(iii);\ (c)-(i)$

Solution

From production:

$S\rightarrow 0A$

and

$A\rightarrow 00A\mid \lambda$

So, $A$ can generate:

$\lambda,\ 00,\ 0000,\ldots$

Hence, $S$ generates:

$0,\ 000,\ 00000,\ldots$

This is represented by:

$(00)^*0$

Now consider:

$S\rightarrow 0BB$

But $B$ has productions:

$B\rightarrow 1B\mid 11C$

and

$C\rightarrow B$

Here, $B$ never terminates into $\lambda$ or any final terminal-only string.

So, this branch does not generate any valid finite string.

Hence, the grammar generates only:

$L((00)^*0)$

Solution

STRIPS is used in AI planning.

In STRIPS, actions are represented using:

Preconditions
Add list
Delete list

So, it mainly describes how actions change the state of the world.

Therefore, STRIPS representation is an action-centric representation.

Solution

Solution

For fuzzy conjunction and fuzzy disjunction to be dual, they must satisfy De Morgan type relation.

The duality condition is:

$t(x,y)=1-s(1-x,1-y)$

Solution

Given language:

$L={a^n b^n\mid n\ge 0}$

This is a context free language.

Now check each statement.

For $S_1$:

$L^2=L\cdot L$

Context free languages are closed under concatenation.

So, $L^2$ is also context free.

Hence, $S_1$ is true.

For $S_2$:

$L^k$ means concatenation of $L$ with itself $k$ times.

For any fixed $k\ge 1$, context free languages are closed under finite concatenation.

So, $L^k$ is context free.

Hence, $S_2$ is true.

For $S_3$:

$L^*$ is context free because context free languages are closed under Kleene star.

Also, for this specific language $L={a^n b^n\mid n\ge 0}$, its complement $\overline{L}$ is also context free.

So, $\overline{L}$ and $L^*$ both are context free languages.

Hence, $S_3$ is true.

Therefore, all three statements $S_1,\ S_2$ and $S_3$ are correct.

Solution

In fuzzy sets, a higher $\alpha$-cut gives a smaller or equal set.

Since,

$\alpha_1<\alpha_2$

the cut at $\alpha_1$ will contain all elements of the cut at $\alpha_2$.

So,

$A_{\alpha_1}\supseteq A_{\alpha_2}$

Solution

$L_1={a^n b^n c^m}\cup{a^n b^m c^m}$ is a standard example of an inherently ambiguous language.

Reason: strings of the form $a^n b^n c^n$ can be generated from both parts:

First part: $a^n b^n c^m$ when $m=n$

Second part: $a^n b^m c^m$ when $m=n$

So, ambiguity is unavoidable for $L_1$.

Now,

$L_2={ww^R\mid w\in{a,b}^*}$ is the language of even length palindromes.

This language is context-free and not inherently ambiguous.

Solution

Defuzzification converts fuzzy output into a crisp value.

Mean of maximum is a defuzzification method.

Centre of area is also a defuzzification method.

Height method is also used for defuzzification.

Therefore, all $M1,M2$ and $M3$ are defuzzification methods.

Solution

In Chomsky Normal Form, every production must be of the form:

$A\rightarrow BC$

or

$A\rightarrow a$

If a production has maximum $K$ symbols on the right side, then to convert it into binary productions, at most $K-1$ productions are needed.

So, for $|P|$ productions, maximum productions required are:

$(K-1)|P|$

Also, for terminals, we may need separate productions for each terminal.

Number of terminals $=|T|$

So, total maximum number of productions:

$(K-1)|P|+|T|$

Solution

Genetic algorithms are based on the idea of natural evolution.

They use selection to choose better individuals.

They use reproduction to create new generations.

They use mutation to introduce variations.

So, evolution, selection, reproduction and mutation are all related to genetic algorithms.

Solution

The Chomsky hierarchy and decidability relation is:

Context-free languages $\subseteq$ Context-sensitive languages

Context-sensitive languages $\subseteq$ Recursive languages

Recursive languages $\subseteq$ Recursively enumerable languages

So,

$L_1\subseteq L_2\subseteq L_4\subseteq L_3$

Solution

A self-organizing feature map is an unsupervised neural network.

It groups similar input patterns without using labelled output data.

Back-propagation is generally supervised learning.

Solution

Checking whether two Turing machines accept the same language means checking:

$L(M_1)=L(M_2)$

This is undecidable.

So, $S_1$ is true.

For $S_2$:

Checking whether:

$L(M_1)\subseteq L(M_2)$

for arbitrary Turing machines is also undecidable.

So, $S_2$ is also true.

Solution

Given,

$f(x)=\dfrac{1}{1+e^{-2x}}$

Differentiate with respect to $x$:

$f'(x)=\dfrac{2e^{-2x}}{(1+e^{-2x})^2}$

At $x=0$,

$e^{-2(0)}=e^0=1$

So,

$f'(0)=\dfrac{2}{(1+1)^2}$

$=\dfrac{2}{4}$

$=\dfrac{1}{2}$

Solution

For pair $(A,B)$:

Take sequence of indices:

$3,4,1$

From $A$ side:

$A_3A_4A_1=11\ 101\ 001=11101001$

From $B$ side:

$B_3B_4B_1=111\ 010\ 01=11101001$

Both strings are equal.

So, pair $(A,B)$ has a PCP solution.

For pair $(C,D)$:

Starting must be with first pair because only it gives matching prefix:

$C_1=00,\ D_1=0$

After this, extra $0$ remains on upper side. Repeating first pair keeps increasing extra zeros, and other pairs do not match the required prefix properly.

So, pair $(C,D)$ has no PCP solution.

Solution

Reinforcement learning is generally formalized using a Markov decision process.

In a Markov decision process, the agent interacts with an environment using states and actions.

The agent knows the set of possible states and the set of possible actions.

Therefore, the blanks are:

Markov decision process, states

Solution

Classful IP address ranges are:

Class A: $0$ to $127$

Class B: $128$ to $191$

Class C: $192$ to $223$

Class D: $224$ to $239$

Given last address is:

$223.255.255.255$

This belongs to Class C.

Solution

Total routers:

$8\times 9\times 10=720$

For each router, routing table entries are counted as:

Entries for routers in its own region:

$10$

Entries for other regions in same cluster:

$9-1=8$

Entries for other clusters:

$8-1=7$

Total entries:

$10+8+7=25$

Solution

A Bluetooth piconet consists of:

$1$ master node

Up to $7$ active slave nodes

So, the blanks are:

one and seven

Therefore, the correct answer is

Solution

Throughput means actual data transferred per second.

Given,

Number of frames per minute $=12000$

Bits per frame $=10000$

Total bits per minute:

$12000\times 10000=120000000$

Now convert into bits per second:

$\dfrac{120000000}{60}=2000000\ bps$

Solution

ICANN stands for:

Internet Corporation for Assigned Names and Numbers

It manages domain names, IP address allocation and related internet identifiers.

Solution

In probability theory,

$P(A)+P(\neg A)=1$

But in Dempster-Shafer theory, belief values need not add up to $1$ because some uncertainty may remain unassigned.

So,

$Bel(A)+Bel(\neg A)\le 1$

Solution

For $S_1$:

$\forall xP(x)\vee \forall xQ(x)$ means either $P(x)$ is true for all $x$, or $Q(x)$ is true for all $x$.

But $\forall x(P(x)\vee Q(x))$ means for every $x$, at least one of $P(x)$ or $Q(x)$ is true.

These two statements are not logically equivalent.

So, $S_1$ is true.

For $S_2$:

$\exists xP(x)\wedge \exists xQ(x)$ means there exists some $x$ for $P(x)$ and there exists some $x$ for $Q(x)$. These may be different values.

But $\exists x(P(x)\wedge Q(x))$ means there exists the same $x$ for which both $P(x)$ and $Q(x)$ are true.

These two statements are also not logically equivalent.

So, $S_2$ is true.

Solution

In the given game tree:

$\square$ represents MAX node

$\circ$ represents MIN node

So, we evaluate the tree from bottom to top using the minimax rule.

At MIN node, minimum value is selected.

At MAX node, maximum value is selected.

From the left side of the tree:

$\min(17,19)=17$

After applying MAX and MIN levels, the left subtree gives value:

$17$

From the right side of the tree:

The available minimum values include $15$ and $14$, so the right subtree gives a value less than $17$.

At the root node, we have MAX node.

So root will select maximum value:

$\max(17,14)=17$

Therefore, the value of the root node is:

$17$

Solution

Additive rule models combine the contribution of rules in an additive manner.

Takagi-Sugeno-Kang model is an additive rule model.

Kosko's Standard Additive Model $($SAM$)$ is also an additive rule model.

Mamdani model is not generally considered an additive rule model in this classification.

So, examples of additive rule model are:

$M_2$ and $M_3$

Solution

Given:

$t(x,y)=1-s(1-x,1-y)$

So,

$s(x,y)=1-t(1-x,1-y)$

Now,

$t(1-x,1-y)=\dfrac{(1-x)(1-y)}{(1-x)+(1-y)-(1-x)(1-y)}$

Numerator:

$(1-x)(1-y)=1-x-y+xy$

Denominator:

$(1-x)+(1-y)-(1-x)(1-y)$

$=2-x-y-(1-x-y+xy)$

$=1-xy$

So,

$t(1-x,1-y)=\dfrac{1-x-y+xy}{1-xy}$

Now,

$s(x,y)=1-\dfrac{1-x-y+xy}{1-xy}$

$s(x,y)=\dfrac{1-xy-1+x+y-xy}{1-xy}$

$s(x,y)=\dfrac{x+y-2xy}{1-xy}$

Solution