---

Solution

Nyquist Sampling Theorem states:

Sampling frequency must be at least twice the maximum frequency present in the signal.

$ f_s \ge 2f_{max} $

---

Solution

---

Solution

Period $T=100\ ms=0.1\ sec$

Frequency:

$f=\frac{1}{T}=\frac{1}{0.1}=10\ Hz$

Now convert into kHz:

$10\ Hz=\frac{10}{1000}\ kHz=0.01\ kHz=10^{-2}\ kHz$

---

Solution

Dual is obtained by interchanging:

$+$ ↔ $\cdot$

$0$ ↔ $1$

Applying dual rule:

A → III

B → IV

C → II

D → I

---

Solution

---

Solution

Abstraction means hiding or removing unnecessary details and keeping only important information.

So, removing details from a state representation is called abstraction.

---

Solution

Tokens are the smallest meaningful units of a program.

Break the statement:

for | i | in | range | ( | begin | : | end | : | step | ) | :

Tokens:

for

i

in

range

(

begin

:

end

:

step

)

:

Total tokens = 12

---

Solution

A compiler that runs on one machine but generates code for another machine is called a cross compiler.

---

Solution

AI problem solving commonly uses heuristic search.

In AI, solution steps may not always be explicit, and knowledge may be imprecise.

Repetition mechanism is mainly a feature of conventional algorithmic programming, not a special feature of AI problem solving.

---

Solution

From the diagrams:

• Both machines are deterministic (each state has exactly one transition for each input symbol).

• The first machine has states A and B with transitions on a and b.

• The second machine has states A, B, C, but the accepted language behavior matches the first machine.

Both machines accept the same language, even though the number of states differs.

Thus they are equivalent machines.

---

Solution

---

Solution

---

Solution

“Some” means there exists at least one person.

“my friends” means $f(x)$.

“not perfect” means $\neg p(x)$.

So, the statement becomes:

$\exists x(f(x)\land \neg p(x))$

---

Solution

Complement of fuzzy set:

$\mu_{A'}(x) = 1 - \mu_A(x)$

Compute:

$x_1$: $1 - 0.3 = 0.7$

$x_2$: $1 - 0.7 = 0.3$

$x_3$: $1 - 0.4 = 0.6$

Thus,

$A' = {(x_1,0.7),(x_2,0.3),(x_3,0.6)}$

---

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

In CNF, formula is written as conjunction of clauses.

Each clause is a disjunction of literals.

Example:

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

Here, $(p\vee \neg q)$ and $(r\vee s)$ are clauses.

So, clauses in CNF are disjunction of literals.

---

Solution

Interrupt Service Routine (ISR) steps:

Save processor registers → C

Check which device raised interrupt → D

Service the device → B

Restore processor registers → E

Re-enable interrupt facility → A

Correct sequence:

C, D, B, E, A

---

Solution

---

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

For reflexive relation, every element must have pair $(x,x)$.

But $(c,c)$ and $(d,d)$ are missing.

So, relation is not reflexive.

For antisymmetric relation, if $(x,y)$ and $(y,x)$ both exist, then $x=y$.

Here, no reverse pair exists for $(c,d),(c,g),(d,g)$.

So, relation is antisymmetric.

For symmetric relation, if $(x,y)$ exists, then $(y,x)$ must also exist.

But $(c,d)$ exists and $(d,c)$ does not exist.

So, relation is not symmetric.

Therefore, relation satisfies B and not A.

---

Solution

Number of spanning trees:

For complete graph:

$\tau(K_n)=n^{n-2}$

A: $K_3 = 3^{1} = 3$

B: $K_4 = 4^{2} = 16$

For complete bipartite graph:

$\tau(K_{m,n}) = m^{n-1} n^{m-1}$

C: $K_{2,2} = 2^{1} \times 2^{1} = 4$

For cycle graph:

$\tau(C_n)=n$

D: $C_5 = 5$

Thus:

A = 3

C = 4

D = 5

B = 16

Increasing order:

A, C, D, B

---

Solution

---

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

From $\forall x(P(x)\vee Q(x))$, we can get:

$P(c)\vee Q(c)$

So, step (B) is correct.

But from $P(c)\vee Q(c)$, we cannot conclude $P(c)$ alone.

Also, we cannot conclude $Q(c)$ alone.

So, steps (C) and (E) are not correct inferences.

Step (G) would be correct only if (D) and (F) were validly obtained.

Hence, the main error is in steps (C) and (E).

---

Solution

Standard I/O techniques are:

• Programmed I/O

• Interrupt-driven I/O

• Direct Memory Access (DMA)

Rotational I/O and Channelized I/O are not standard CPU I/O techniques.

Thus:

A, B, D are correct.

---

Solution

Critical region is related to mutual exclusion.

Wait signal is related to Hoare's monitor.

Working set is based on principle of locality.

Deadlock is related to circular wait.

So,

A – II, B – I, C – III, D – IV

---

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

Symbol table stores information about identifiers like name, type, scope, address and other attributes.

It helps in storage allocation.

It helps in checking type compatibility.

It also helps in avoiding or suppressing duplicate error messages for the same identifier.

So, all A, B and C are correct.

---

Solution

Common properties of social networks:

• Scale-free degree distribution → True

• Small world property → True

• Short average path length → True

However, most social networks are not necessarily directed; many are modeled as undirected networks.

Thus the statement that is not a common property is:

---

Solution

Software validation checks whether the software meets the requirements and expectations of the customer.

---

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

Given minterms are:

$0,1,2,3,6,12,13,14,15$

$A'B'$ covers minterms $0,1,2,3$

$AB$ covers minterms $12,13,14,15$

Remaining minterm is $6$

Option (B):

$A'CD'$ covers minterms $2,6$

Both are present in the function.

So, option (B) is correct.

Option (D):

$BCD'$ covers minterms $6,14$

Both are present in the function.

So, option (D) is also correct.

Options (A) and (C) include minterm $4$, which is not present in the function.

---

Solution

A grammar is ambiguous if a string generated by it has more than one parse tree.

Equivalent definitions:

• More than one leftmost derivation

• More than one rightmost derivation

Thus the correct statements are:

B and C.

---

Solution

Morphological analysis, semantic analysis and pragmatic analysis are standard components of natural language understanding.

Meaning analysis is not a standard separate component because meaning is covered under semantic analysis.

---

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 a k-segment pipeline, theoretical maximum speedup is $k$.

So, statement A is true.

In practical cases, due to pipeline filling time, emptying time, delays and unequal stages, exact maximum speedup $k$ is not achieved.

So, statement B is true.

All pipeline segments need not take exactly the same computation time.

So, statement C is false.

---

Solution

Steps in page replacement:

No frame is free → D

Find a frame to replace → A

Free that frame → E

Update the page table → B

Use the freed frame for the new page → C

---

Solution

A contains numbers of the form:

$4n + 2$

So, numbers in A are:

$6, 10, 14, 18, 22, 26, 30, ...$

B contains multiples of 3:

$3, 6, 9, 12, 15, 18, 21, 24, 27, 30, ...$

Common elements are:

$6, 18, 30, 42, ...$

These can be written as:

$12n - 6$

---

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

A multiprocessor system has multiple processors controlled by one operating system.

So, statement A is true.

Multiple computers connected through communication lines describes a distributed system or multicomputer system, not a tightly coupled multiprocessor system.

So, statement B is false.

Multiprocessor systems are generally classified as MIMD systems, that means multiple instruction stream and multiple data stream.

So, statement C is true.

Therefore, A and C only are correct.

---

Solution

Typical DBMS query processing steps:

Scanning, parsing and validating → C

Query optimizer → A

Query code generator → D

Runtime database processor → B

Correct order:

C → A → D → B

---

Solution

In an unclustered B+ tree, retrieving records in sorted order requires scanning index entries and then fetching records from data pages.

Cost of scanning leaf level entries:

$F \times N$

Number of records:

$P \times N$

So, total cost:

$FN + PN = (F + P)N$

Final Answer: (b) (F + P) * N

---

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

XML is used to store and transport data, not to display data like HTML.

So, statement A is false.

XML defines syntax for representing data, but meaning depends on application.

So, statement B is true.

XML tags are case-sensitive.

So, <Letter>, <LETTER>, and <letter> are different tags.

So, statement C is true.

---

Solution

Insert words sequentially into BST.

banana → root

peach → right of banana

apple → left of banana

pear → right of peach

coconut → left of peach

mango → right of coconut

papaya → right of mango

Longest path:

banana → peach → coconut → mango → papaya

Number of edges = 4

---

Solution

Assertion A is true because FIFO page replacement may show Belady’s anomaly.

In Belady’s anomaly, increasing the number of page frames can sometimes increase the number of page faults.

Reason R is true, but it is not the correct explanation of Assertion A.

---

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

In perspective projection, parallel lines generally meet at vanishing point.

So, statement A is true.

Perspective transformation involves perspective division, commonly by z-coordinate.

So, statement B is true.

Because division is involved, perspective transformation is not linear.

So, statement C is false.

---

Solution

Verification → Quality Assurance → IV

Validation → Quality Control → III

Internal logic exercise → White box testing → I

Software requirement exercise → Black box testing → II

Matching:

A → IV

B → III

C → I

D → II

---

Solution

Initial semaphore value = 7

Each P operation decreases the value by 1.

Each V operation increases the value by 1.

So,

$7 - 20 + x = 5$

$x - 13 = 5$

$x = 18$

---

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

Phong shading requires more computation than Gouraud shading.

So, statement A is false.

Gouraud shading computes color at vertices and interpolates color inside the polygon.

So, statement B is true.

Phong shading interpolates normal vectors and then computes illumination.

So, statement C is true.

---

Solution

Memory required:

$2048 \times 8$

Each chip:

$128 \times 4$

First match word size:

$8 / 4 = 2$ chips per word.

Now match number of words:

$2048 / 128 = 16$

Total chips:

$16 \times 2 = 32$

---

Solution

Using Amdahl’s law:

Fraction improved = $0.30$

Speedup of improved part = $2$

Overall speedup:

$S = \frac{1}{(1 - 0.30) + \frac{0.30}{2}}$

$S = \frac{1}{0.70 + 0.15}$

$S = \frac{1}{0.85}$

$S = 1.176 \approx 1.18$

---

Solution

Given network block is:

$130.56.0.0/16$

So, the network prefix part is:

$130.56$

---

Solution

Two operations conflict if:

They belong to different transactions.

They operate on the same data item.

At least one operation is write.

So, statements A, B and C are true.

Statement D is false because conflict needs same data item, not different data items.

---

Solution

A: False when $r=1, p=0$ → Not tautology

B: False when $p=1, r=0$ → Not tautology

C:

$\sim p \rightarrow (p \rightarrow r)$

Always true → Tautology

D:

$(p \land r) \rightarrow (p \rightarrow r)$

Always true → Tautology

E:

$\sim(p \rightarrow r) \rightarrow p$

Always true → Tautology

Thus tautologies:

C, D, E

---

Solution

Scaling transformation is used to increase or decrease the size of a 2-dimensional object.

---

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

Software reliability can be described with respect to different time measures such as execution time, calendar time and clock time.

So, all A, B and C are correct.

---

Solution

Sequential circuits depend on previous state (memory).

• Flip-flop → sequential circuit

• Counter → sequential circuit

Multiplexer, Decoder and Adder are combinational circuits.

---

Solution

For a 3D array $A[a][b][c]$ stored in row major order:

Address of $A[r][s][t]$ is

Base address + $w[(r \times b \times c) + (s \times c) + t]$

So,

Address = $ A[0][0][0] + w(bcr + c*s + t)$

---

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

For object-behavioral modeling, analyst evaluates use-cases.

State transition diagram is also built to show object states and transitions.

The model is reviewed for accuracy and consistency.

Statement D is not correct as written, because events should drive the interaction sequence, not “do not derive” it.

---

Solution

Union → User defined data type → IV

Function → Subroutine → III

Interactive Environment → Virtual Reality → I

Output device → Shadow mask → II

Matching:

A → IV

B → III

C → I

D → II

---

Solution

Cost Performance Index is calculated as:

$CPI = \frac{BCWP}{ACWP}$

That means:

Budgeted cost of work performed ÷ Actual cost of work performed

---

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

Behavioral testing means black-box testing.

Equivalence partitioning is a black-box testing technique.

Graph-based testing method is also a behavioral testing technique.

Boundary value analysis is also a black-box testing technique.

Data flow testing and loop testing are white-box testing techniques.

Therefore, A, B and C only are correct.

---

Solution

A Perceptron is a single-layer feed-forward neural network used for linear classification.

---

Solution

After reboot, the TCP server can again start listening on port P.

The old TCP connection state is lost after reboot. So, if the client sends a packet for the old connection, the server does not recognize it and sends an RST segment.

---

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

For an algorithm to have tight running time $\Theta(g(n))$, worst-case should be $O(g(n))$ and best-case should be $\Omega(g(n))$.

This condition is given in statement A.

Statement B reverses the required bounds.

Statement C is false because $O(g(n))$ and $\Omega(g(n))$ are not always equal.

Statement D is false because a function cannot be both smaller order and larger order than the same $g(n)$.

---

Solution

Backtracking → Predictive parsing may require backtracking → III

Infinite languages with matching numbers → handled using Automata → I

Canonical LR parser → requires large number of states → IV

Post Correspondence Problem → Undecidable problem → II

Matching:

A → III

B → I

C → IV

D → II

---

Solution

Number of transactions per second:

$ \frac{20000}{120} = 166.67 $

Size of each article:

$3k$ bytes $= 3000$ bytes

$3000$ bytes $= 3000 \times 8 = 24000$ bits

Throughput:

$166.67 \times 24000 = 4000000$ bits per second

$= 4$ megabits per second

---

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

(A) True, because every tree is bipartite, so it is 2-colorable.

(B) False, because a bipartite graph has no odd cycle, but it can have even cycles.

(C) True, because every bipartite graph is 2-colorable.

(D) True, by greedy coloring, any graph with maximum degree $d$ can be colored using at most $d+1$ colors.

(E) False, because having $O(|V|)$ edges does not guarantee coloring with only $O(\log |V|)$ colors.

So, incorrect statements are (B) and (E).

---

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

Transmission delay

$= \frac{\text{Frame size}}{\text{Bandwidth}}$

$= \frac{10\times10^6}{6\times10^6}$

$= 1.6667\ s$

Propagation delay

Distance $=5000\ km =5\times10^6\ m$

$= \frac{5\times10^6}{2\times10^8}$

$=0.025\ s$

Router delay

Each router delay $=2\mu s+1\mu s=3\mu s$

Total routers $=20$

Total delay $=20\times3\mu s=60\mu s=0.00006\ s$

Total latency

$=1.6667+0.025+0.00006$

$\approx1.691726\ s$

---

Solution

A is correct because a database design is in BCNF when every relation schema in the design is in BCNF.

B is incorrect because BCNF removes dependency problems caused by non-super-key determinants.

C is correct because 3NF decomposition can be made lossless.

D is correct because 4NF deals with multivalued dependencies.

---

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

A hash function takes an input message of arbitrary length and produces a fixed length hash value.

So, statement (A) is true.

Statement (B) is false because hash function output is fixed length, not variable length.

Statement (C) is true because two different messages may produce the same hash value. This is called collision.

Therefore, true statements are (A) and (C) only.

---

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

First bit is fixed as 0, so remaining 3 bits are free.

Possible strings:

0000

0001

0010

0011

0100

0101

0110

0111

Total outcomes $=8$

Strings with at least two consecutive 0's:

0000

0001

0010

0011

0100

Favourable outcomes $=5$

Probability

$=\frac{5}{8}$

---

Solution

In a production system, conflict resolution can be based on the rule matched, the object matched, or the action of the matched rule.

But assigning preference based on the action that the matched object would perform is not a standard conflict resolution approach.

---

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

For context free languages, equivalence problem is undecidable.

So,

$L(G_1)=L(G_2)$ is undecidable.

Also, inclusion problem for context free languages is undecidable.

So,

$L(G_2)\subseteq L(G_1)$ is undecidable.

Now,

$L(G_1)=R$

is also undecidable because if $R=\Sigma^*$, then this becomes CFL universality problem:

$L(G_1)=\Sigma^*$

which is undecidable.

Therefore, all three problems are undecidable.

---

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

In LR parsing, shift-reduce conflicts occur when the parser can either shift the next input symbol or reduce using a rule.

These conflicts are resolved using operator precedence and associativity rules.

---

Solution

S1 is false because LRU does not suffer from Belady’s anomaly.

S2 is true because shortest remaining time first may cause starvation for long processes.

S3 is false because each thread has its own stack.

Final Answer: (b) S1, S3 false and S2 is true

---

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

For $L_1$:

$L_1=\{a^{2^z}\mid z\text{ is an integer}\}$

The possible lengths are:

$1,2,4,8,16,32,\ldots$

So,

$L_1=\{a,a^2,a^4,a^8,a^{16},\ldots\}$

This is not regular because the gap between consecutive string lengths keeps increasing.

So, $L_1$ is not regular.

For $L_2$:

$L_2=\{a^{2z}\mid z\ge 0\}$

The possible lengths are:

$0,2,4,6,8,\ldots$

So,

$L_2=\{\lambda,a^2,a^4,a^6,\ldots\}$

This language contains all strings of even length over alphabet $\{a\}$.

It can be written as:

$L_2=(aa)^*$

Since $(aa)^*$ is a regular expression, $L_2$ is regular.

For $L_3$:

$L_3=\{\omega\omega\mid \omega\in\{a,b\}^*\}$

In this language, the second half of the string must be exactly the same as the first half.

A finite automaton cannot remember the complete first half and compare it with the second half.

So, $L_3$ is not regular.

Therefore, only $L_2$ is regular.

---

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

Backpropagation computes error at the output layer (sink) and propagates the error backwards through hidden layers toward the input layer (source) to update weights.

---

Solution

Find closure of $EC$:

$EC^+ = {E, C}$

Using $E \to A$,

$EC^+ = {E, C, A}$

Using $A \to B$,

$EC^+ = {E, C, A, B}$

Using $EC \to D$,

$EC^+ = {E, C, A, B, D}$

So, $EC$ determines all attributes.

---

Solution

---

Solution

A grammar is ambiguous if at least one string has more than one parse tree or more than one leftmost derivation.

For grammar $(A)$:

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

The string $abab$ can be generated in more than one way.

First derivation:

$S\Rightarrow SS$

$\Rightarrow aSbS$

$\Rightarrow abS$

$\Rightarrow abaSb$

$\Rightarrow abab$

Second derivation:

$S\Rightarrow aSb$

$\Rightarrow abSab$

$\Rightarrow abab$

So, grammar $(A)$ is ambiguous.

For grammar $(B)$:

$S\rightarrow aSbS\mid bSaS\mid \lambda$

The string $abab$ can be generated in more than one way.

First derivation:

$S\Rightarrow aSbS$

$\Rightarrow abS$

$\Rightarrow abaSbS$

$\Rightarrow abab$

Second derivation:

$S\Rightarrow aSbS$

$\Rightarrow a(bSaS)bS$

$\Rightarrow abab$

So, grammar $(B)$ is ambiguous.

For grammar $(C)$:

$S\rightarrow aAB$

$A\rightarrow bBb$

$B\rightarrow A\mid \lambda$

The string $abbbb$ can be generated in two ways.

First way:

$S\Rightarrow aAB$

$\Rightarrow a(bb)(bb)$

$\Rightarrow abbbb$

Second way:

$S\Rightarrow aAB$

$\Rightarrow a(bbbb)(\lambda)$

$\Rightarrow abbbb$

So, grammar $(C)$ is also ambiguous.

Therefore, grammars $(A)$, $(B)$ and $(C)$ all are ambiguous.

---

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

Speed hierarchy of memory/storage:

CPU Registers → fastest

SRAM → cache memory

DRAM → main memory

Hard Disk → secondary storage

Magnetic Tape → slowest storage

Order:

C → B → A → E → D

---

Solution

hysical layer deals with transmission of raw bits.

Data Link Layer converts raw bits into frames.

Network layer controls and monitors subnet.

Transport layer supports connection-oriented and connectionless transmission.

So,

A – III, B – I, C – II, D – IV

---

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 cloud computing, pooling and sharing of resources means multiple users can use shared computing resources like CPU, memory, storage and network.

Virtualization is the main concept that helps in pooling and sharing of resources.

Using virtualization, one physical machine can be divided into multiple virtual machines.

So, many users can share the same physical resources.

Virtual Memory is an operating system concept, not mainly a cloud computing concept for resource pooling.

Service means providing facilities like $IaaS$, $PaaS$ and $SaaS$, but the direct concept related to pooling and sharing is virtualization.

Therefore, only $(C)$ Virtualization is correct.

---

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 → False (only owner or DBA can grant privileges)

B → True

C → False (system error is not a malicious attack)

D → True

False statements:

A and C

---

Solution

In worst case, insertion causes splitting at every level.

There are 4 levels, so 4 new nodes may be created due to splitting.

If the root also splits, one extra new root node is created.

Maximum newly created nodes:

$4 + 1 = 5$

---

Solution

In synchronous interleaved memory organization,

For $m\ll n$,

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

For $m\gg n$,

$t=T$

---

Solution

POP is used by a client to download emails from the mail server.

POP has two modes:

Delete mode and keep mode.

In Delete mode, after the client retrieves the mail, the mail is deleted from the mailbox.

So, statement $(B)$ is true.

In Delete mode, mail is not deleted before retrieval.

So, statement $(C)$ is false.

In keep mode, mail is not deleted after retrieval.

The mail remains in the mailbox even after retrieval.

So, statement $(E)$ is true.

Statement $(D)$ is false because in keep mode mail is not deleted before retrieval.

Therefore, true statements are $(A)$, $(B)$ and $(E)$.

---

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

Count to infinity → Distance vector routing 

---

Solution

Regular languages:

Closed under union, concatenation, intersection, complement, kleene star.

Context-free languages:

Closed under union, concatenation, kleene star.

Not closed under intersection and complement.

Thus incorrect statements:

C and D

---

Solution

---

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

A firewall can filter packets using information present in the packet header.

It can filter packets on the basis of Source IP Address.

So, statement (A) is true.

It can filter packets on the basis of Destination IP Address.

So, statement (B) is true.

It can filter packets on the basis of TCP Source Port.

So, statement (C) is true.

It can filter packets on the basis of UDP Source Port.

So, statement (D) is true.

It can also filter packets on the basis of TCP Destination Port.

So, statement (E) is true.

Therefore, all statements (A), (B), (C), (D) and (E) are correct.

---

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

• Digital Signature → Confirms authenticity and integrity 
• Hash Function → Produces a fixed-size digest 
• AES → Symmetric encryption algorithm 
• RSA → Asymmetric encryption algorithm

---

Solution

Effective address:

$EA = ADR + XR$

This is indexed addressing, where the address field is added to the index register.

---

Solution

---

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 statement says that a radical person is electable if he or she is conservative, otherwise not electable.

This means, for a radical person, electability depends exactly on conservativeness.

So, the correct logical form is:

$R\Rightarrow(E\Leftrightarrow C)$

Therefore, statement (B) is true.

Now,

$E\Leftrightarrow C$

can be written as:

$(E\Rightarrow C)\land(C\Rightarrow E)$

So,

$R\Rightarrow[(E\Rightarrow C)\land(C\Rightarrow E)]$

Now convert implications:

$E\Rightarrow C\equiv \neg E\lor C$

$C\Rightarrow E\equiv \neg C\lor E$

Therefore,

$R\Rightarrow[(\neg E\lor C)\land(\neg C\lor E)]$

This is equivalent to:

$(\neg R\lor \neg E\lor C)\land(\neg R\lor \neg C\lor E)$

So, statement (D) is also true.

Statement (A) is not correct because it says that a person is conservative if and only if the person is radical and electable, which is not the meaning of the given sentence.

Statement (C) is not the exact logical assertion of the given sentence.

Therefore, correct statements are (B) and (D).

---

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

• LL(0) is the weakest (no lookahead, top-down).
• LR(0) is stronger than LL(0) (bottom-up, no lookahead).
• SLR(1) adds 1-symbol lookahead using FOLLOW sets → accepts more grammars than LR(0).
• LALR(1) merges LR(1) states; more powerful than SLR(1) but below LR(1).
• LR(1) is the most powerful among these deterministic bottom-up parsers.

---

Solution

For 8-bit signed integer (two’s complement):

Range = $-2^{7}$ to $2^{7}-1$

Least value = $-128$

For 8-bit unsigned integer:

Range = $0$ to $2^{8}-1$

Least value = $0$

---

Solution

---

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

Statement (A) is false.

Entailment means if $\alpha$ is true, then $\beta$ must be true in all models where $\alpha$ is true.

Correct definition is:

$\alpha\models\beta$

means $\beta$ is true in every model in which $\alpha$ is true.

But statement (A) says few worlds, so it is false.

Statement (B) is true.

Forward chaining and backward chaining are natural reasoning algorithms for Horn form knowledge bases.

Statement (C) is false.

Sound inference algorithm derives only those sentences that are logically entailed.

But deriving all entailed sentences is the property of completeness, not soundness.

Statement (D) is true.

Propositional logic does not scale well to environments of unbounded size because it cannot represent general rules using variables and quantifiers.

Therefore, true statements are (B) and (D).

---

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

• An adjacency matrix represents a graph using a 2D array (matrix).
• This type of storage uses sequential memory allocation — rows and columns are stored in contiguous memory.
• Hence, this method is called a Sequential Representation of a graph.

---

Solution

Cardinality means number of elements in the set.

$|A_1| = 2$

$|A_2| = 4$

$|A_3| = 1$

$|A_4| = 3$

$|A_5| = 5$

Increasing order:

$1 < 2 < 3 < 4 < 5$

So order becomes:

$A_3, A_1, A_4, A_2, A_5$

---

Solution

---

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

Minimax search is generally implemented using depth-first search, not breadth-first search.

Statement (B) is true.

Alpha-beta pruning depends highly on the order in which states are examined.

If the best moves are examined first, more pruning is possible.

Statement (C) is true.

Alpha-beta pruning does not change the final result of minimax.

It only reduces the number of nodes examined.

So, alpha-beta search computes the same optimal move as minimax.

Statement (D) is false.

In games of imperfect information, optimal play requires reasoning about current and future belief states of each player.

Therefore, true statements are (B) and (C).

---

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

• User-Mode Programs have the lowest priority and are preemptible.
• Kernel System Service Routines run in kernel mode and can be preempted by higher priority tasks like interrupts.
• Bottom Half Interrupt Handlers execute after the top half and have higher priority than kernel threads.
• Top Half Interrupt Handlers handle immediate hardware responses and have the highest priority.

---

Solution

A:

For every integer $n$, choose $m=n^2+1$

Then $n^2<m$ → True

B:

$\exists m$ such that $n<m^2$ for all integers $n$.

But integers are unbounded → False

C:

$n^2+m^2=5$

Example: $1^2+2^2=5$ → True

D:

$n^2+m^2=6$

No integer solution → False

E:

$n+m=4$

$n-m=1$

Add equations:

$2n=5$ → $n=2.5$ (not integer) → False

True statements: A and C

---

Solution

---

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

Given,

$R_1=\{(1,1),(2,2),(3,3)\}$

$R_2=\{(1,1),(1,2),(1,3),(1,4)\}$

Now,

$R_1\cup R_2$

means all elements of $R_1$ and $R_2$.

So,

$R_1\cup R_2=\{(1,1),(1,2),(1,3),(1,4),(2,2),(3,3)\}$

Therefore, (A) matches with I.

Now,

$R_1-R_2$

means elements that are in $R_1$ but not in $R_2$.

Common element is $(1,1)$.

So,

$R_1-R_2=\{(2,2),(3,3)\}$

Therefore, (B) matches with IV.

Now,

$R_1\cap R_2$

means common elements of $R_1$ and $R_2$.

So,

$R_1\cap R_2=\{(1,1)\}$

Therefore, (C) matches with II.

Now,

$R_2-R_1$

means elements that are in $R_2$ but not in $R_1$.

So,

$R_2-R_1=\{(1,2),(1,3),(1,4)\}$

Therefore, (D) matches with III.

Final matching is:

A-I, B-IV, C-II, D-III

---

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

Complexity increases as follows:

Rule-based system → simplest

Shallow neural network → moderate complexity

CNN image classification → more complex

Autonomous driving → highly complex system

Thus increasing order:

A → B → C → D