---

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

“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

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

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

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

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

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

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

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

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

(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

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

Total length of bit string is $10$.

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

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

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

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

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

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

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

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

Remaining $7$ bits are free.

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

Therefore,

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

$=512+256-128$

$=640$

---

Solution

Given,

$V=6$

Each vertex has degree $4$.

So, sum of degrees is

$6 \times 4=24$

By handshaking theorem,

$2E=24$

$E=12$

For a connected planar graph, Euler’s formula is

$V-E+R=2$

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

$6-12+R=2$

$R=8$

---

Solution

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

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

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

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

Therefore,

$m=n$

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

So,

$m,n \ge 2$

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

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

---

Solution

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

Given statement is

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

We know that

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

So,

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

Now truth table se false cases:

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

$p \vee q$

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

$\neg p \vee q$

Therefore, PCNF is

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

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

---

Solution

A standard deck has

$13$ hearts

and

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

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

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

Then, we may select only $2$ hearts.

So, cards selected without guaranteeing $3$ hearts:

$39+2=41$

Now, the next card must be a heart.

So, required number of cards is

$41+1=42$

---

Solution

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

First,

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

So,

$(a) \rightarrow (iv)$

Now,

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

So,

$(b) \rightarrow (iii)$

Now,

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

Therefore,

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

Using De Morgan’s law,

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

$=p \wedge q$

So,

$(c) \rightarrow (i)$

Now,

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

Using De Morgan’s law,

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

So,

$(d) \rightarrow (ii)$

Therefore, the correct matching is

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

---

Solution

Given 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

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

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

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

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

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

To form a triangle, we can choose:

2 points from line AB and 1 point from line AC

or

2 points from line AC and 1 point from line AB

Number of triangles:

$ {m \choose 2}n + {n \choose 2}m $

$ = \frac{m(m-1)}{2}n + \frac{n(n-1)}{2}m $

$ = \frac{mn}{2}[(m-1)+(n-1)] $

$ = \frac{1}{2}mn(m+n-2) $

---

Solution

$2^{50} \times 2^{-38} = 2^{12}$ seconds

$2^{12} = 4096$ seconds

Convert to minutes:

$4096/60 \approx 68.27$ minutes

$\approx 1.14$ hours

---

Solution

---

Solution

Letters: 26 (A to Z)

Two digit positive integers:

01 to 99 → 99 numbers

Total combinations:

$26 \times 99 = 2574$

---

Solution

Greedy Best-First Search selects the node that appears closest to the goal according to heuristic value.

It may get trapped and can be incomplete even if the search space is finite.

So, (A) matches with II.

$A^*$ search is optimal and complete under proper conditions, but its computation and space complexity are very high because it stores many generated nodes.

So, (B) matches with IV.

Recursive Best-First Search uses limited memory and its space complexity is linear in depth.

So, (C) matches with I.

$SMA^*$ means Simplified Memory-Bounded $A^*$.

It is optimal if the optimal solution is reachable within available memory; otherwise, it returns the best reachable solution.

So, (D) matches with III.

Final matching is:

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

---

Solution

Typical modeling steps:

Formulate model mathematically → B

Solve mathematically → C

Fit solution with data → A

If poor fit, reformulate → D

Interpret results → E

Correct sequence:

B → C → A → D → E

---

Solution

Typical construction steps:

Problem statement → D

Convert to regular expression → B

Convert to NFA-ε → C

Convert to DFA → E

Minimize DFA → A

Order:

D → B → C → E → A

---

Solution

Statement I:

We need to check whether $5$ divides $n^5-n$.

By Fermat's theorem,

$n^5\equiv n\pmod 5$

So,

$n^5-n\equiv 0\pmod 5$

Therefore, $5$ divides $n^5-n$.

So, Statement I is correct.

Statement II:

$n^3-n=n(n-1)(n+1)$

This is the product of three consecutive integers.

In any three consecutive integers, one number is divisible by $3$ and at least one number is divisible by $2$.

So, the product is divisible by $6$.

Therefore, $6$ divides $n^3-n$.

So, Statement II is also correct.

---

Solution

---

Solution

---

Solution

$a*b=a+b+2$

Associativity

$(a*b)*c=(a+b+2)+c+2=a+b+c+4$

$a*(b*c)=a+(b+c+2)+2=a+b+c+4$

Identity element:

$a*e=a$

$a+e+2=a$

$e=-2$

Inverse:

$a*b=-2$

$a+b+2=-2$

$b=-a-4$

---

Solution

Characteristic equation

$r^2-8r+16=0$

$(r-4)^2=0$

$r=4$

General solution

$a_n=(c_1+c_2n)4^n$

Thus valid sequences:

$4^n$

$n4^n$

---

Solution

---

Solution

Let

$f(2^k) = g(k)$

Then recurrence becomes

$g(k) = 5g(k-1) + 3$

with

$g(0) = f(1) = 7$

Solve recurrence.

Homogeneous solution:

$g_h(k) = C5^k$

Particular solution:

Assume constant $A$

$A = 5A + 3$

$-4A = 3$

$A = -\frac{3}{4}$

General solution:

$g(k) = C5^k - \frac{3}{4}$

Use initial condition

$g(0) = 7$

$C - \frac{3}{4} = 7$

$C = \frac{31}{4}$

Thus

$f(2^k) = \frac{31}{4}5^k - \frac{3}{4}$

---

Solution

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

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

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

---

Solution

$x_1=1000,\ x_2=500$

Now,

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

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

$x_2=500\le 600$

Also,

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

So, all constraints are satisfied.

---

Solution

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

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

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

Here,

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

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

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

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

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

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

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

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

So,

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

and

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

---

Solution

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

Relation $R$ is defined as:

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

Symmetric:

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

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

Therefore, $R$ is not symmetric.

Transitive:

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

Therefore, $R$ is transitive.

Equivalence relation:

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

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

So, $R$ is not an equivalence relation.

Partial order relation:

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

Here, $R$ is not reflexive.

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

---

Solution

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

Total number of vertices:

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

For a tree,

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

Sum of degrees:

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

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

By handshaking theorem,

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

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

$12n-2=11n$

$n=2$

So,

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

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

---

Solution

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

$n^2$

Here,

$n=4$

So, total ordered pairs:

$4^2=16$

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

Number of compulsory diagonal pairs:

$4$

Remaining pairs:

$16-4=12$

Each remaining pair can be either selected or not selected.

So, number of reflexive relations:

$2^{12}$

---

Solution

We have,

$45=3^2\times 5$

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

Using Euler's phi function,

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

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

$=24$

---

Solution

Statement $S_1$ is true.

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

So,

$P\subseteq CO-NP$

Statement $S_2$ is also true.

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

$NP=CO-NP$

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

Therefore, $P\ne NP$.

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

---

Solution

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

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

So,

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

Now consider $S_2$.

For prime $p$, Fermat's theorem gives

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

for $a\in Z_p^*$.

But $S_2$ says

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

This is not generally true.

Actually,

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

So, $S_2$ is false.

---

Solution

Dirac’s theorem states that if a simple graph with $n \ge 3$ vertices satisfies

$deg(v) \ge \frac{n}{2}$

for every vertex $v$, then the graph is Hamiltonian.

Thus the degree of each vertex must be at least half of the number of vertices.

---

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

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.

---

Solution

---

Solution

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

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

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

Therefore, all three statements are decidable.

---

Solution

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

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

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

Rejecting means it halts without reaching an acceptable state.

Therefore, the correct condition is:

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

---

Solution

We have to find:

$7^{17}\bmod 561$

Now,

$7^2=49$

$7^4=49^2=2401$

$2401\bmod 561=157$

So,

$7^4\bmod 561=157$

Now,

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

$157^2=24649$

$24649\bmod 561=526$

So,

$7^8\bmod 561=526$

Now,

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

$526^2=276676$

$276676\bmod 561=103$

So,

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

Now,

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

$=103\times 7\bmod 561$

$=721\bmod 561$

$=160$

---

Solution

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

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

So, a clique forms a complete subgraph.

---

Solution

---

Solution

---

Solution

---

Solution

---

Solution

Translate each statement:
(a) “If intelligent then unhappy” ⇒ P → ¬Q.
(b) “Neither intelligent nor happy” ⇒ ¬P ∧ ¬Q.
(c) “Being not intelligent is necessary for being happy” ⇒ Q → ¬P.
(d) “Not intelligent implies unhappy” ⇒ ¬P → ¬Q.

Only Option 3 matches all four translations.

Answer: 3

---

Solution

Given Reason statements are:

$r\to \bar{q}$

$r\lor s$

$s\to \bar{q}$

$p\to q$

From $r\lor s$, either $r$ is true or $s$ is true.

Case 1:

If $r$ is true, then using $r\to \bar{q}$, we get:

$\bar{q}$

Case 2:

If $s$ is true, then using $s\to \bar{q}$, we get:

$\bar{q}$

So, in both cases:

$\bar{q}$ is true.

Now we also have:

$p\to q$

Using modus tollens:

$p\to q$ and $\bar{q}$ imply $\bar{p}$.

Therefore, Assertion (A), that is $\bar{p}$, is true.

Also, Reason (R) correctly explains how $\bar{p}$ is obtained.

Hence, both (A) and (R) are true and (R) is the correct explanation of (A).

---

Solution

A statement in mathematical logic is a declarative sentence which has a definite truth value, either true or false.

$(i)$ There will be snow in January.
This is a declarative sentence. So, it is a statement.

$(ii)$ What is the time now?
This is a question. So, it is not a statement.

$(iii)$ Today is Sunday.
This is a declarative sentence. So, it is a statement.

$(iv)$ You must study Discrete Mathematics.
This is a command or advice. So, it is not a statement.

Therefore, only $(i)$ and $(iii)$ are statements.

---

Solution

Equivalence is represented by

$p\Leftrightarrow q$

So,

$(a)\rightarrow(iv)$

Contrapositive of $p\Rightarrow q$ is

$\sim q\Rightarrow \sim p$

So,

$(b)\rightarrow(iii)$

Converse of $p\Rightarrow q$ is

$q\Rightarrow p$

So,

$(c)\rightarrow(ii)$

Implication is represented by

$p\Rightarrow q$

So,

$(d)\rightarrow(i)$

Therefore, correct matching is

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

---

Solution

Total balls are

$6+4=10$

Number of ways to select $4$ balls from $10$ balls is

${}^{10}C_4$

We need exactly $2$ red balls and $2$ green balls.

Number of ways to select $2$ red balls from $6$ red balls is

${}^{6}C_2$

Number of ways to select $2$ green balls from $4$ green balls is

${}^{4}C_2$

So, required probability is

$\dfrac{{}^{6}C_2 \times {}^{4}C_2}{{}^{10}C_4}$

$=\dfrac{15 \times 6}{210}$

$=\dfrac{90}{210}$

$=\dfrac{3}{7}$

---

Solution

All four AVL rotation cases are correctly explained:

LL case: left of left

RR case: right of right

LR case: right of left

RL case: left of right

So, correct option is:

$\boxed{(c)\ \text{A, B, C and D}}$

---

Solution

Let Bus, Train and Automobile be represented by $B,T,A$ respectively.

Given,

$n(B)=30$

$n(T)=35$

$n(A)=100$

$n(B\cap T)=15$

$n(B\cap A)=15$

$n(T\cap A)=20$

$n(B\cap T\cap A)=5$

Using the formula,

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

Now,

$n(B\cup T\cup A)=30+35+100-15-15-20+5$

$=165-50+5$

$=120$

Therefore, $120$ people completed the survey form.

---

Solution

In divide and conquer matrix multiplication, matrix is divided into smaller submatrices.

There are $8$ recursive multiplications of size $n/2$.

So, recurrence is:

$T(n)=8T(n/2)+\Theta(n^2)$

Using Master Theorem:

$a=8,\ b=2$

$n^{\log_b a}=n^{\log_2 8}=n^3$

So,

$T(n)=\Theta(n^3)$

Therefore, A, C and E are correct.

Correct option is:

$\boxed{(a)\ \text{A, C, E only}}$

---

Solution

For $S_1$:

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

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

These two statements are not logically equivalent.

So, $S_1$ is true.

For $S_2$:

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

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

These two statements are also not logically equivalent.

So, $S_2$ is true.

---

Solution

In PERT/CPM network, a merge event is an event where two or more activities come together.

It represents the joining of two or more events or activities.

Therefore, the merge event represents joining.

---

Solution

Given objective function is

$z=-2x_1-3x_2$

To maximize $z=-2x_1-3x_2$, we need to minimize the negative loss.

The main lower constraint is

$x_1+x_2\geq 2$

Now check the feasible corner points on $x_1+x_2=2$:

If $x_2=0$, then

$x_1=2$

So, point is $(2,0)$.

At $(2,0)$,

$z=-2(2)-3(0)$

$z=-4$

If $x_1=0$, then

$x_2=2$

So, point is $(0,2)$.

At $(0,2)$,

$z=-2(0)-3(2)$

$z=-6$

Since $-4>-6$, maximum value is $-4$.

Also, $(2,0)$ satisfies the other constraints:

$2x_1+x_2=2(2)+0=4\leq 10$

$x_1+x_2=2+0=2\leq 8$

Therefore, optimal solution is

$x_1=2,\ x_2=0,\ z=-4$

---

Solution

Using Kruskal's algorithm, we select edges in increasing order of weights, without forming a cycle.

From the graph, the selected edge weights are:

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

Since the graph has $9$ vertices, the minimum spanning tree must have

$9-1=8$ edges.

Now, total weight of MST is

$1+1+1+2+2+2+3+4$

$=16$

Therefore, the weight of the minimum spanning tree is

$16$

---

Solution

For $S_1$:

By Lagrange theorem, the order of every element of a finite group divides the order of the group.

So, if $m$ is the order of element $a$, then $m$ divides $n$.

Hence, $S_1$ is true.

For $S_2$:

If a finite group has even order, then there exists at least one non-identity element of order $2$.

So, there exists $a\ne e$ such that:

$a*a=e$

Hence, $S_2$ is also true.

---

Solution

The final simplex table of the primal problem also gives information about the optimal solution of the dual problem.

Statement (b) is correct.

By strong duality theorem, if one problem has a finite optimal solution, then the other also has a finite optimal solution.

Statement (c) is correct.

If one problem is unbounded, then the other problem is infeasible.

So, all three statements are correct.

---

Solution

Given:

$P$ : It is hot day

$q$ : Temperature is $48^\circ C$

Expression:

$\neg P \land \neg q$

Meaning:

$\neg P$ → It is not a hot day

$\neg q$ → Temperature is not $48^\circ C$

Combined with AND:

Neither $P$ nor $q$

Thus sentence:

"It is neither a hot day nor temperature is $48^\circ C$"

---

Solution

Statement:

“Joy is loved by everyone”

Meaning:

Every person $x$ loves Joy.

Mathematically:

$\forall x; L(x,;Joy)$

---

Solution

Database normal forms:

1NF → atomic values

2NF → remove partial dependency

3NF → remove transitive dependency

BCNF → stronger FD rules

4NF → multivalued dependency

5NF → join dependency

---

Solution

Sample space for 3 tosses:

$S={HHH,HHT,HTH,HTT,THH,THT,TTH,TTT}$

Thus

$n(S)=8$

Event: exactly 1 head or 2 heads

1 head → ${HTT,THT,TTH}$

2 heads → ${HHT,HTH,THH}$

So

$n(E)=6$

Probability

$P(E)=\frac{6}{8}=\frac{3}{4}$

Thus correct statements:

(B) and (C)

---

Solution

---

Solution

Statement $(i)$ is not a standard sufficient condition for Hamiltonian graph.

By Dirac's theorem, the sufficient condition is

$\deg(v)\geq \dfrac{n}{2}$

for every vertex $v$.

So, statement $(i)$ is false.

Statement $(ii)$ is true by Ore's theorem.

Ore's theorem says that if for every pair of non-adjacent vertices $v$ and $w$,

$\deg(v)+\deg(w)\geq n$

then the graph is Hamiltonian.

Statement $(iii)$ is not the standard sufficient condition here.

Therefore, only statement $(ii)$ is correct.

---

Solution

Given,

$T(n)=2T(\sqrt{n})+\lg n$

Let

$n=2^m$

So,

$\lg n=m$

and

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

Let

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

Then,

$S(m)=2S\left(\dfrac{m}{2}\right)+m$

Using Master theorem,

$a=2,\ b=2$

So,

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

Therefore,

$S(m)=O(m\lg m)$

Now put back $m=\lg n$.

So,

$T(n)=O(\lg n\lg(\lg n))$

---

Solution

---

Solution

For a connected component with $m$ vertices, minimum edges required:

$m-1$

If graph has $k$ connected components, then minimum total edges:

$=(n_1-1)+(n_2-1)+...+(n_k-1)$

$=(n_1+n_2+...+n_k)-k$

$=n-k$

Correct option is:

$\boxed{(d)\ n-k}$

---

Solution

Check A:

$\neg p\to(q\to r)\equiv p\lor(\neg q\lor r)$

$=p\lor\neg q\lor r$

Also,

$q\to(p\lor r)\equiv\neg q\lor p\lor r$

Both are same, so A is true.

Check B:

$(p\to q)\to r\equiv(p\land\neg q)\lor r$

$p\to(q\to r)\equiv\neg p\lor\neg q\lor r$

Both are not always same, so B is false.

Check C:

Both expressions are not always logically equivalent.

So, C is false.

Therefore, only A is correct.

---

Solution

Statement I is a standard identity of floor function:

$\lfloor 2x\rfloor=\lfloor x\rfloor+\left\lfloor x+\frac{1}{2}\right\rfloor$

So, Statement I is true.

Statement II is not always true.

Take $x=0.2$ and $y=0.2$.

$\lceil x+y\rceil=\lceil 0.4\rceil=1$

But,

$\lceil x\rceil+\lceil y\rceil=\lceil 0.2\rceil+\lceil 0.2\rceil=1+1=2$

So, Statement II is false.

---

Solution

We need to assign $5$ different jobs to $4$ different employees such that every employee gets at least one job.

This is an onto function problem.

Total ways without restriction:

$4^5=1024$

Subtract cases where at least one employee gets no job:

$\binom{4}{1}3^5=4\times243=972$

Add cases where two employees get no job:

$\binom{4}{2}2^5=6\times32=192$

Subtract cases where three employees get no job:

$\binom{4}{3}1^5=4$

Required ways:

$4^5-\binom{4}{1}3^5+\binom{4}{2}2^5-\binom{4}{3}1^5$

$=1024-972+192-4=240$

---

Solution

Total number of storage bins:

$50\times85\times5=21250$

By pigeonhole principle, if $21250$ products are stored, each product can be placed in a different bin.

To guarantee that at least two products are stored in the same bin, we need one more product.

So, least number of products:

$21250+1=21251$

---

Solution

Let number of ways to climb $n$ stairs be $f(n)$.

A person can reach the $n^{th}$ stair either from $(n-1)^{th}$ stair or from $(n-2)^{th}$ stair.

So,

$f(n)=f(n-1)+f(n-2)$

Base values:

$f(1)=1$

$f(2)=2$

Now,

$f(3)=3$

$f(4)=5$

$f(5)=8$

$f(6)=13$

$f(7)=21$

$f(8)=34$

---

Solution

A wheel graph $W_n$ has one central vertex connected to all vertices of a cycle.

In $W_n$, the central vertex has degree $n-1$.

Each outer vertex has degree $3$, because it is connected to two cycle vertices and one central vertex.

For the graph to be regular:

$n-1=3$

$n=4$

So, $W_4$ is regular.

---

Solution

A planar graph is a graph that can be drawn on a plane without any two edges crossing each other.

Graph A can be redrawn without edge crossing, so Graph A is planar.

Graph B is similar to $K_{3,3}$ structure. Since $K_{3,3}$ is non-planar, Graph B is not planar.

Graph C also contains a non-planar subdivision structure, so Graph C is not planar.

Therefore, only Graph A is planar.

---

Solution

Given condition means if two elements commute, then they must be equal.

For A:

$a*(a*a)=(a*a)*a$ by associativity.

So, $a$ and $a*a$ commute.

Hence, $a=a*a$.

So, A is true.

For B:

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

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

So, $a$ and $a*b*a$ commute.

Hence, $a*b*a=a$.

So, B is true.

For C:

Using B, $c*a*c=c$ and $a*c*a=a$.

Now,

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

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

So, $a*b*c$ and $a*c$ commute.

Hence, $a*b*c=a*c$.

So, C is also true.

---

Solution

Check corner points of feasible region.

Intersection of $x+3y=11$ and $4x+y=15$:

From $4x+y=15$,

$y=15-4x$

Put in $x+3y=11$:

$x+3(15-4x)=11$

$x+45-12x=11$

$-11x=-34$

$x=\frac{34}{11}$

Now,

$y=15-4\cdot\frac{34}{11}=\frac{29}{11}$

Objective value:

$Z=6x+5y$

$Z=6\cdot\frac{34}{11}+5\cdot\frac{29}{11}$

$Z=\frac{204+145}{11}=\frac{349}{11}=31.72$

Other corner values are smaller.

---

Solution

---

Solution

---

Solution

---

Solution

$P={9,5,2,7,6,16,9}$

$W={2,5,6,11,1,9,3}$

Find profit by weight ratio:

Item 5: $\frac{6}{1}=6$

Item 1: $\frac{9}{2}=4.5$

Item 7: $\frac{9}{3}=3$

Item 6: $\frac{16}{9}=1.77$

Now take items in decreasing ratio:

Total weight $=1+2+3+9=15$

Total profit $=6+9+9+16=40$

Correct option is:

$\boxed{(b)\ 40}$

---

Solution

Take items in decreasing profit by weight ratio:

Item 5: weight $1$, profit $6$

Item 1: weight $2$, profit $9$

Item 7: weight $3$, profit $9$

Item 6: weight $9$, profit $16$

Item 2: weight $5$, profit $5$

Total weight used:

$1+2+3+9+5=20$

Total profit:

$6+9+9+16+5=45$

Remaining capacity:

$25-20=5$

Next best item is item 4 with profit $7$ and weight $11$.

Fractional profit:

$5\times \frac{7}{11}=\frac{35}{11}=3.18$

Maximum profit:

$45+3.18=48.18\approx 48.1$

Correct option is:

$\boxed{(a)\ 48.1}$

---

Solution

For fractional knapsack, if items are already arranged according to profit by weight ratio, then best-case selection can be done in linear time.

Here, total items are:

$n=8$

So, best-case time complexity is:

$O(n)=O(8)$

Correct option is:

$\boxed{(a)\ O(8)}$

---

Solution

Fractional knapsack allows taking fractions of items.

So, we choose items according to highest profit by weight ratio.

This is a greedy approach.

Correct option is:

$\boxed{(c)\ \text{Greedy Algorithm}}$

---

Solution

In $0/1$ knapsack, an item is either selected completely or rejected completely.

In fractional knapsack, an item can be divided into smaller parts according to required weight.

So, correct option is:

$\boxed{(d)\ \text{In }0/1\text{ knapsack problem, items cannot be divided into smaller portions and in fractional knapsack we can divide the item into required proportions of weight}}$

---

Solution

We use the Master Theorem for $T(n) = aT(n/b) + f(n)$ Here, $a = 2$, $b = 4$, so $n^{\log_b a} = n^{\log_4 2} = n^{1/2} = \sqrt{n}$ Thus, $f(n) = \sqrt{n}$ is of the same order as $n^{\log_b a}$. Therefore, by Case 2 of Master Theorem, $T(n) = \Theta(n^{\log_b a} \log n) = \Theta(\sqrt{n} \log n)$ ✅ But wait! Let’s check growth dominance carefully: Actually, when $f(n) = \Theta(n^{\log_b a})$, we multiply by $\log n$, hence the correct bound is $\boxed{T(n) = \Theta(\sqrt{n} \log n)}$

---

Solution

Let total numbers = 200 Divisible by 2 → 200/2 = 100 Divisible by 5 → 200/5 = 40 Divisible by both (LCM 10) → 200/10 = 20 Using inclusion–exclusion: n(2 ∪ 5) = 100 + 40 − 20 = 120 Probability = 120 / 200 = 3/5

---

Solution

---

Solution

---

Solution

---

Solution

By Handshaking Theorem, sum of degrees of all vertices in an undirected graph is equal to twice the number of edges.

So,

$\sum deg(v)=2|E|$

This is always even. Hence, Statement II is true.

Also, in any undirected graph, the number of vertices having odd degree is always even.

Hence, Statement I is also true.

Therefore, both statements are true.

---

Solution

There are $4$ married couples, so total persons are $8$.

You asked $7$ persons, and all gave different answers.

Maximum possible handshakes by one person are $6$ because a person cannot shake hands with himself or herself and cannot shake hands with spouse.

So the $7$ different answers must be:

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

Now, the person who shook $6$ hands must be paired with the person who shook $0$ hands.

Similarly,

$5$ is paired with $1$

$4$ is paired with $2$

The only remaining number is $3$.

So your spouse shook $3$ hands.

Final Answer: $ \boxed{(c)} $

---

Solution

(B) is false (for composite k, both factors are < k). (A), (C), (D) are true for positive integers.

---

Solution

Reason: From (xy)² = xyxy = x²y² = xxyy. Left-multiply by x⁻¹ and right-multiply by y⁻¹ to get yx = xy, hence G is abelian. (2) and (3) are false (there exist non-abelian groups where every element has order 3 or 5, e.g., unitriangular 3×3 matrices over ℤ₃/ℤ₅). (4) is false because every subgroup of an abelian (commutative) group is abelian.

---

Solution

The given graph has $4$ vertices.

Let the vertices be:

$A, B, C, D$

Edges are:

$AB, BC, AD, BD, CD$

So, total edges are $5$.

This graph is like complete graph $K_4$ with one edge missing.

Number of spanning trees in $K_4$ is given by Cayley’s formula:

$4^{4-2}=4^2=16$

In $K_4$, each edge appears in equal number of spanning trees.

Total edge appearances in all spanning trees:

$16 \times 3 = 48$

Because each spanning tree of $4$ vertices has $3$ edges.

Since $K_4$ has $6$ edges, each edge appears in:

$\frac{48}{6}=8$

Now, one edge is missing in the given graph.

So, spanning trees containing that missing edge are removed.

Number of spanning trees:

$16-8=8$

---

Solution

Statement P:

For a connected graph with $n$ vertices, minimum number of edges must be:

$n-1$

Here,

$n=80$

Minimum edges required:

$80-1=79$

But given edges are only $77$.

So, such a connected graph cannot exist.

Therefore, P is true.

Statement Q:

In an Euler graph, every vertex must have even degree.

So, Q is true.

Statement R:

A simple, undirected, connected and acyclic graph is a tree.

Every tree with more than one vertex has at least two vertices of degree $1$.

Here, vertices are $50$.

So, R is true.

Statement S:

Every bipartite graph is $2$-colorable.

A bipartite graph with more than ten vertices can exist.

So, S is true.

Therefore, all four statements are correct.

Number of correct statements:

$4$

---

Solution

Statement P:

For a connected graph with $n$ vertices, minimum number of edges must be:

$n-1$

Here,

$n=80$

Minimum edges required:

$80-1=79$

But given edges are only $77$.

So, such a connected graph cannot exist.

Therefore, P is true.

Statement Q:

In an Euler graph, every vertex must have even degree.

So, Q is true.

Statement R:

A simple, undirected, connected and acyclic graph is a tree.

Every tree with more than one vertex has at least two vertices of degree $1$.

Here, vertices are $50$.

So, R is true.

Statement S:

Every bipartite graph is $2$-colorable.

A bipartite graph with more than ten vertices can exist.

So, S is true.

Therefore, all four statements are correct.

Number of correct statements:

$4$

---

Solution

Statement $1$:

Circuit satisfiability belongs to NP because if an input assignment is given, we can verify in polynomial time whether the circuit output is $1$.

So, statement $1$ is true.

Statement $2$:

Circuit satisfiability is at least as hard as any problem in NP.

So, it is NP-hard.

Therefore, statement $2$ is true.

Statement $3$:

A problem is NP-Complete if it is both in NP and NP-hard.

Circuit satisfiability is a standard NP-Complete problem.

So, statement $3$ is true.

Statement $4$:

The size $\theta(K^2+1)$ is not a general property of the circuit satisfiability problem.

So, statement $4$ is false.

Statement $5$:

This statement is not a basic defining property needed here for Circuit SAT classification.

So, statement $5$ is not selected.

Therefore, correct statements are:

$1,2,3$

---

Solution

Positive odd integers not exceeding $100$ are:

$1,3,5,\ldots,99$

Number of odd integers $=50$

Perfect squares not exceeding $100$ are:

$1^2,2^2,3^2,\ldots,10^2$

Number of perfect squares $=10$

Odd perfect squares are:

$1^2,3^2,5^2,7^2,9^2$

Number of odd perfect squares $=5$

Required number:

$50+10-5=55$

---

Solution

---

Solution

Books are identical and boxes are also identical.

So, we need to find the number of partitions of $6$ into at most $4$ parts.

Possible distributions are:

$6$

$5+1$

$4+2$

$4+1+1$

$3+3$

$3+2+1$

$3+1+1+1$

$2+2+2$

$2+2+1+1$

Total ways $=9$

---

Solution

Check option (a):

$(p\to r)\land(q\to r)$

$=(\neg p\lor r)\land(\neg q\lor r)$

$=(\neg p\land\neg q)\lor r$

$=\neg(p\lor q)\lor r$

$=(p\lor q)\to r$

So, option (a) is logically equivalent.

Option (b) is also equivalent because if $p$ and $q$ have same truth value, then $\neg p$ and $\neg q$ also have same truth value.

Option (c) is the standard form of biconditional:

$p\leftrightarrow q\equiv(p\land q)\lor(\neg p\land\neg q)$

So, option (c) is logically equivalent.

Now check option (d):

$((p\land q)\to r)=\neg(p\land q)\lor r=\neg p\lor\neg q\lor r$

But,

$(p\to r)\land(q\to r)=(\neg p\lor r)\land(\neg q\lor r)$

Both are not always same.

---

Solution

Solution: $R=\{x:x\in N,\ x\text{ is multiple of }3,\ x\le 100\}$ $S=\{x:x\in N,\ x\text{ is multiple of }5,\ x<100\}$ $R\cap S$ contains numbers which are multiples of both $3$ and $5$. So, $R\cap S$ contains multiples of $15$. Multiples of $15$ less than $100$ are: $15,30,45,60,75,90$ So, $|R\cap S|=6$ Also, $S\cap R=R\cap S$ Therefore, $|(R\cap S)\times(S\cap R)|=6\times6=36$ So, the correct answer is $36$.

---

Solution

Planar Graph:

According to the four color theorem, every planar graph is $4$-colorable.

So,

a → III

Bipartite Graph:

A bipartite graph can be colored using $2$ colors.

So,

b → IV

PERT:

PERT is used when activity time is uncertain. Hence, it is a probabilistic model.

So,

c → I

CPM:

CPM is used when activity time is fixed and known. Hence, it is a deterministic model.

So,

d → II

Correct matching:

a-III; b-IV; c-I; d-II

---

Solution

Digits are 1, 2, 4 and 6.

Sum of digits:

1 + 2 + 4 + 6 = 13

Total four digit numbers formed using all four digits:

4! = 24

Each digit appears 6 times at each place.

So, required sum:

6 × 13 × 1111 = 86658

---

Solution

$ad(b+c)=bc(a+d)$

Dividing both sides by $abcd$,

$\frac{b+c}{bc}=\frac{a+d}{ad}$

$\frac{1}{b}+\frac{1}{c}=\frac{1}{a}+\frac{1}{d}$

Rearranging,

$\frac{1}{a}-\frac{1}{b}=\frac{1}{c}-\frac{1}{d}$

So, relation R is based on equality of the same expression.

Therefore, R is reflexive, symmetric and transitive.

---

Solution

Statement I:

Integer Linear Programming is a hard problem because variables are restricted to integer values.

General Integer Linear Programming is considered NP-hard.

So, it is not solved by a general polynomial time algorithm.

Therefore, statement I is true.

Statement II:

PERT stands for Program Evaluation and Review Technique.

PERT is mainly used for project scheduling when activity times are uncertain.

Its main focus is time estimation and completing the project in minimum possible time.

Therefore, statement II is true.

So,

I is True and II is True.

---

Solution

---

Solution

We need shortest path from 1 to 100 using operations:

$i \to i+1$ or $i \to 3i$

A shortest path is:

$1 \to 3 \to 9 \to 10 \to 11 \to 33 \to 99 \to 100$

Number of edges $=7$

---

Solution

---

Solution

Each time an a is read:

$a \rightarrow$ push 3 a's onto the stack.

Each b pops one a from the stack.

Thus:

1 input a produces 3 stack symbols, so we need 3 b's to remove them.

Therefore the relation is:

$b = 3a$

Language:

${a^n b^{3n} \mid n>0}$