Your Answer : (Not Answered)

Correct Answer : A

There are 6660 such words.

Words of length 5 with no repeated letter from 8 letters:

\[ P(8, 5) = 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 = 6720 \]

Words containing 'bad': treat 'bad' as one block, then choose 2 more distinct letters from the remaining 5 and arrange the block with them.

\[ \begin{aligned} \binom{5}{2} \times 3! &= 10 \times 6 = 60 \\ 6720 - 60 &= 6660 \end{aligned} \]

The other figures do not follow from this count: subtracting the 60 forbidden words is the only correction needed, since 'bad' cannot occur twice in five distinct letters.

Your Answer : (Not Answered)

Correct Answer : C

4 code words are possible.

A generator matrix with k rows produces every linear combination of its rows over GF(2), so a code with k independent rows has \(2^{k}\) code words. Here G has 2 independent rows of length 3:

\[ \begin{aligned} 0 \cdot r_1 + 0 \cdot r_2 &= 000 \\ r_1 &= 110 \\ r_2 &= 011 \\ r_1 + r_2 &= 101 \end{aligned} \]

That gives \(2^{2} = 4\) code words. 8 would be \(2^{3}\), every 3-bit word, which would need three independent rows. 1 and 2 forget either the all-zero word or the sum of the two rows, both of which are always in a linear code.

Your Answer : (Not Answered)

Correct Answer : C

The shortest path from A to I has weight 42.

Reading the weights from the figure, the cheap edges near A are A-C (9), A-D (12) and C-D (4), and D connects straight to I with weight 30. Running Dijkstra's algorithm from A:

• A = 0; then C = 9, D = 12 (A-C-D would be 13), B = 22.
• From D: I = 12 + 30 = 42 and E = 12 + 33 = 45.
• Every other route to I is longer: through H it is at least 22 + 34 + 19 = 75, and through G at least 45 + 23 + 21 = 89.

\[ \begin{aligned} d(A,I) &= w(A,D) + w(D,I) \\ &= 12 + 30 = 42 \end{aligned} \]

43 is the path A-C-D-I, \(9 + 4 + 30\), which looks attractive because it starts with the cheapest edge but ends one unit heavier. 2 and 3 count edges rather than adding weights: A-D-I has two edges.

Your Answer : (Not Answered)

Correct Answer : C

Such a graph exists for \(a = 2, b = 3, c = 4\).

Whitney's inequality says that for every graph, vertex connectivity \(\le\) edge connectivity \(\le\) minimum degree, i.e. \(a \le b \le c\). Moreover, Chartrand and Harary showed that every triple of positive integers with \(a \le b \le c\) is realised by some graph.

Only option C satisfies \(2 \le 3 \le 4\). Option A has \(a = 4 \gt b = 2\), option B has \(a = 4 \gt b = 3\), and option D has \(b = 4 \gt c = 3\), each violating Whitney's inequality.

Your Answer : (Not Answered)

Correct Answer : B

The incidence matrix is 9×18.

A node (vertex)-edge incidence matrix has one row for each vertex and one column for each edge; entry (i, j) is 1 when vertex i is an end of edge j. The graph has 9 vertices (A to I) and 18 edges (e1 to e18), so the matrix is 9 rows by 18 columns. Each column holds exactly two 1s, because every edge of an undirected graph has two ends.

18×9 is the transpose, an edge-vertex arrangement. 9×9 is the size of the adjacency matrix, and 18×18 matches nothing. The weight set W does not affect the order of the matrix.

Your Answer : (Not Answered)

Correct Answer : C

The answer is (I) if and only if (II).

If L is a chain and \(a \wedge b \in I\) for an ideal I, then \(a \wedge b\) is the smaller of \(a\) and \(b\), so one of them lies in I: every ideal is prime.

Conversely, suppose every ideal is prime but \(a\) and \(b\) are incomparable. The principal ideal \((a \wedge b]\) contains \(a \wedge b\), so being prime it contains \(a\) or \(b\). If it contains \(a\), then \(a \le a \wedge b \le b\), contradicting incomparability; similarly for \(b\). So L is a chain. Each condition implies the other.

Your Answer : (Not Answered)

Correct Answer : C

Neither (I) nor (II) is true.

Not every distributive lattice is complemented: the three-element chain \(0 \lt a \lt 1\) is distributive, but \(a\) has no complement (no \(b\) with \(a \wedge b = 0\) and \(a \vee b = 1\)). Distributivity only guarantees that complements are unique when they exist.

The same chain is modular, so (II) fails for the same reason. Modularity does not even give uniqueness: in the diamond \(M_{3}\) each atom has two complements.

Your Answer : (Not Answered)

Correct Answer : C

The cart holds 21 units.

The person takes 1 unit of the first item, 2 of the second, and so on up to r units of the rth, so the total for n items is the sum of the first n natural numbers:

\[ \begin{aligned} 1 + 2 + \dots + n &= \frac{n(n+1)}{2} \\ &= \frac{6 \times 7}{2} = 21 \end{aligned} \]

6 counts only the items, not the units. 42 is \(n(n+1)\), forgetting to halve, and 14 matches no step of the sum.

Your Answer : (Not Answered)

Correct Answer : C

The basic operations on sets are union, intersection, difference and subset.

A set abstract data type is defined by the operations of set theory: union (elements in either set), intersection (elements in both), difference (elements in one but not the other) and the subset test, along with membership.

Push and pop are stack operations. Insert and delete belong to many structures (lists, trees) and do not define a set. Traversing and merging are general operations on lists and files, not the defining operations of sets.

Your Answer : (Not Answered)

Correct Answer : D

The code can correct 0 errors.

The code words are all sums (mod 2) of the rows of G: 000, 110, 011 and 110 + 011 = 101.

\[ \begin{aligned} d_{min} &= \text{least non-zero weight} = 2 \\ t &= \lfloor (d_{min} - 1)/2 \rfloor = \lfloor 1/2 \rfloor = 0 \end{aligned} \]

With a minimum distance of 2 the code can detect a single error but cannot correct any, because a received word one bit away from two code words is equally close to both. Correcting one error would need a minimum distance of at least 3, so 1, 2 and 3 are all too high.

Your Answer : (Not Answered)

Correct Answer : C

The false statement is G cannot be planar for any value of V and E.

The complete graphs \(K_{1}\) to \(K_{4}\) are all planar: \(K_{4}\) can be drawn as a triangle with a vertex in the middle joined to the three corners, with no edges crossing. Only from \(K_{5}\) onwards is a complete graph non-planar, by Kuratowski's theorem, so the statement fails for small V.

The other statements are true. A complete graph on V vertices needs exactly V colours, since every vertex is adjacent to every other, so it is V-colourable. Each pair of vertices is joined by one edge, giving \(E = V(V-1)/2\). And every vertex is adjacent to every other, so the graph is always connected.

Your Answer : (Not Answered)

Correct Answer : A

The property that holds is The diagonal entries of \(A^{2}\) are the degrees of the vertices of the graph.

\((A^{2})_{ii} = \sum_{j} a_{ij} a_{ji} = \sum_{j} a_{ij}^{2} = \sum_{j} a_{ij}\), since \(A\) is symmetric with entries 0 or 1. That sum counts the neighbours of vertex \(i\), which is its degree.

The others fail. For the path on three vertices u - v - w (\(n = 3\)), the graph is connected, but \(A^{2} + I_{3}\) has a 0 in position (u, v): there is no walk of length exactly 2 from u to v, because the graph is bipartite. A triangle plus one isolated vertex has \(n = 4\) and its entries sum to \(6 = 2(n-1)\), yet it has a cycle. Two disjoint edges on four vertices put a 1 in every row and column, but the graph is not connected.

Your Answer : (Not Answered)

Correct Answer : D

The formula that is NOT valid is ∀x (p(x) ∨ q(x)) ⇒ (∀x p(x) ∨ ∀x q(x)).

Counterexample: let the domain be the integers, \(p(x)\) = “x is even” and \(q(x)\) = “x is odd”. Every integer is even or odd, so the left side is true, but neither “all integers are even” nor “all are odd” is true.

The others are valid. (A): if \(\forall x\,p(x)\) fails then \(\exists x\neg p(x)\) holds, and if it holds then the premise gives \(\forall x\,q(x)\). (B): an existential distributes over disjunction, so the two sides are equivalent. (C): a witness of \(p \land q\) is a witness for each separately.

Your Answer : (Not Answered)

Correct Answer : D

The true statement is In each cycle \(C\) in \(G\), either all edges in \(C\) have even weight OR all edges in \(C\) have odd weight.

Suppose a cycle had an even edge e and an odd edge f. Take a spanning tree that contains e but not f (start from the cycle minus f and extend it). Removing e splits the tree into two parts, and f, lying on the same cycle, reconnects them, so swapping e for f gives another spanning tree whose weight differs by an odd amount. Both trees cannot be even, a contradiction. So the edges of every cycle share one parity.

The other statements fail on examples. A path of two edges of weight 1 has only one spanning tree, of weight 2, so edges need not be even, and a cycle of odd edges does the same. A triangle of odd edges with a pendant edge of weight 2 has every spanning tree of even weight, yet its edges are neither all even nor all odd.

Your Answer : (Not Answered)

Correct Answer : B

For all graphs, \(d_{1}(u, v) \le d_{2}(u, v)\).

The minimum spanning tree T is a subgraph of G, so the unique path between u and v in T is also a path in G. The shortest path in G can only be as short as that path or shorter, so \(d_{1} \le d_{2}\).

Equality need not hold, because an MST minimises total weight, not individual distances. In a triangle with edges u-v of weight 3 and u-w, w-v of weight 2 each, the MST keeps the two edges of weight 2, so \(d_{2}(u, v) = 4\) while \(d_{1}(u, v) = 3\). That example rules out '=' and '\(\ge\)', and the case where u and v are joined by an MST edge rules out '\(\ne\)'.

Your Answer : (Not Answered)

Correct Answer : B

Only statement II is true, so the answer is II only.

II is true (the cycle property): if \(e\) is the heaviest edge on some cycle, then in any spanning tree containing \(e\), removing \(e\) and adding another edge of that cycle reconnects the tree with smaller total weight. So no MST contains \(e\).

I is false. Being the lightest edge of some cycle does not force an edge into the MST. Take vertices A, B, C, D with edges AC = 1, BC = 2, AB = 3, AD = 4 and BD = 5. AB is the lightest edge of the cycle A-B-D (3, 4, 5), yet it is the heaviest edge of the triangle A-B-C, so by the cycle property no MST contains it; the MST is AC, BC, AD. So only II holds.

Your Answer : (Not Answered)

Correct Answer : A

The answer is P only.

P is true. Every spanning tree has exactly \(|V| - 1\) edges, so adding the same constant to every edge raises every tree's total by the same amount. The order of trees by weight is unchanged, and so is the minimum spanning tree. (Kruskal's algorithm also sees the same order of edges.)

Q is false. Paths have different numbers of edges, so the increase depends on path length. For example, a direct edge of weight 6 against a two-edge path of weights 2 + 3: before, the two-edge path (5) is shorter; after adding 2 to each edge, it costs 9 while the direct edge costs 8. Paths with more edges are penalized more.

Your Answer : (Not Answered)

Correct Answer : A

The closed form is \(\frac{x(1 + x^{2})}{(1 - x^{2})^{2}} + \frac{1}{1 - x}\).

Write \(a_{n} = 1 + b_{n}\), where \(b_{n} = n\) for odd \(n\) and 0 otherwise. The constant part gives \(\sum x^{n} = \frac{1}{1-x}\). For the odd part, start from \(g(x) = \sum n x^{n} = \frac{x}{(1-x)^{2}}\) and keep only the odd powers with \(\frac{g(x) - g(-x)}{2}\):

\[ \begin{aligned} \sum_{n \text{ odd}} n x^{n} &= \frac{1}{2}\left[\frac{x}{(1-x)^{2}} + \frac{x}{(1+x)^{2}}\right] \\ &= \frac{x\left[(1+x)^{2} + (1-x)^{2}\right]}{2(1-x^{2})^{2}} \\ &= \frac{x(1 + x^{2})}{(1 - x^{2})^{2}} \end{aligned} \]

Check the first terms: the sequence is 1, 2, 1, 4, 1, 6, ..., and \(\frac{x(1+x^{2})}{(1-x^{2})^{2}} = x + 3x^{3} + 5x^{5} + \cdots\), which added to \(1 + x + x^{2} + \cdots\) gives exactly that. The other numerators fail on these terms: \(x(3 - x^{2})\) and \(2x\) give 3 and 2 as the coefficient of \(x\) instead of 1, and \(x\) gives 2 as the coefficient of \(x^{3}\) instead of 3.

Your Answer : (Not Answered)

Correct Answer : A

The true statement is \(T(n) = \Theta(2^{n})\).

The characteristic equation of \(T(n) = 5T(n-1) - 6T(n-2)\) is \(r^{2} - 5r + 6 = 0\), with roots 2 and 3, so \(T(n) = a2^{n} + b3^{n}\). The initial values fix the constants:

\[ \begin{aligned} T(0) &= a + b = 1 \\ T(1) &= 2a + 3b = 2 \\ \Rightarrow b &= 0, \quad a = 1 \end{aligned} \]

So \(T(n) = 2^{n}\) exactly (check: \(T(2) = 10 - 6 = 4\)). The \(3^{n}\) term would normally dominate, which is the trap, but these initial conditions make its coefficient zero. The \(n2^{n}\) and \(n3^{n}\) forms arise only from a repeated root, which this equation does not have.

Your Answer : (Not Answered)

Correct Answer : A

The expression has 12 terms. In the binomial expansion of \((a+b)^{n}\) there are \(n+1\) terms, because the power of \(a\) runs from \(n\) down to 0, which gives \(n+1\) different values. Here \(a = x^{2}\), \(b = \frac{2}{x}\) and \(n = 11\), so \[ \text{number of terms} = 11 + 1 = 12 \] The number 11 is the power and not the count of terms, while 22 and 24 come from doubling the power or the count, which does not follow from the binomial theorem.