---

Solution

---

Solution

Using Kruskal's algorithm, edges are selected in increasing order of weight.

From the graph:

$a-b = 1$

$d-f = 1$

$b-f = 2$

$d-c = 2$

$d-e = 3$

So, the valid order must follow:

Weight $1$ edges first:

$I, II$ in any order

Then weight $2$ edges:

$III, IV$ in any order

Then weight $3$ edge:

$V$

Now check option (c):

II, I, III, V, IV

Here, edge $V = d-e$ has weight $3$, but edge $IV = d-c$ has weight $2$.

So, selecting $V$ before $IV$ violates Kruskal's increasing weight rule.

Therefore, this order cannot be used.

---

Solution

While simplifying a CFG, the safest order is:

First remove $\epsilon$-productions.

Then remove unit productions.

Finally remove useless symbols and productions.

Reason:

After removing $\epsilon$-productions, new unit productions may be created.

After removing unit productions, some symbols may become useless.

So, useless symbols should be removed at the end.

Correct order is:

$\epsilon$-productions → Unit productions → Useless symbols and productions

---

Solution

Physical layer:

Transmission of raw bits over communication channel.

So, II comes first.

Data Link layer:

Transforms raw bits into frames.

So, I comes second.

Network layer:

Controls and monitors subnet.

So, IV comes third.

Transport layer:

Provides connection-oriented or connection-less data transmission.

So, V comes fourth.

Application layer:

Handles user interfaces.

So, III comes last.

---

Solution

Statement I:

Artificial Neural Network is a machine learning technique.

So, statement I is correct.

Statement II:

ANN is useful for large datasets because it can learn complex patterns from data.

So, statement II is correct.

Statement III:

Neural networks can automatically learn important features from data without manual feature programming.

So, statement III is correct.

Statement IV:

ANN is inspired by the human brain and nervous system.

So, statement IV is correct.

Therefore, all statements are correct.

---

Solution

Check each case one by one.

Case 1: Suppose P is guilty.

P says: Q did it → False
Q says: S did it → False
R says: I did not do it → True
S says: Q lied → True

Here, two statements are false. So, P is not guilty.

Case 2: Suppose Q is guilty.

P says: Q did it → True
Q says: S did it → False
R says: I did not do it → True
S says: Q lied → True

Here, exactly one statement is false.

So, Q can be guilty.

Case 3: Suppose R is guilty.

P says: Q did it → False
Q says: S did it → False
R says: I did not do it → False
S says: Q lied → True

Here, three statements are false. So, R is not guilty.

Case 4: Suppose S is guilty.

P says: Q did it → False
Q says: S did it → True
R says: I did not do it → True
S says: Q lied → False

Here, two statements are false. So, S is not guilty.

Therefore, the guilty person is Q.

---

Solution

Raster scan display forms an image using many small dots called pixels.

These pixels are scanned line by line from left to right and top to bottom.

Television display also works in a similar raster scanning manner.

So, Assertion A is true.

Reason R correctly explains why raster scan devices can use television monitors.

So, Reason R is also true and it is the correct explanation of Assertion A.

---

Solution

In Round Robin scheduling, each process gets CPU for one time quantum.

Given:

Time quantum $=4$ ms

Number of processes $=20$

Maximum waiting time occurs for the last process in the ready queue.

Before the last process gets CPU, the other $19$ processes will execute.

So,

Maximum waiting time $=19 \times 4$

$=76$ ms

---

Solution

For minimum-weight vertex cover, we can write an integer linear programming formulation.

Its LP relaxation can be used to find a lower bound.

So, Statement 1 is correct.

But for minimum-weight vertex cover, the objective should be minimized, not maximized.

Correct objective should be:

$ \text{Minimize } \sum_{v \in V} w(v)x(v) $

Statement 2 says maximizing the objective, so Statement 2 is incorrect.

---

Solution

When the server crashes and reboots, the server loses the old TCP connection state.

Statement I:

If the client is only waiting to receive data and TCP keepalive timer is not used, then the client may not immediately know that the server has crashed.

So, the client may wait indefinitely.

Therefore, Statement I is true.

Statement II:

After reboot, if the client sends a packet for the old TCP connection, the server will not recognize that old connection.

In this case, the server sends a reset segment, that is $RST$, not a $FIN$ segment.

$FIN$ is used for normal connection termination.

$RST$ is used when the connection is invalid or not recognized.

Therefore, Statement II is false.

---

Solution

Given block:

$130.56.0.0/16$

Total host bits:

$32-16=16$

Number of required subnets:

$1024=2^{10}$

So, $10$ bits are borrowed for subnetting.

Remaining host bits:

$16-10=6$

Number of addresses in each subnet:

$2^6=64$

---

Solution

Given network block is:

$130.56.0.0/16$

So, the network prefix part is:

$130.56$

---

Solution

$64$ addresses

So, first subnet starts from:

$130.56.0.0$

Since each subnet has $64$ addresses, the first subnet range is:

$130.56.0.0$ to $130.56.0.63$

Therefore, first address is:

$130.56.0.0$

Last address is:

$130.56.0.63$

---

Solution

Original prefix is:

$/16$

Required subnets:

$1024=2^{10}$

So, new prefix length is:

$16+10=26$

Therefore, subnet prefix is:

$/26$

Subnet mask for $/26$ is:

$255.255.255.192$

---

Solution

Given block is:

$130.56.0.0/16$

Number of subnets required:

$1024 = 2^{10}$

So, new prefix is:

$/16 + 10 = /26$

For $/26$, each subnet has:

$2^{32-26} = 2^6 = 64$ addresses

So, subnet block size is:

$64$

In the last octet, subnets will be:

$0, 64, 128, 192$

The last subnet of the whole block $130.56.0.0/16$ will be in the last third octet:

$255$

So, last subnet starts at:

$130.56.255.192$

Since block size is $64$, it ends at:

$130.56.255.255$

---

Solution

$M1$ is used when the machine is in state $q1$ and reads symbol $c$.

In this stage, the machine has already marked one $a$ as $X1$ and is searching for the corresponding $c$.

So, when it finds $c$, it marks it as $X2$ and moves left to return back.

Therefore,

$M1=(q2,X2,L)$

---

Solution

$M2$ is in state $q0$ on symbol $X1$.

In standard Turing Machine design for this language, $X1$ represents an already marked $a$.

So, the machine should skip $X1$ and move right to search for the next unmarked $a$.

Correct move should be:

$(q0,X1,R)$

But this option is not present in the given options.

---

Solution

$M3$ is in state $q3$ on symbol $a$.

State $q3$ is used after matching all $a$'s with $c$'s. Now the machine works on $b$'s and $d$'s.

So, if the machine sees an unmarked $a$ in state $q3$, it means the string is not in the correct form.

Hence, it is an error entry.

---

Solution

$M4$ is in state $q5$ on symbol $Y1$.

Here, $Y1$ represents a marked $b$.

After marking one corresponding $d$ as $Y2$, the machine moves left and reaches $Y1$.

Now it should move right and again go to state $q3$ to search for the next unmarked $b$.

Therefore,

$M4=(q3,Y1,R)$

---

Solution

$M5$ is in state $q4$ on symbol $X2$.

Here, $X2$ represents an already marked $c$.

In state $q4$, the machine is moving right to find an unmarked $d$ corresponding to a marked $b$.

So, when it sees $X2$, it simply skips it and moves right.

Therefore,

$M5=(q4,X2,R)$

---

Solution

---

Solution

Let the boxes be $B_1, B_2, B_3$ and event $E$ be drawing $1$ white and $1$ red ball.

Since one box is chosen randomly,

$P(B_1)=P(B_2)=P(B_3)=\frac{1}{3}$

For first box,

$P(E|B_1)=\frac{\binom{2}{1}\binom{4}{1}}{\binom{9}{2}}=\frac{8}{36}=\frac{2}{9}$

For second box,

$P(E|B_2)=\frac{\binom{3}{1}\binom{2}{1}}{\binom{7}{2}}=\frac{6}{21}=\frac{2}{7}$

For third box,

$P(E|B_3)=\frac{\binom{4}{1}\binom{3}{1}}{\binom{8}{2}}=\frac{12}{28}=\frac{3}{7}$

Using Bayes theorem,

$P(B_1|E)=\frac{P(B_1)P(E|B_1)}{P(B_1)P(E|B_1)+P(B_2)P(E|B_2)+P(B_3)P(E|B_3)}$

$P(B_1|E)=\frac{\frac{1}{3}\times\frac{2}{9}}{\frac{1}{3}\times\frac{2}{9}+\frac{1}{3}\times\frac{2}{7}+\frac{1}{3}\times\frac{3}{7}}$

$P(B_1|E)=\frac{\frac{2}{9}}{\frac{2}{9}+\frac{2}{7}+\frac{3}{7}}$

$P(B_1|E)=\frac{\frac{2}{9}}{\frac{59}{63}}=\frac{14}{59}=0.237$

---

Solution

In synchronous interleaved memory organization,

For $m\ll n$,

$t=m\cdot \frac{T}{n}$

For $m\gg n$,

$t=T$

---

Solution

A crossbar switch provides a separate path between processor and memory module.

So, multiple connections can be made at the same time without blocking each other.

Therefore, crossbar switch is a non blocking network.

---

Solution

For $7$ bit Hamming code, parity positions are

$1,2,4$

Data positions are

$3,5,6,7$

Given data bits are

$1101$

So,

$D_1=1,\ D_2=1,\ D_3=0,\ D_4=1$

Arrange them as:

$P_1\ P_2\ D_1\ P_4\ D_2\ D_3\ D_4$

$=P_1\ P_2\ 1\ P_4\ 1\ 0\ 1$

For even parity,

$P_1$ checks positions $1,3,5,7$

$P_1+1+1+1=\text{even}$

$P_1=1$

$P_2$ checks positions $2,3,6,7$

$P_2+1+0+1=\text{even}$

$P_2=0$

$P_4$ checks positions $4,5,6,7$

$P_4+1+0+1=\text{even}$

$P_4=0$

Therefore, Hamming code is

$1010101$

---

Solution

Given expression:

$ABC+A\overline{B}CD+E\overline{F}+AD$

Number of inputs in product terms:

$ABC=3$

$A\overline{B}CD=4$

$E\overline{F}=2$

$AD=2$

Total inputs for AND gates:

$3+4+2+2=11$

There are $4$ product terms, so OR gate needs $4$ inputs.

Total gate inputs:

$11+4=15$

---

Solution

In an octal to binary encoder, there are $8$ input lines and $3$ output lines.

The outputs represent binary form of input lines $D_0$ to $D_7$.

Standard equations are:

$A_2=D_4+D_5+D_6+D_7$

$A_1=D_2+D_3+D_6+D_7$

$A_0=D_1+D_3+D_5+D_7$

So, the given circuit represents an Octal to Binary encoder.

---

Solution

Total capacity $=$ Number of tracks $\times$ Number of sectors $\times$ Bytes per sector

$163840=80\times \text{Number of sectors}\times 128$

$\text{Number of sectors}=\frac{163840}{80\times128}$

$\text{Number of sectors}=16$

---

Solution

Tag bits $=9$

Index bits $=12$

Main memory size $=2^{9+12}=2^{21}$

$2^{21}=2048K$

Cache memory size $=2^{12}=4K$

Therefore, main memory size $=2048K$ and cache memory size $=4K$

---

Solution

In primal maximization problem,

If the constraint is equality type, then the corresponding dual variable is unrestricted.

Here, first constraint is equality type, so

$y_1$ is unrestricted.

The expected condition for second dual variable is

$y_2\ge 0$

---

Solution

Given expression:

$(\overline{P}\land Q)\lor(P\land \overline{Q})\lor(P\land Q)$

Take common $P$ from last two terms:

$=(\overline{P}\land Q)\lor P(\overline{Q}\lor Q)$

Since,

$\overline{Q}\lor Q=1$

So,

$=(\overline{P}\land Q)\lor P$

Using identity,

$P\lor(\overline{P}\land Q)=P\lor Q$

Therefore,

$(\overline{P}\land Q)\lor(P\land \overline{Q})\lor(P\land Q)=P\lor Q$

---

Solution

Given grammar:

$S\to AB\mid CA$

$B\to BC\mid AB$

$A\to a$

$C\to aB\mid b$

Here,

$A\to a$, so $A$ is generating.

$C\to b$, so $C$ is generating.

But $B\to BC\mid AB$ always contains $B$ again.

So, $B$ is non-generating.

Remove all productions containing $B$.

Remaining grammar is:

$S\to CA$

$A\to a$

$C\to b$

---

Solution

Given,

$S\to AbB$

$A\to aAb\mid \lambda$

So, $A$ generates equal number of $a$ and $b$.

$A\Rightarrow a^n b^n$

Also,

$B\to bB\mid \lambda$

So, $B$ generates any number of $b$.

$B\Rightarrow b^k$

Now,

$S\Rightarrow AbB$

$S\Rightarrow a^n b^n b b^k$

$S\Rightarrow a^n b^{n+k+1}$

So, number of $b$ is always greater than number of $a$.

Therefore,

$L=\{a^n b^m:n\ge 0,m>n\}$

---

Solution

$n\ge 4$

So, at least $4$ symbols $a$ are compulsory.

This is represented by:

$aaaaa^*$

Also,

$m\le 3$

So, number of $b$ can be $0,1,2,$ or $3$.

This is represented by:

$\lambda+b+bb+bbb$

Therefore, required regular expression is:

$aaaaa^*(\lambda+b+bb+bbb)$

---

Solution

$L=\{ab,aa,baa\}$

Check option (b):

$abaabaaabaa=ab\cdot aa\cdot baa\cdot ab\cdot aa$

So, option (b) is in $L^*$.

Check option (c):

$aaaabaaaa=aa\cdot aa\cdot baa\cdot aa$

So, option (c) is in $L^*$.

Check option (d):

$baaaaabaa=baa\cdot aa\cdot ab\cdot aa$

So, option (d) is in $L^*$.

But option (a) cannot be completely divided into strings $ab,aa,baa$.

Therefore, $baaaaabaaaaa$ is NOT in $L^*$.

---

Solution

For each input $a$, the NPDA pushes $2$ symbols $1$ into the stack.

For each input $b$, the NPDA pops $1$ symbol $1$ from the stack.

So, number of $b$ must be twice the number of $a$.

Therefore,

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

Also, $\lambda$ is accepted because:

$\delta(q_0,\lambda,z)=\{(q_f,z)\}$

---

Solution

Painter's algorithm is used for hidden surface removal.

It works by drawing far objects first and then nearer objects over them.

So, hidden surface removal with minimal $3D$ pipeline can be solved using Painter's algorithm.

---

Solution

Given,

$p=13,\ q=5,\ e=7$

$n=pq=13\times 5=65$

$\phi(n)=(p-1)(q-1)$

$\phi(n)=12\times 4=48$

Now,

$ed\equiv 1\pmod{\phi(n)}$

$7d\equiv 1\pmod{48}$

$7\times 7=49\equiv 1\pmod{48}$

So,

$d=7$

Cipher value of $6$ is:

$C=6^e\mod n$

$C=6^7\mod 65$

$C=46$

Therefore, $d=7$ and cipher value $=46$

---

Solution

The condition is:

$num\ !=\ 65$

It means $num$ is not equal to $65$.

Option (a):

$num>65\ ||\ num<65$

This is true when $num$ is not equal to $65$.

Option (b):

$!(num==65)$

This also means $num$ is not equal to $65$.

Option (c):

$num-65$

In C language, any non-zero value is treated as true.

So, this is also true when $num\neq 65$.

Option (d):

$!(num-65)$

This becomes true when $num-65=0$, that is $num=65$.

So, it is opposite of $num\ !=\ 65$.

---

Solution

Pointers are used to store addresses of variables.

They can be used to simulate call by reference.

They are also used to manipulate dynamic data structures like linked lists, trees, etc.

But pointers do not reference values directly. They access values indirectly through addresses.

---

Solution

In XML, namespace is used to provide globally unique names for elements and attributes.

It avoids name conflicts between different XML documents.

---

Solution

When a parent process is terminated, the operating system may terminate all its child processes.

This is called cascading termination.

---

Solution

In Linux, journalling is a file system feature.

It records file system changes as transactions before applying them permanently.

This helps in recovery after a crash or power failure.

---

Solution

The given equation represents a transformation using homogeneous coordinates.Here, the original point is written as:$\left[\matrix{x\cr y\cr z\cr 1}\right]$After transformation, it becomes:$\left[\matrix{\bar{x}\cr \bar{y}\cr \bar{z}\cr \bar{w}}\right]$The transformation is done by multiplying the point with a general $4\times4$ matrix.A general homogeneous coordinate transformation matrix can represent projective transformation.Such a projective transformation is called Homography.Now check the options:Scaling is used only to increase or decrease the size of an object.Shear is used only to slant the shape of an object.Steganography is not a transformation. It is a technique of hiding information.Homography is the correct term for this type of general homogeneous/projective transformation.

---

Solution

RAD stands for Rapid Application Development.

RAD is a software process model used for fast development of software.

In this model, development is done quickly with the help of prototypes, user feedback and reusable components.

Now check the options:

Option (a) Rapid Application Development is the full form of RAD.

Option (b) Relative Application Development is not correct.

Option (c) Rapid Application Design is not the standard full form.

Option (d) Recent Application Development is not correct.

---

Solution

SRS means Software Requirement Specification.

A requirement is called verifiable when it can be checked or tested by some practical process.

Here, the question says every requirement can be checked by a cost effective process.

This directly means that the requirement can be verified.

Now check the options:

Traceable means requirements can be traced from source to design or testing.

Modifiable means changes can be made easily in SRS.

Complete means all requirements are present.

Verifiable means each requirement can be checked or tested.

---

Solution

Fault based testing is a testing technique in which artificial faults are introduced into a program.

The purpose is to check whether the test cases are strong enough to detect those faults.

Mutation testing follows this idea.

In mutation testing, small changes are made in the program to create mutants.

If test cases detect these mutants, then the test cases are considered effective.

Now check the options:

Unit testing checks individual modules.

Beta testing is done by real users before final release.

Stress testing checks system behavior under heavy load.

Mutation testing is a fault based testing technique.

---

Solution

Alpha testing and Beta testing are performed to check whether the software is acceptable to users.

Alpha testing is usually done at the developer side by internal users or testers.

Beta testing is done by real users in the real environment before final release.

Both are used to validate the software from the user's point of view.

Therefore, Alpha and Beta testing are forms of Acceptance Testing.

Now check the options:

White-Box Testing checks internal code structure.

Black-Box Testing checks functionality without seeing internal code.

System Testing checks the complete system.

Acceptance Testing checks whether the software is acceptable for final use.

---

Solution

Requirement Engineering is the complete process of handling software requirements.

It includes:

Gathering requirements from the client

Analyzing requirements

Documenting requirements

Validating requirements

The question clearly mentions gathering, analyzing and documenting requirements.

So, this is not only requirement elicitation.

Requirement elicitation is only the activity of collecting requirements.

The complete process is called Requirement Engineering Process.

---

Solution

Software metrics are used to measure different aspects of software development.

Product metrics are related to the software product itself.

They measure properties such as:

Size of the software

Complexity of the software

Quality of the software

Performance of the software

Here, size and complexity describe the software product.

So, they are part of Product Metrics.

Now check the options:

People Metrics are related to team members.

Project Metrics are related to project cost, schedule and effort.

Process Metrics are related to software development process.

Product Metrics are related to software size, complexity and quality.

---

Solution

We need sailors whose age is over $20$ and who have not reserved a red boat.

First find sailors with age over $20$.

From Sailors table:

$\pi_{sid}(\sigma_{age>20}(Sailors))=\{22,29,31,32,58,64,74,85,95\}$

Now find red boats.

From Boats table, red boats are:

$Bid=102$ and $Bid=104$

Now find sailors who reserved red boats.

From Reserves table:

$Sid=22$ reserved $Bid=102$ and $Bid=104$

$Sid=31$ reserved $Bid=102$ and $Bid=104$

$Sid=64$ reserved $Bid=102$

So,

$\pi_{sid}((\sigma_{color='red'}(Boats))\bowtie Reserves\bowtie Sailors)=\{22,31,64\}$

Now subtract sailors who reserved red boats from sailors whose age is over $20$.

$\{22,29,31,32,58,64,74,85,95\}-\{22,31,64\}$

$=\{29,32,58,74,85,95\}$

So, the correct relational algebra expression must be:

$\pi_{sid}(\sigma_{age>20}(Sailors))-\pi_{sid}((\sigma_{color='red'}(Boats))\bowtie Reserves\bowtie Sailors)$

---

Solution

We need the names of sailors who have reserved a red boat.

First, we must identify red boats from the Boats table.

Red boats are obtained by:

$\sigma_{color='red'}(Boats)$

After this, we need to join these red boats with Reserves table, because Reserves table tells which sailor reserved which boat.

Then we join with Sailors table to get sailor names.

So, Q1 is correct:

$\pi_{sname}((\sigma_{color='red'}(Boats))\bowtie Reserves\bowtie Sailors)$

Now check Q2.

Q2 first finds red boat IDs:

$\pi_{bid}(\sigma_{color='red'}(Boats))$

Then it joins with Reserves to find sailors who reserved those red boats.

Then it projects $sid$ and joins with Sailors to get sailor names.

So, Q2 is also correct.

Now check Q3.

Q3 applies condition $color='red'$ on Reserves.

But Reserves table does not contain the attribute $color$.

The $color$ attribute belongs to Boats table.

So, Q3 is incorrect.

Therefore, both Q1 and Q2 compute the required result.

---

Solution

We need the names of sailors who have reserved boat $103$.

The information about reservation is available in the Reserves table.

So, to find sailors who reserved boat $103$, first select those tuples from Reserves where $bid=103$.

$\sigma_{bid=103}(Reserves)$

Then join this result with Sailors table using $sid$.

Finally, project the sailor names using $\pi_{sname}$.

So, Q3 is correct:

$\pi_{sname}((\sigma_{bid=103}(Reserves))\bowtie Sailors)$

Now check Q2.

In Q2, Reserves is first joined with Sailors.

Then condition $bid=103$ is applied.

After that, sailor names are projected.

This also gives the same correct result.

So, Q2 is also correct.

Now check Q1.

Q1 selects $bid=103$ from Boats and joins it directly with Sailors.

But Boats table and Sailors table do not directly tell which sailor reserved which boat.

The Reserves table is required for this relationship.

So, Q1 is incorrect.

Therefore, both Q2 and Q3 compute the required result.

---

Solution

We need the names of sailors who have reserved all boats.

In relational algebra, when we need to find entities related to all values of another relation, we use division operation.

Here,

$Reserves(Sid,Bid,day)$ tells which sailor reserved which boat.

$Boats(Bid,Bname,Color)$ tells all available boats.

First, take only required columns from Reserves:

$\pi_{sid,bid}(Reserves)$

This gives pairs of sailors and boats reserved by them.

Now take all boat IDs from Boats:

$\pi_{bid}(Boats)$

To find sailors who reserved every boat, apply division:

$(\pi_{sid,bid}(Reserves))/(\pi_{bid}(Boats))$

This gives only those $sid$ values which are associated with all $bid$ values.

Now rename this result as $Tempsids$:

$\rho(Tempsids,((\pi_{sid,bid}Reserves)/(\pi_{bid}Boats)))$

Finally, join $Tempsids$ with Sailors table to get sailor names:

$\pi_{sname}((Tempsids)\bowtie Sailors)$

So, the correct query must use:

$\pi_{sid,bid}Reserves$

and

$\pi_{bid}Boats$

with division operation.

Option (b) correctly represents this logic.

---

Solution

We need the names of sailors who have reserved both types of boats:

Red boat

Green boat

First, find sailors who reserved a red boat.

Red boats are selected by:

$\sigma_{color='red'}(Boats)$

Now join this with Reserves table, because Reserves table contains the information about which sailor reserved which boat.

$\pi_{sid}((\sigma_{color='red'}(Boats))\bowtie Reserves)$

This gives the $sid$ of sailors who reserved a red boat.

Rename this result as:

$Tempred$

So,

$Tempred=\pi_{sid}((\sigma_{color='red'}(Boats))\bowtie Reserves)$

Now, find sailors who reserved a green boat.

Green boats are selected by:

$\sigma_{color='green'}(Boats)$

Join with Reserves table and project $sid$:

$\pi_{sid}((\sigma_{color='green'}(Boats))\bowtie Reserves)$

Rename this result as:

$Tempgreen$

So,

$Tempgreen=\pi_{sid}((\sigma_{color='green'}(Boats))\bowtie Reserves)$

Now, sailors who reserved both red and green boats will be obtained by intersection:

$Tempred\cap Tempgreen$

This gives common $sid$ values.

Finally, join this result with Sailors table to get sailor names:

$\pi_{sname}((Tempred\cap Tempgreen)\bowtie Sailors)$

Therefore, option (a) correctly finds sailors who reserved both a red and a green boat.

---

Solution

Given,

Frame size $=64$ bytes

Data rate $=1.536\ mbps$

Distance $=3000\ km$

Propagation delay per km $=6\mu sec/km$

First, convert frame size into bits.

$1$ byte $=8$ bits

So,

$64$ bytes $=64\times 8=512$ bits

Now, transmission delay is given by:

$T_t=\frac{\text{Frame size in bits}}{\text{Data rate}}$

$T_t=\frac{512}{1.536\times 10^6}$ seconds

$T_t=333.33\times 10^{-6}$ seconds

$T_t=333.33\mu sec$

Now, propagation delay is given by:

$T_p=\text{Distance}\times \text{Propagation delay per km}$

$T_p=3000\times 6$

$T_p=18000\mu sec$

Therefore,

$T_t=333.33\mu sec$

$T_p=18000\mu sec$

---

Solution

$T_t=333.33\mu sec$

$T_p=18000\mu sec$

Now,

$a=\frac{T_p}{T_t}$

$a=\frac{18000}{333.33}$

$a=54$

For sliding window protocol, sender window size required for maximum efficiency is:

$W=1+2a$

$W=1+2(54)$

$W=109$

So, sequence number field must be able to represent at least $109$ different sequence numbers.

Using $k$ bits, number of sequence numbers is:

$2^k$

Now check:

$2^6=64$

$64<109$, so $6$ bits are not sufficient.

$2^7=128$

$128\ge 109$, so $7$ bits are sufficient.

---

Solution

$T_t=333.33\mu sec$

$T_p=18000\mu sec$

Now,

$a=\frac{T_p}{T_t}$

$a=\frac{18000}{333.33}$

$a=54$

For maximum efficiency in sliding window protocol, sender window size should be:

$W=1+2a$

$W=1+2(54)$

$W=109$

So, sender window size required for maximum efficiency is $109$.

---

Solution

Given,

Sequence number field $=6$ bits

So, total sequence numbers are:

$2^6=64$

In sliding window protocol, maximum usable sender window size is:

$W=2^6-1$

$W=64-1=63$

From previous calculation,

$a=54$

Efficiency of sliding window protocol is:

$\eta=\frac{W}{1+2a}$

$\eta=\frac{63}{1+2(54)}$

$\eta=\frac{63}{109}$

$\eta=0.578$

---

Solution

Efficiency of the system is:

$\eta=0.578$

Given data rate is:

$1.536\ Mbps$

Maximum achievable throughput is:

$Throughput=\eta\times \text{Data rate}$

$Throughput=0.578\times1.536$

$Throughput=0.887\ Mbps$

Therefore, the maximum achievable throughput is $0.887\ Mbps$.

---

Solution

Size oriented metrics are derived by considering the size of the software product.

Usually, size is measured in terms of lines of code.

These metrics normalize quality and productivity measures using software size.

For example:

Productivity can be measured as output per line of code.

Quality can be measured as defects per line of code.

Since the question says that quality and/or productivity measures are normalized by considering the size of the software, it refers to Size Oriented Metrics.

---

Solution

In Iterative Enhancement Model, the complete system is not developed at once.

The requirements are divided into parts or categories.

Then each category of requirements is implemented step by step in different iterations.

After every iteration, the software is improved by adding new features or enhancing existing features.

Waterfall model follows a fixed sequence of phases.

Prototyping model focuses on making a prototype first.

Evolutionary model evolves the software with user feedback.

But implementing requirements category-wise is mainly related to Iterative Enhancement Model.

---

Solution

Software product measures are of two types:

Direct measures

Indirect measures

Direct measures can be measured directly, such as size, cost and effort.

Indirect measures cannot be measured directly.

They are evaluated using other factors.

Quality, complexity and reliability are indirect measures of a software product.

So, all the given options are indirect measures of product.

---

Solution

Cohesion means how strongly the elements of a module are related to each other.

Communicational cohesion occurs when different parts of a module operate on the same input data or produce the same output data.

Here, modules X and Y operate on the same input and output.

So, this is an example of Communicational cohesion.

Logical cohesion groups similar logical activities.

Sequential cohesion occurs when output of one part becomes input of another part.

Procedural cohesion occurs when elements follow a particular sequence.

---

Solution

---

Solution

Cipher Feedback Mode is a block cipher mode that converts a block cipher into a stream cipher.

It is called self synchronizing because if some bits are lost or damaged, the system can automatically resynchronize after some blocks.

Output Feedback Mode is also used like a stream cipher, but it is a synchronous stream cipher, not self synchronizing.

Electronic Codebook Mode encrypts each block independently.

Cipher Block Chaining Mode uses the previous ciphertext block for chaining.

Therefore, the block cipher mode used as a self synchronizing stream cipher is Cipher Feedback Mode.

---

Solution

Given minterms are: $3,4,5,6,7,11,15$ Using K-Map grouping: Group 1: $4,5,6,7 \Rightarrow A'B$ Group 2: $3,7,11,15 \Rightarrow CD$ Therefore, $F(A,B,C,D)=A'B+CD$

---

Solution

Transport layer protocols are used for end-to-end communication between applications.

TCP is a connection-oriented transport layer protocol.

It establishes a connection before data transfer.

UDP is a connectionless transport layer protocol.

It does not establish a connection before sending data.

UDP sends data in the form of datagrams and is part of the Internet protocol family.

Routing Protocol works at the network layer.

Datagram Control Protocol is not the standard connectionless transport protocol in the TCP/IP family.

---

Solution

We know, $P \to Q \equiv \sim P \vee Q$ Also, contrapositive of $P \to Q$ is $\sim Q \to \sim P$ So, $P \to Q \equiv \sim Q \to \sim P$ Also, $P \to Q \equiv \sim(P \wedge \sim Q)$ Now, $\sim Q \to P \equiv Q \vee P$ This is not equivalent to $P \to Q$.

---

Solution

Given,

Channel bandwidth $=64$ kbps

Frame size $=512$ bytes

Frame size in bits:

$512\times 8=4096$ bits

Transmission time:

$T_t=\frac{4096}{64000}$

$T_t=0.064$ sec

$T_t=64$ ms

For a satellite channel, one-way propagation delay is generally taken as approximately $270$ ms.

So,

$a=\frac{T_p}{T_t}$

$a=\frac{270}{64}$

$a=4.21875$

For sliding window protocol, maximum efficiency is achieved when:

$W\ge 1+2a$

$1+2a=1+2(4.21875)$

$1+2a=9.4375$

Given window size is:

$W=15$

Since,

$15>9.4375$

So, the channel can be fully utilized.

Therefore, maximum throughput is equal to the channel bandwidth.

Maximum throughput $=64$ kbps

---

Solution

Each of the $7$ people can leave at any one of the $3$ stops. Total ways without restriction: $3^7=2187$ But each stop must have at least one person leaving. Using inclusion-exclusion: Required ways $=3^7-\binom{3}{1}2^7+\binom{3}{2}1^7$ $=2187-3(128)+3(1)$ $=2187-384+3$ $=1806$

---

Solution

Given classless address:

$167.199.170.82/27$

Here, prefix length is:

$27$

In IPv4, total bits are:

$32$

So, host bits are:

$32-27=5$

Number of addresses in the network is:

$2^{host\ bits}$

$=2^5$

$=32$

So, total number of addresses in this network is $32$.

Note: Usable host addresses would be $30$, but the question asks total number of addresses in the network.

---

Solution

In $(x+y+z)^7$, the general coefficient of $x^ay^bz^c$ is $\frac{7!}{a!b!c!}$ Here, $a=2,\ b=3,\ c=2$ So, coefficient is $\frac{7!}{2!3!2!}$ $=C(7,2)\times C(5,3)$

---

Solution

The Network layer is responsible for packet formation, routing and delivery of packets from source to destination.

At the source side, it divides data into packets.

At the destination side, it re-assembles packets to form the original message.

Transport layer mainly provides end-to-end communication and segmentation.

Data link layer works with frames.

Physical layer works with bits.

Since the question specifically says packets, the correct layer is Network layer.

---

Solution

There are $7$ possible grades. To avoid getting $6$ students in the same grade, maximum $5$ students can receive each grade. So, maximum students without guarantee: $7\times 5=35$ Now, one more student will surely make at least $6$ students in one grade. Required number of students: $35+1=36$

---

Solution

Given,

Number of pipeline stages:

$k=4$

Number of data items:

$n=1000$

Stage delays are:

$150$ ns, $120$ ns, $160$ ns and $140$ ns

Register delay:

$5$ ns

In a pipeline, clock cycle time is decided by the slowest stage.

Slowest stage delay:

$160$ ns

So, pipeline clock cycle time is:

$160+5=165$ ns

Total time required for $n$ tasks in a $k$-stage pipeline is:

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

$=(4+1000-1)\times 165$

$=1003\times 165$

$=165495$ ns

$=165.495\ \mu sec$

Numerically, this is approximately $165.5$.

So, according to the given options, the answer is $165.5$.

---

Solution

---

Solution

Given MAC address:

$4A:30:10:21:10:1A$

To identify whether a MAC address is unicast or multicast, we check the least significant bit of the first octet.

First octet is:

$4A$

Convert $4A$ into binary:

$4A=(01001010)_2$

The least significant bit is:

$0$

If the least significant bit of the first octet is $0$, it is a unicast address.

If it is $1$, it is a multicast address.

Broadcast address is:

$FF:FF:FF:FF:FF:FF$

The given address is not broadcast.

Therefore, the given address is a unicast address.

---

Solution

---

Solution

If $f(n)=O(g(n))$ and $g(n)=O(h(n))$, then by transitivity:

$f(n)=O(h(n))$

But option says:

$f(n)=\omega(h(n))$

So, option (a) is incorrect.

Check option (b):

If $f(n)=\Omega(g(n))$ and $g(n)=\Omega(h(n))$, then:

$f(n)=\Omega(h(n))$

But option says:

$f(n)=O(h(n))$

So, option (b) is incorrect.

Check option (c):

If $f(n)=o(g(n))$, then $f(n)$ grows strictly slower than $g(n)$.

If $g(n)=o(h(n))$, then $g(n)$ grows strictly slower than $h(n)$.

Therefore, $f(n)$ also grows strictly slower than $h(n)$.

So,

$f(n)=o(h(n))$

Thus, option (c) is correct.

Check option (d):

If $f(n)=\omega(g(n))$ and $g(n)=\omega(h(n))$, then:

$f(n)=\omega(h(n))$

Since $\omega(h(n))$ is stronger than $\Omega(h(n))$, option (d) is also mathematically correct.

Therefore, mathematically both option (c) and option (d) are correct.

If the exam expects only one answer, then the question has ambiguity.

---

Solution

---

Solution

Given recurrence is:

$T(n)=3T\left(\frac{n}{4}\right)+n\log n$

Compare with Master Theorem:

$T(n)=aT\left(\frac{n}{b}\right)+f(n)$

Here,

$a=3,\ b=4,\ f(n)=n\log n$

Now,

$n^{\log_b a}=n^{\log_4 3}$

Since,

$\log_4 3<1$

So,

$n^{\log_4 3}<n$

But,

$f(n)=n\log n$

Clearly,

$n\log n$ grows faster than $n^{\log_4 3}$.

So, by Master Theorem Case 3,

$T(n)=\theta(n\log n)$

---

Solution

---

Solution

In a heap, height of a node means the number of edges on the longest downward path from that node to a leaf.

Leaves have height $0$.

In an $n$-element heap, the number of nodes at height $h$ decreases as $h$ increases.

Standard result:

Number of nodes of height $h$ in an $n$-element heap is at most

$\left\lceil \frac{n}{2^{h+1}}\right\rceil$

Ignoring the ceiling value, it is written as:

$\frac{n}{2^{h+1}}$

So, the required expression is:

$\frac{n}{2^{h+1}}$

---

Solution

---

Solution

For a B-tree with minimum degree $t$, every internal node except root has at least $t$ children.

Also, every node except root has at least $t-1$ keys.

For a B-tree of height $h$, the minimum number of keys is:

$n\ge 2t^h-1$

Now solve this inequality for $h$.

$n+1\ge 2t^h$

$\frac{n+1}{2}\ge t^h$

Taking logarithm base $t$ on both sides:

$\log_t\frac{n+1}{2}\ge h$

So,

$h\le \log_t\frac{n+1}{2}$

---

Solution

---

Solution

Quick sort uses the divide and conquer technique.

In Quick sort, first we choose a pivot element.

Then the array is divided into two parts:

Elements smaller than pivot

Elements greater than pivot

After partitioning, Quick sort is applied recursively on both parts.

So, the problem is divided into smaller subproblems and then solved recursively.

This is exactly the divide and conquer approach.

---

Solution

---

Solution

---

Solution

---

Solution

Given,

Preorder traversal:

$ABCEIFJDGHKL$

Inorder traversal:

$EICFJBGDKHLA$

In preorder traversal, the first element is always the root.

So, root is:

$A$

In inorder traversal, $A$ is at the end.

So, all remaining nodes are in the left subtree of $A$.

Now, after $A$, the next root in preorder is:

$B$

In inorder traversal:

$EICFJBGDKHL$

Here, nodes before $B$ are in left subtree of $B$:

$EICFJ$

Nodes after $B$ are in right subtree of $B$:

$GDKHL$

Now solve left subtree of $B$.

Preorder part is:

$CEIFJ$

Root is $C$.

Inorder part is:

$EICFJ$

Left of $C$ is $EI$ and right of $C$ is $FJ$.

For $EI$, root is $E$, so postorder is:

$IE$

For $FJ$, root is $F$, so postorder is:

$JF$

So, postorder of subtree rooted at $C$ is:

$IEJFC$

Now solve right subtree of $B$.

Preorder part is:

$DGHKL$

Root is $D$.

Inorder part is:

$GDKHL$

Left of $D$ is $G$ and right of $D$ is $KHL$.

So, left postorder is:

$G$

For right part $KHL$, root is $H$.

Left of $H$ is $K$ and right of $H$ is $L$.

So, postorder of subtree rooted at $H$ is:

$KLH$

Thus, postorder of subtree rooted at $D$ is:

$GKLHD$

Now, postorder of subtree rooted at $B$ is:

$IEJFCGKLHDB$

Finally, root $A$ comes at the end.

So, final postorder traversal is:

$IEJFCGKLHDBA$

---

Solution

---

Solution

Insert elements one by one in AVL tree.

Insert $35$:

Tree is balanced. No rotation.

Insert $50$:

$50$ becomes right child of $35$.

Tree is balanced. No rotation.

Insert $40$:

$40$ goes to left of $50$.

This creates Right-Left imbalance at $35$.

For Right-Left case, we do:

Right rotation at $50$

Left rotation at $35$

So far:

Left rotations $=1$

Right rotations $=1$

Insert $25$:

$25$ goes to left side.

Tree remains balanced. No rotation.

Insert $30$:

$30$ goes to right of $25$.

This creates Left-Right imbalance at $35$.

For Left-Right case, we do:

Left rotation at $25$

Right rotation at $35$

Now total:

Left rotations $=2$

Right rotations $=2$

Insert $60$:

$60$ goes to right side.

Tree remains balanced. No rotation.

Insert $78$:

$78$ goes to right of $60$.

This creates Right-Right imbalance at $50$.

For Right-Right case, we do:

Left rotation at $50$

Now total:

Left rotations $=3$

Right rotations $=2$

Insert $20$:

$20$ goes to left side.

Tree remains balanced. No rotation.

Insert $28$:

$28$ goes to right of $25$.

Tree still remains balanced. No rotation.

Therefore, total rotations are:

$3$ left rotations and $2$ right rotations.

---

Solution

---

Solution

---

Solution

---

Solution

Given functional dependencies are:

$A\to B$

$ABCD\to E$

$EF\to G$

$EF\to H$

$ACDF\to EG$

First, split the right hand side having multiple attributes.

$ACDF\to EG$ becomes:

$ACDF\to E$

$ACDF\to G$

So, the set becomes:

$A\to B$

$ABCD\to E$

$EF\to G$

$EF\to H$

$ACDF\to E$

$ACDF\to G$

Now check $ABCD\to E$.

Since,

$A\to B$

So, from $ACD$, we can get $B$ also.

Therefore,

$ACD^+=ACDB$

Now using $ABCD\to E$, we get:

$ACD\to E$

So, $B$ is extraneous in $ABCD\to E$.

Hence,

$ABCD\to E$ reduces to $ACD\to E$

Now check $ACDF\to E$.

Since we already have:

$ACD\to E$

So, $ACDF\to E$ is unnecessary.

Therefore, remove $ACDF\to E$.

Now check $ACDF\to G$.

From $ACDF$, using $ACD\to E$, we get $E$.

Now we have $E$ and $F$.

Using,

$EF\to G$

we get $G$.

So, $ACDF\to G$ is also unnecessary.

Therefore, remove $ACDF\to G$.

The remaining minimal cover is:

$A\to B$

$ACD\to E$

$EF\to G$

$EF\to H$

---

Solution

---

Solution

A trigger is a special type of database statement or procedure.

It is executed automatically when a specific event occurs in the database.

For example, a trigger may execute automatically when:

A record is inserted

A record is updated

A record is deleted

So, a trigger is not manually executed by the user every time.

It is automatically executed by the DBMS as a side effect of modification to the database.

Now check the options:

Option (a) is incorrect because trigger is not used to start DBMS.

Option (b) is incorrect because trigger is not mainly used for debugging.

Option (c) is incorrect because user validity checking is related to authentication or authorization.

Option (d) is correct because trigger executes automatically after database modification.

---

Solution

---

Solution

Given page reference string is:

$4,3,2,1,4,3,5,4,3,2,1,5$

Frame size $=3$

Using LRU page replacement, the least recently used page is replaced when a page fault occurs.

Now process each page:

$4$ gives page fault.

Frames: $4$

Total faults $=1$

$3$ gives page fault.

Frames: $4,3$

Total faults $=2$

$2$ gives page fault.

Frames: $4,3,2$

Total faults $=3$

$1$ gives page fault. Replace least recently used page $4$.

Frames: $1,3,2$

Total faults $=4$

$4$ gives page fault. Replace least recently used page $3$.

Frames: $1,4,2$

Total faults $=5$

$3$ gives page fault. Replace least recently used page $2$.

Frames: $1,4,3$

Total faults $=6$

$5$ gives page fault. Replace least recently used page $1$.

Frames: $5,4,3$

Total faults $=7$

$4$ is already present.

Frames: $5,4,3$

Total faults $=7$

$3$ is already present.

Frames: $5,4,3$

Total faults $=7$

$2$ gives page fault. Replace least recently used page $5$.

Frames: $2,4,3$

Total faults $=8$

$1$ gives page fault. Replace least recently used page $4$.

Frames: $2,1,3$

Total faults $=9$

$5$ gives page fault. Replace least recently used page $3$.

Frames: $2,1,5$

Total faults $=10$

Therefore, number of page faults $=10$.

---

Solution

---

Solution

Given,

Tape transport speed $=200$ inches/second

Recording density $=1600$ bytes/inch

Total data $=600000$ bytes

First, find the data transfer rate.

Data transfer rate $=$ Transport speed $\times$ Recording density

Data transfer rate $=200\times1600$

Data transfer rate $=320000$ bytes/second

Now, time required to write data is:

$Time=\frac{\text{Total data}}{\text{Data transfer rate}}$

$Time=\frac{600000}{320000}$

$Time=1.875$ seconds

The records are grouped in $100$ characters with blocking factor $10$, so one block has:

$100\times10=1000$ characters

This grouping affects blocking arrangement, but the total amount of data to be written remains $600000$ bytes.

Therefore, required time is:

$1.875$ sec

---

Solution

---

Solution

---

Solution

---

Solution

For recursively enumerable sets, these properties are related to languages accepted by Turing machines.

Now check each property one by one.

(A) Finiteness:

To decide whether a recursively enumerable language is finite or infinite, we need to know all strings accepted by the Turing machine.

But a Turing machine may not halt on some inputs.

So, finiteness of recursively enumerable sets is not decidable.

(B) Context Freedom:

To decide whether a recursively enumerable language is context-free or not is also not decidable.

This is a non-trivial property of the language accepted by a Turing machine.

By Rice's theorem, every non-trivial property of recursively enumerable languages is undecidable.

So, context freedom is not decidable.

(C) Emptiness:

Emptiness means checking whether the language accepted by a Turing machine is empty or not.

That is, we need to decide whether the Turing machine accepts at least one string.

This is also undecidable for recursively enumerable languages.

Therefore, all three properties are not decidable.

---

Solution

---

Solution

Activation record is related to a subroutine call.

When a function or subroutine is called, an activation record is created to store information like parameters, return address and local variables.

So,

$(A)-(III)$

Location counter is used in assembler.

Assembler uses location counter to keep track of the address of the instruction or data item being assembled.

So,

$(B)-(IV)$

Reference count is related to garbage collection.

In reference counting, the system counts how many references point to an object. If the count becomes zero, that object can be removed.

So,

$(C)-(II)$

Address relocation is done by linker loader.

The linker loader adjusts addresses when a program is loaded into memory.

So,

$(D)-(I)$

Final matching is:

$(A)-(III), (B)-(IV), (C)-(II), (D)-(I)$

---

Solution

---

Solution

Fourth Generation Technique $(4GT)$ is a software development approach that uses high-level tools and languages.

It helps in faster software development because less manual coding is required.

Now check each statement:

(A) It controls efforts.

This is correct because $4GT$ reduces manual programming effort.

(B) It controls resources.

This is also correct because fewer resources may be needed due to automation and high-level tools.

(C) It controls cost of development.

This is also correct because reduced effort and better resource usage reduce development cost.

Therefore, all statements are correct.

---

Solution

---

Solution

Given grammar is:

$S\to SbS\mid a$

This grammar is ambiguous.

The string is:

$abababa$

It contains $4$ symbols $a$ and $3$ symbols $b$.

This is like combining four $a$'s using three $b$ operators.

Because the grammar does not define a fixed grouping rule, the string can be derived in more than one way.

For example, one possible grouping is:

$(((a)b(a))b(a))b(a)$

Another possible grouping is:

$(a)b((a)b((a)b(a)))$

So, the string has more than one parse tree.

For every different parse tree, there is a corresponding different left most derivation.

So, it has more than one left most derivation.

Similarly, for every different parse tree, there is a corresponding different right most derivation.

So, it has more than one right most derivation.

Therefore, all three statements are true in the sense of ambiguity.

---

Solution

Cyclomatic complexity measures the number of linearly independent paths in a program.

---

Solution

$\alpha-\beta$ pruning is an optimization technique used with the minimax algorithm in game playing search trees.

It can be applied at any depth of the game tree.

It is not restricted to only one particular level.

Now check each statement:

(A) Root $(0)$ level

At the root level, $\alpha$ and $\beta$ values are initialized and the search starts from this level.

So, $\alpha-\beta$ pruning can be applied from root level.

Therefore, statement (A) is correct.

(B) $6$ level

If the game tree is searched up to depth $6$, then $\alpha-\beta$ pruning can be applied up to level $6$.

Therefore, statement (B) is correct.

(C) $8$ level

Similarly, if the game tree is searched up to depth $8$, then $\alpha-\beta$ pruning can also be applied up to level $8$.

Therefore, statement (C) is correct.

(D) Depends on utility value in a breadth first order

This is incorrect because $\alpha-\beta$ pruning is normally applied using depth first search, not breadth first search.

It depends on $\alpha$ and $\beta$ values during depth first minimax search.

Therefore, only (A), (B) and (C) are correct.

---

Solution

---

Solution

Check statement (A):

$(\alpha\land(\beta\lor\gamma))\equiv((\alpha\land\beta)\lor(\alpha\land\gamma))$

This is distributive law of logic.

So, statement (A) is true.

Check statement (B):

$(\alpha\lor\beta)\equiv\neg\alpha\lor\beta$

This is not always true.

For example, let $\alpha=True$ and $\beta=False$.

Then,

$\alpha\lor\beta=True\lor False=True$

But,

$\neg\alpha\lor\beta=False\lor False=False$

Both values are different.

So, statement (B) is false.

Check statement (C):

$(\alpha\Rightarrow\beta)\equiv(\neg\beta\Rightarrow\neg\alpha)$

This is contrapositive law.

Also,

$\alpha\Rightarrow\beta\equiv\neg\alpha\lor\beta$

And,

$\neg\beta\Rightarrow\neg\alpha\equiv\beta\lor\neg\alpha$

Since,

$\neg\alpha\lor\beta\equiv\beta\lor\neg\alpha$

So, statement (C) is true.

Check statement (D):

$(\neg(\alpha\lor\beta))\equiv(\neg\alpha\Rightarrow\neg\beta)$

Using De Morgan's law,

$\neg(\alpha\lor\beta)\equiv\neg\alpha\land\neg\beta$

Now,

$\neg\alpha\Rightarrow\neg\beta\equiv\alpha\lor\neg\beta$

These two are not equivalent.

So, statement (D) is false.

Therefore, only (A) and (C) are correct.

---

Solution

---

Solution

Given,

$(\{a,b\},*)$ is a semigroup.

So, the operation $*$ is associative.

That means,

$(x*y)*z=x*(y*z)$

Also given,

$a*a=b$

Now check statement (A):

Using associativity,

$(a*a)*a=a*(a*a)$

Since $a*a=b$, we get:

$b*a=a*b$

So,

$a*b=b*a$

Therefore, statement (A) is true.

Now check statement (B):

We need to prove $b*b=b$.

Since $b=a*a$, we can write:

$b*b=(a*a)*b$

Using associativity,

$(a*a)*b=a*(a*b)$

Now, $a*b$ must be either $a$ or $b$ because the set is $\{a,b\}$.

Case 1:

If $a*b=a$, then

$a*(a*b)=a*a=b$

Case 2:

If $a*b=b$, then

$a*(a*b)=a*b=b$

In both cases,

$b*b=b$

Therefore, statement (B) is also true.

Hence, both (A) and (B) are true.