৪৯তম বিসিএস ⎯ কম্পিউটার সায়েন্স (CSE) [৯৭১]

Answer: c)
Explanation:
    A proposition is a declarative sentence that can only have a truth value: True (T) or False (F).
    Example: “2 + 3 = 5” → True, “2 + 2 = 5” → False.

Some examples of Propositions:

"Man is Mortal", it returns truth value TRUE
"13 + 8 = 3 2", it returns truth value FALSE
The following is not a Proposition −
"X is less than 2". It is because unless we give a specific value of X, we cannot say whether the statement is true or false

 Answer: b)
Explanation:
    Negation flips the truth value.
    If p = True → ¬p = False; if p = False → ¬p = True.
Other options:
   a) original statement, not negation.
   c) Uncertain → not logical negation.
   d) Not exact logical negation.

 Answer: b)
Explanation:
    Conjunction (AND) is True only if both components are True.
 Truth table:
    T ∧ T = T
    T ∧ F = F
    F ∧ T = F
    F ∧ F = F

Other options:
    a) That’s disjunction (OR).
    c) Both false → AND = F.
    d) Only one true → AND = F.

 Answer: a)
Explanation:
    Tautology = compound statement that is true in all cases.
    Example: p ∨ ¬p → always true.

Other options:
    b) Always false → contradiction, not tautology.
    c) Sometimes true → contingency.
    d) Undecidable → not applicable here.

Answer: b)
Explanation:
    ∀ = “for all” → P(x) must be true for every element in domain.

Other options:
    a) That’s existential quantifier ∃.
    c) Negation.
    d) Not precise.

Answer: b)

Explanation:
“All humans are mortal” → For every individual, if that individual is a human, then they are mortal.

In logic terms, we are stating something about all members of the domain, so we use the universal quantifier ∀.

Predicate representation:
Let Human(x) represent “x is a human”.

Let Mortal(x) represent “x is mortal”.

Logical form: ∀x(Human(x)→Mortal(x)) Read as: “For all x, if x is a human, then x is mortal.”

Why implication (→) is used:
Only humans need to be mortal; non-humans don’t matter.

So we write “if x is human then x is mortal”.

Other options:
a) Existential quantifier → only one human mortal, incorrect.

b) Wrong direction of implication.

d) Doesn’t capture "all".

 Answer: a) “Some birds cannot fly”

 Explanation:

Original statement: “All birds can fly”

In predicate logic: ∀x(Bird(x)→CanFly(x)) - This says: for every bird x, x can fly.
Negation in logic: The negation of a universally quantified statement (∀xP(x)) is: ¬(∀xP(x))≡∃x¬P(x)

Meaning: “It is not true that all birds can fly” → “There exists at least one bird that cannot fly.”

Apply to our statement:

Original: ∀x (Bird(x) → CanFly(x))

Negation: ∃x ¬(Bird(x) → CanFly(x))

Simplify the implication:

Recall:  A→B≡¬A∨B 
          So ¬(A → B) ≡ ¬(¬A ∨ B) ≡ A ∧ ¬B (applying De morgan law)

Apply to our statement: ¬(Bird(x) → CanFly(x)) ≡ Bird(x) ∧ ¬CanFly(x)

This means: “x is a bird AND x cannot fly.”

“There exists at least one x such that x is a bird and x cannot fly.”

In plain English: “Some birds cannot fly.” 

Other options:

b) “No bird can fly” -This is much stronger → states every bird cannot fly. Negation only requires at least one bird cannot fly, not all.

c) “All birds cannot fly” -Same as b) → universal negative, not correct negation.

d) “Some birds can fly” This does not negate “all birds can fly.”

Answer: (d) Set is both Non-empty and Finite

Explanation:
The integer that is neither positive nor negative is 0. If the set contains such an integer, then it contains at least one element (0), so it is non-empty. And since it contains a specific integer (or a finite number of such integers), the set is finite. So both properties apply.

Others option:

(a) Empty set: Wrong, because the set contains at least one element (0).

(b) Non-empty: Partially correct, but incomplete because we must also note finiteness.

(c) Finite: Also partially correct, but incomplete because non-emptiness is ignored.

Answer: (a) Infinite set

Why (a) is correct:
The set {x ∈ N : x is prime} is the set of all prime numbers. The set of primes is well-known to be infinite 

Others option:

(b) Finite set: Wrong, because there are infinitely many primes (no largest prime).

(c) Empty set: Wrong, because the set of primes definitely contains elements (e.g., 2, 3, 5, …).

(d) Not a set: Wrong, because by definition {x ∈ N : x is prime} is a well-defined mathematical set.

Answer: (d) All of the mentioned
A set B is a subset of A if every element of B is also an element of A.

{1,2} ⊆ {1,2,3,4}

{1,2,3} ⊆ {1,2,3,4}

{1} ⊆ {1,2,3,4}
So all three options are valid subsets.

Answer: a) One

Empty set (∅): A set that contains no elements.

Example: ∅ = {}

Power set (P(S)): The set of all subsets of a set S.

If a set has n elements,
then the power set has 2ⁿ subsets.

In empty Set, n=0 elements.

Formula: Number of subsets =2ⁿ =2⁰=1
So, the power set of ∅ = { ∅ }

Answer: c) 8
Cardinality → the number of elements in a set.

Example: |{2,4,6}| = 3

Power set (P(S)) → the set of all subsets of a set S.

If a set has n elements, its power set has 2ⁿ elements (subsets).

Apply to given set

Set given: {1, 5, 6}

Number of elements in S = 3

Formula: ∣P(S)∣=2ⁿ=2³=8

So, the power set has 8 subsets.

Answer: b)  ∅

Explanation:

Complement of a set A = elements of U not in A.

So, complement of entire universe U = U-U =∅ = empty set

 Answer: a) A

Explanation:

If A is inside B, then common elements = A.

Other options:

b) Only if A = B.

c) That equals B, not A.

d) False unless A is ∅

 Answer: c)
Explanation:
    Symmetric: whenever (a, b) exists, its reverse (b, a) must also exist.
   
Other options:
   b) Transitive property.
   c) Reflexive property.
   d) Wrong

Answer: b)
Explanation:
    Reflexive requires all (a, a).
   For {1,2,3}, must have (1,1), (2,2), (3,3).
    Option (b) is missing (3,3), so not reflexive.

Answer: b)
Explanation:
    Symmetric means order doesn’t matter: if a is related to b, then b is related to a.
Other options:
    a) Wrong, not symmetric definition.
    c) This is transitive definition.
    d) Wrong, (b) is correct.

Answer: a)
Explanation:
    A function maps each element of domain A to exactly one element in codomain B.
    Example: f(x) = x² maps every real number x to exactly one square value.
Other options:
    a) “At most one” → could allow no mapping, which is invalid.
    c) Wrong: not every B must be mapped.
    d) Arbitrary relation does not guarantee function properties

Answer: a)
Explanation:
    Injective: no two distinct inputs give the same output.
    Example: f(x)=2x is injective.


Other options:
    b) That’s surjective.
    c) That would mean constant function.
    d) Wrong.

Answer: c)  

Mathematical induction is a proof technique used to prove that a statement P(n) is true for all natural numbers n∈N.

Idea:
If something is true for the first natural number (usually n=1), and if whenever it’s true for some n=k,
it’s also true for n=k+1, then it must be true for all natural numbers.

Steps:

Base Case: Show that the statement is true for the first natural number (often n=1).

Inductive Hypothesis: Assume the statement is true for n=k.

Inductive Step: Prove that if it’s true for n=k, then it’s true for n=k+1. n∈N.

Mathematical induction applies specifically to natural numbers because: Natural numbers are well-ordered (every non-empty subset has a least element).

They are discrete and successive (each has a "next" number).

Induction relies on moving step by step from 1 → 2 → 3.

 Answer: d)

Steps of induction:
1.    Base case
2.    Assume statement true for n=k (hypothesis)
3.    Prove for n=k+1 (inductive step)
d) Proof by contradiction is different proof technique, not part of induction.

Answer: c)
Explanation:
    By induction principle → truth propagates forward from base case → true for all natural numbers n ≥ 1.
Wrong options:
    a) Not “some”, but all.
    b) Odd only → false.
    d) Even only → false.

 Answer: c)
Explanation:
    A graph G= (V, E) consists of a set of vertices (nodes) and set of edges (connections).
    Example: Social network → users = vertices, friendships = edges.
Wrong options:
    a) Only vertices → incomplete.
    b) Only edges → meaningless without vertices.
    d) Graphs can have cycles, but not all are trees.

 Answer: c)
Explanation:
    Tree = connected + acyclic graph.
    Example: Computer file system.

Wrong options:
    a) Trivial, not valid.
    b) A single vertex without edges is a trivial tree, but general definition = connected + no cycles.
    d) Trees have minimum edges, not maximum.

Answer: a)
Explanation:
    Recurrence relation expresses each term in terms of previous terms.
    Example: Fibonacci sequence: F(n) = F(n-1) + F(n-2).

 Wrong options:
    b) Sum formula → not recurrence.
    c) Graph generation → unrelated.

Answer b)
Types of Recurrence Relations

Linear Homogeneous Recurrence Relation

General form: a_n=c₁a_n−1+c₂a_n−2+⋯+ c_nk_n−k
​Only involves previous terms, no extra “free” terms.
Example: a_n=3a_n−1−2a_n−2.
Linear Non-Homogeneous Recurrence Relation

General form: a_n=c₁a_n−1+c₂a_n−2+⋯+ c_ka_n−k+ f(n)

Same as homogeneous, but with an extra function f(n) (non-zero).
Example: a_n=2a_n−1+n.

Nonlinear Recurrence Relation

If the terms involve powers, products, or non-linear functions of a_n−1, a_n−2, ….
Example: an= (a_n−1)²+3.

Quadratic Recurrence Relation
A special kind of nonlinear relation where terms involve squares, e.g., a_n=(a_n−1)²
 
Analyze the Given Recurrence:  a_n = 2a_n-1 +n
The recurrence involves only the first previous term (a_n−1).

Coefficient of a_n−1 is 2 (linear dependence).

There is an extra term +n.

This is an explicit function of n.

This makes it non-homogeneous.

Wrong options:

a) Homogeneous → RHS must be 0.
c) Nonlinear → depends on powers/products of a_(n-1).
d) Quadratic → no quadratic term in given equation like (an−1​)² or n²

Answer: b)
Explanation:
    Generating function G(x) = a₀ + a₁ x + a₂ x² + …
    Encodes sequence into a power series, useful for combinatorial analysis.
Wrong options:
    a) Polynomial = finite, generating function may be infinite series.
    c) Recurrence = formula, not function.
    d) Sum = only part of series.

Answer: b)
Explanation:
Classic Fibonacci sequence:
F(0) = 0, F(1) = 1, 
F(n) = F(n-1) + F(n-2), n ≥ 2.
Sequence: 0,1,1,2,3,5,8,13,21, …

So the correct definition is addition of the two previous terms
Wrong options:
    a) Product → not Fibonacci.
    c) n² → simple formula, not recurrence.
    d) n! → factorial, not recurrence.

Answer: b)

Explanation:

Gaussian elimination reduces a system of linear equations to row echelon form for solving.

Wrong options:

(a) Differential eqns use other methods (Euler, Runge-Kutta).

(c) Quadratic eqns solved by quadratic formula.

(d) Non-linear equs need iteration (Newton-Raphson).

Answer: c) 

Explanation:

Forward elimination → eliminate coefficients below pivot.

Back substitution comes later.

Answer: d)
Newton–Raphson Method:

Iterative root-finding method for nonlinear equations.

Formula: x_n+1 =x_n−f( x_n) / f′(x_n)
 ​Starts with an initial guess x₀ and improves it step by step until convergence.

a) Gaussian elimination→ → Direct method → reduces the matrix to row echelon form in finite steps. No repeated approximation involved.

b) Gauss–Jordan → → Direct method → reduces augmented matrix to reduced row echelon form.

Provides solution directly, no iteration required.

c) Cramer’s rule→ →   Direct method → uses determinants to solve linear systems→ Finite calculation, no iteration.

Newton–Raphson Method:

Iterative root-finding method for nonlinear equations.

Formula: x_n+1 =x_n−f( x_n) / f′(x_n)
 ​Starts with an initial guess x₀ and improves it step by step until convergence.

Answer: b)
Explanation:
The degree of a polynomial is determined by the highest power of the variable present in the expression.
In the given polynomial, f(x) = 2x³ - 5x² + 7x + 6 
The powers of (x) in these terms are 3, 2, 1, and 0 (for the constant term (6), which can be written as ( 6x^0 )), respectively. The highest among these powers is 3, making the degree of the polynomial three

Answer: a) Values of argument
Explanation:

 Polynomial Interpolation: Polynomial interpolation is a numerical method used to construct a polynomial P(x) that passes exactly through a set of given data points (x₀, y_{0), (}x₁, y₁), ..., (x_n, y_n).

Once the polynomial is constructed, it can be used to estimate or compute the value of the function at any point 
x within the data range.

Purpose: 
Compute values of the argument: P(x)≈f(x) for any x within the range of known points.

This is especially useful when the exact functional form of f(x) is unknown, but discrete data points are available.

Other options:

b) Integration →→Integration can be approximated using formulas like Trapezoidal or Simpson’s rule, sometimes using interpolated values, but interpolation itself is not directly for integration.

c) Differentiation →→Numerical differentiation can also use polynomial derivatives, but interpolation’s main goal is to find function values, not derivatives.

d) None of the above  →answer a)

 Answer: b) h²
Explanation:

Option Analysis:
a) h→ first-order methods (like Euler’s method) have error ∝ h.
c) h³ → Simpson’s 1/3rd rule has error ∝ h⁴ (fourth-order accurate).
d) h⁴ → too high for Trapezoidal Rule, applies to Simpson’s 1/3rd rule.

Answer: c
Explanation:
2x – y + 3z = 9 ……….(i)
x + y + z = 6 ……………………(ii)
x – y + z = 2 ……………………(iii)
To eliminate x, operate (ii) – (iii)
y = 4
Now, operate (i) – 2(ii),
-3y + z = 3
Now by back substitution,
z = 15
x + 4 +15 = 6
X = -13.

Answer: c)  f'(x)= 0 
Newton–Raphson Formula: x_n+1 =x_n−f( x_n) / f′(x_n)

This formula updates an approximation x_n to a better estimate x_n+1 of the root.

Derivative f′(x_n) is in the denominator

When the Method Fails:
If f′(x_n​)=0:

x_n+1=x_n−f(xn)/0→ division by zero!
This is undefined → Newton–Raphson fails.

Answer: b) Numerical differentiation
 Explanation:

Numerical differentiation is the process of approximating derivatives of functions using discrete data points.

If instead we approximate integrals, it’s called numerical integration (or quadrature).

Explanation:
When we approximate integrals using values of , it’s called Numerical Integration (also called Quadrature).

Correct Answer: c) Numerical integration

Correct Answer: d) Multiple of 3
Explanation:

 Answer: a) Trapezoidal rule
Explain:

Romberg’s method is a numerical integration technique that improves the accuracy of integral approximation using extrapolation. It is based on the Trapezoidal rule.

The key idea: Compute trapezoidal approximations for different step sizes and then use Richardson extrapolation to improve accuracy.
It generates a triangular table of values R(i, j) where each new value refines the previous approximation

Answer: a) Solve normal equations 

Other options :

b) Trapezoidal rule is for numerical integration, not solving linear equations or fitting lines.

  Least squares doesn’t require integration; it requires solving algebraic equations.

c) Euler’s method is a numerical method for solving differential equations.

Least squares fitting involves algebraic minimization, not differential equations.

d) Gaussian elimination only can be used to solve the normal equations once they are formed.

But forming the normal equations is the essential step in least squares.

Answer: b) Reduced row echelon form 
 Gauss–Jordan Method:
Gauss–Jordan elimination is an extension of Gaussian elimination.

Objective: Solve a system of linear equations Ax=b
Key steps:
Convert the augmented matrix [A∣b] into row echelon form (like Gaussian elimination).
Continue eliminating above and below each pivot to transform it into Reduced Row Echelon Form (RREF).
In RREF: Each pivot element = 1
All other entries in the pivot column = 0
Leading 1s appear to the right as you move down the rows
This allows direct reading of the solution from the final matrix. 
Other options:
a) Upper triangular matrix appears in Gaussian elimination, not Gauss–Jordan.
c) Lower triangular has zeros above the diagonal, used in LU decomposition sometimes.
Gauss–Jordan does not produce a lower triangular matrix.
d) Singular means determinant = 0, i.e., no unique solution.
Gauss–Jordan can work with singular or non-singular matrices, but the final form is not necessarily singular.
This option is irrelevant to the method itself.
 
Step 3: Key Insight

Answer: a)

Explanation:

(a) Correct → Least squares helps when data has noise/errors.

(b), (c), (d) Wrong → no need of approximation in exact or no-data cases.

Answer: a) 
Explanation:

Polynomial degree determines the type of curve:

Degree 1 → straight line
Degree 2 → parabola
Degree 3 → cubic curve
Higher degrees → more complex curves
Least squares degree 1 → linear regression → straight line.

Answer: b)

Explanation: Runge–Kutta 4th order method 

(b) Correct → RK4 is widely used due to good accuracy with reasonable computation.

Answer: c)
Explanation:

 a) Find exact solution always
False, numerical methods do not give exact solutions, only approximations.

b) Eliminate differential equations 
False. We don’t eliminate ODEs, we approximate their solution.

c) Approximate solution when exact solution is difficult
Correct. This is the main purpose of numerical methods for ODEs.

d) Solve algebraic equations 

False. ODE numerical methods deal with differential equations, not general algebraic equations (unless the ODE is discretized into algebraic form).