CSC165 · TU past paper

Discrete Structures 2079 question paper

The complete TU 2079 exam paper for Discrete Structures (CSC165), all 12 questions with solved model answers written to the mark scheme.

Past Papers2081 2080.1 2080 2079 2078 2076 2075

Tap a question to open its answer.

110 marksNumericalInjective and Bijective FunctionsHideAnswer
How do you plot the function on graph? Determine whether the function $f(x) = x^2$ is injective, surjective or bijective with reasons. Solve the recurrence relation $a_n = 6a_{n-1} + 9a_{n-2}$ with initial conditions $a_0 = 1, a_1 = 6$ . [10]
How do you plot the function on graph? Determine whether the function $f(x) = x^2$ is injective, surjective or bijective with reasons. Solve the recurrence relation $a_n = 6a_{n-1} + 9a_{n-2}$ with initial conditions $a_0 = 1, a_1 = 6$. [10]
Function: $f(x) = x^2$ (domain and codomain taken as $\mathbb{R} \to \mathbb{R}$ ) - Recurrence: $an = 6a{n-1} + 9a{n-2}$ - Initial conditions: $a0 = 1$ , $a1 = 6$ --- Steps: 1. Choose several $x$ -values from the domain. 2. Compute

Function: $f(x) = x^2$ (domain and codomain taken as $\mathbb{R} \to \mathbb{R}$) - Recurrence: $an = 6a{n-1} + 9a{n-2}$ - Initial conditions: $a0 = 1$, $a1 = 6$ --- Steps: 1. Choose several $x$-values from the domain. 2. Compute
210 marksNumericalmathematical InductionHideAnswer
A group of 8 scientist is composed of 5 chemist and 3 biologist. In how many ways can a committee of 5 be formed that has 3 chemist and 2 biologist? Using mathematical induction prove that $1^3 + 2^3 + 3^3 + ... + n^3 = (n^2(n+1)^2/4)$ for $n \geq 1$ . [10]
A group of 8 scientist is composed of 5 chemist and 3 biologist. In how many ways can a committee of 5 be formed that has 3 chemist and 2 biologist? Using mathematical induction prove that $1^3 + 2^3 + 3^3 + ... + n^3 = (n^2(n+1)^2/4)$ for $n \geq 1$. [10]
Answer

Part 1: Committee Formation

Given Data
- Total scientists = 8 (5 chemists + 3 biologists)
- Committee required = 5 members: exactly 3 chemists and 2 biologists
Solution

Select 3 chemists from 5: $C(5,3) = \frac{5!}{3!\,2!} = \frac{5\times 4}{2\times 1} = 10$

Select 2 biologists from 3: $C(3,2) = \frac{3!}{2!\,1!} = 3$

By the multiplication principle: $\text{Total} = C(5,3)\times C(3,2) = 10 \times 3 = \boxed{30 \text{ ways}}$

Part 2: Proof by Mathematical Induction

Claim: $1^3 + 2^3 + \cdots + n^3 = \frac{n^2(n+1)^2}{4}, \quad n \geq 1$

Base Case (n = 1)
- LHS $= 1^3 = 1$
- RHS $= \dfrac{1^2 \cdot 2^2}{4} = \dfrac{4}{4} = 1$
LHS = RHS, so the statement holds for $n = 1$ . ✓

Inductive Hypothesis

Assume true for $n = k$ : $1^3 + 2^3 + \cdots + k^3 = \frac{k^2(k+1)^2}{4}$

Inductive Step

Show true for $n = k+1$ : $1^3 + \cdots + k^3 + (k+1)^3 = \frac{k^2(k+1)^2}{4} + (k+1)^3$

$= \frac{k^2(k+1)^2 + 4(k+1)^3}{4} = \frac{(k+1)^2\left[k^2 + 4(k+1)\right]}{4}$

$= \frac{(k+1)^2(k^2 + 4k + 4)}{4} = \frac{(k+1)^2(k+2)^2}{4}$

This matches the formula with $n = k+1$ . ✓

Conclusion

By the Principle of Mathematical Induction, the formula holds for all integers $n \geq 1$ : $1^3 + 2^3 + \cdots + n^3 = \frac{n^2(n+1)^2}{4}$
Answer

Part 1: Committee Formation

Given Data
- Total scientists = 8 (5 chemists + 3 biologists)
- Committee required = 5 members: exactly 3 chemists and 2 biologists
Solution

Select 3 chemists from 5: $$C(5,3) = \frac{5!}{3!,2!} = \frac{5\times 4}{2\times 1} = 10$$

Select 2 biologists from 3: $$C(3,2) = \frac{3!}{2!,1!} = 3$$

By the multiplication principle: $$\text{Total} = C(5,3)\times C(3,2) = 10 \times 3 = \boxed{30 \text{ ways}}$$

Part 2: Proof by Mathematical Induction

Claim: $$1^3 + 2^3 + \cdots + n^3 = \frac{n^2(n+1)^2}{4}, \quad n \geq 1$$

Base Case (n = 1)
- LHS $= 1^3 = 1$
- RHS $= \dfrac{1^2 \cdot 2^2}{4} = \dfrac{4}{4} = 1$
LHS = RHS, so the statement holds for $n = 1$. ✓

Inductive Hypothesis

Assume true for $n = k$: $$1^3 + 2^3 + \cdots + k^3 = \frac{k^2(k+1)^2}{4}$$

Inductive Step

Show true for $n = k+1$: $$1^3 + \cdots + k^3 + (k+1)^3 = \frac{k^2(k+1)^2}{4} + (k+1)^3$$

$$= \frac{k^2(k+1)^2 + 4(k+1)^3}{4} = \frac{(k+1)^2\left[k^2 + 4(k+1)\right]}{4}$$

$$= \frac{(k+1)^2(k^2 + 4k + 4)}{4} = \frac{(k+1)^2(k+2)^2}{4}$$

This matches the formula with $n = k+1$. ✓

Conclusion

By the Principle of Mathematical Induction, the formula holds for all integers $n \geq 1$: $$1^3 + 2^3 + \cdots + n^3 = \frac{n^2(n+1)^2}{4}$$
310 marksNumericalEquivalence RelationsHideAnswer
Show that the relation R = {(a, b): |a-b| is even} is an equivalence relation in the set of integers. Given the following transport network with the edges called with their capacities find all S-D cuts and their capacities and what the minimum capacity?[10]
--- To prove R is an equivalence relation, we verify reflexivity, symmetry, and transitivity. For any integer $a$ : $a - a = 0 = 0$ Since $0$ is even, $(a, a) \in R$ for all $a \in \mathbb{Z}$ . R is reflexive. ✓ Suppose $(a, b) \in R$ , ...
--- To prove R is an equivalence relation, we verify reflexivity, symmetry, and transitivity. For any integer $a$: $$a - a = 0 = 0$$ Since $0$ is even, $(a, a) \in R$ for all $a \in \mathbb{Z}$. R is reflexive. ✓ Suppose $(a, b) \in R$, ...
45 marksPredicates and QuantifiersHideAnswer
List any one example of tautology. Represent the following sentences into predicate logic. a. Not all employees are loyal. b. All students having good attitude are lovable. [5]
A tautology is a propositional formula that is always true regardless of the truth values of its variables. Example: $P \lor \neg P \quad \text{(Law of Excluded Middle)}$ P ¬P P ∨ ¬P ---------------- T F T F T T Since the formula is tr...
A tautology is a propositional formula that is always true regardless of the truth values of its variables. Example: $$P \lor \neg P \quad \text{(Law of Excluded Middle)}$$ P ¬P P ∨ ¬P ---------------- T F T F T T Since the formula is tr...
55 marksProof MethodsHideAnswer
Prove that 'If the product of two integers a and b is even then either a is even or b is even' using condition method. [5]
The conditional method (also called proof by contrapositive) proves a statement of the form: P → Q by instead proving its contrapositive: ¬Q → ¬P which is logically equivalent to the original statement. --- Original Statement: If a × b i...
65 marksNumericalApplications of Number TheoryHideAnswer
Use Chinese remainder Theorem to find the value of x such that x = 0 (MOD 2), x = 2 (MOD 3), x = 3 (MOD 5). [5]
$x \equiv 0 \pmod 2, \quad x \equiv 2 \pmod 3, \quad x \equiv 3 \pmod 5$ Moduli: $m1=2,\ m2=3,\ m3=5$ . Residues: $a1=0,\ a2=2,\ a3=3$ . $\gcd(2,3)=\gcd(2,5)=\gcd(3,5)=1$ , so CRT applies. $m = 2\times3\times5 = 30$ $$M1=\frac{30}{2}=15...
$$x \equiv 0 \pmod 2, \quad x \equiv 2 \pmod 3, \quad x \equiv 3 \pmod 5$$ Moduli: $m1=2,\ m2=3,\ m3=5$. Residues: $a1=0,\ a2=2,\ a3=3$. $\gcd(2,3)=\gcd(2,5)=\gcd(3,5)=1$, so CRT applies. $$m = 2\times3\times5 = 30$$ $$M1=\frac{30}{2}=15...
75 marksGraph TypesHideAnswer
Define bipartite graph with an example. State the necessary conditions for the graphs to be isomorphic. [5]
--- A graph G = (V, E) is called a bipartite graph if its vertex set V can be partitioned into two disjoint non-empty subsets V1 and V2 (called partition sets) such that: - Every edge in E connects a vertex in V1 to a vertex in V2. - No ...
85 marksNumericalMinimum Spanning TreesHideAnswer
State Generalized Pigeonhole principle. Find the MST from following graph using Kruskal Algorithm. [5]
Part 1: Requires the statement of the Generalized Pigeonhole Principle (theory, no numeric data). - Part 2: Requires finding the MST using Kruskal's Algorithm "from the following graph." Missing data: The actual graph (vertices, edges,...
95 marksRules of InferencesHideAnswer
Give the premise 'If it rains or strike holds then the exam will be cancelled. If it doesn't rain then it will be sunny day. The exam was not cancelled. Show that it was sunny day'. [5]
Let us define the propositional variables: - p : It rains - q : Strike holds - r : Exam will be cancelled - s : It will be a sunny day --- No. Premise Symbolic Form ----------------------------- P1 If it rains or strike holds, then exam ...
105 marksNumericalIntegers and DivisionHideAnswer
Find the value of $-2 \bmod 3$ and $3153^{15} \bmod 5$ . Illustrate an example to show the join operation between any two Boolean matrices. [5]
Find the value of $-2 \bmod 3$ and $3153^{15} \bmod 5$. Illustrate an example to show the join operation between any two Boolean matrices. [5]
Expression 1: $-2 \bmod 3$ - Expression 2: $3153^{15} \bmod 5$ (the garbled text "3153^{15}315" is read as $3153^{15}$ ) - Task 3: Illustrate the join operation between two Boolean (zero-one) matrices with an example. --- Definition: Fo...

Expression 1: $-2 \bmod 3$ - Expression 2: $3153^{15} \bmod 5$ (the garbled text "3153^{15}315" is read as $3153^{15}$) - Task 3: Illustrate the join operation between two Boolean (zero-one) matrices with an example. --- Definition: Fo...
115 marksEuler and Hamiltonian Path and CircuitsHideAnswer
Give an example of fallacy. State the necessary and sufficient conditions for a graph to have Euler path and Euler circuit. [5]
--- A fallacy is an error in reasoning where a conclusion is drawn incorrectly from given premises, even though the argument appears valid on the surface. Example: Consider the following argument: Premise: If a graph is Eulerian, then ev...
125 marksNumericalExtended Euclidean AlgorithmHideAnswer
Find the GCD of 24 and 32 using Extended Euclidean algorithm. [5]
GCD of 24 and 32 Using the Extended Euclidean Algorithm

Step 1 - Given Data
- $a = 32$ , $b = 24$ (arrange larger first)
- Goal: find $\gcd(24, 32)$ and Bezout coefficients $s, t$ such that $\gcd = s \cdot a + t \cdot b$ .
Step 2 - Solve

Euclidean Algorithm (successive division)

Step Equation Quotient Remainder
1 $32 = 1 \cdot 24 + 8$ 1 8
2 $24 = 3 \cdot 8 + 0$ 3 0

The last non-zero remainder is $8$ .

$\gcd(24, 32) = 8$

Back-Substitution (Extended part)

From Step 1:

$32 = 1 \cdot 24 + 8$

Solve for the remainder $8$ :

$8 = 32 - 1 \cdot 24$

Written as a linear combination:

$\boxed{8 = (1)\cdot 32 + (-1)\cdot 24}$

So the Bezout coefficients are $s = 1$ (for 32) and $t = -1$ (for 24).

Verification

$(1)\cdot 32 + (-1)\cdot 24 = 32 - 24 = 8 \checkmark$

Final Result

$\gcd(24, 32) = 8 = (1)\cdot 32 + (-1)\cdot 24$

Labelling the coefficients by which number they multiply gives $s = -1$ for 24 and $t = 1$ for 32, the same combination: $8 = 32 - 24$ . The GCD result of $8$ is unchanged.
GCD of 24 and 32 Using the Extended Euclidean Algorithm

Step 1 - Given Data
- $a = 32$, $b = 24$ (arrange larger first)
- Goal: find $\gcd(24, 32)$ and Bezout coefficients $s, t$ such that $\gcd = s \cdot a + t \cdot b$.
Step 2 - Solve

Euclidean Algorithm (successive division)

Step Equation Quotient Remainder
1 $32 = 1 \cdot 24 + 8$ 1 8
2 $24 = 3 \cdot 8 + 0$ 3 0

The last non-zero remainder is $8$.

$$\gcd(24, 32) = 8$$

Back-Substitution (Extended part)

From Step 1:

$$32 = 1 \cdot 24 + 8$$

Solve for the remainder $8$:

$$8 = 32 - 1 \cdot 24$$

Written as a linear combination:

$$\boxed{8 = (1)\cdot 32 + (-1)\cdot 24}$$

So the Bezout coefficients are $s = 1$ (for 32) and $t = -1$ (for 24).

Verification

$$(1)\cdot 32 + (-1)\cdot 24 = 32 - 24 = 8 \checkmark$$

Final Result

$$\gcd(24, 32) = 8 = (1)\cdot 32 + (-1)\cdot 24$$

Labelling the coefficients by which number they multiply gives $s = -1$ for 24 and $t = 1$ for 32, the same combination: $8 = 32 - 24$. The GCD result of $8$ is unchanged.

Step	Equation	Quotient	Remainder
1	$32 = 1 \cdot 24 + 8$	1	8
2	$24 = 3 \cdot 8 + 0$	3	0

Step	Equation	Quotient	Remainder
1	$32 = 1 \cdot 24 + 8$	1	8
2	$24 = 3 \cdot 8 + 0$	3	0

Keep going

Important questions + predictions

Full syllabus Flashcards and practice

Other papers

2081 paper 2080.1 paper 2080 paper 2078 paper 2076 paper 2075 paper

Discrete Structures 2079 question paper

Answer

Part 1: Committee Formation

Given Data

Solution

Part 2: Proof by Mathematical Induction

Base Case (n = 1)

Inductive Hypothesis

Inductive Step

Conclusion

Answer

Part 1: Committee Formation

Given Data

Solution

Part 2: Proof by Mathematical Induction

Base Case (n = 1)

Inductive Hypothesis

Inductive Step

Conclusion

GCD of 24 and 32 Using the Extended Euclidean Algorithm

Step 1 - Given Data

Step 2 - Solve

Euclidean Algorithm (successive division)

Back-Substitution (Extended part)

Verification

Final Result

GCD of 24 and 32 Using the Extended Euclidean Algorithm

Step 1 - Given Data

Step 2 - Solve

Euclidean Algorithm (successive division)

Back-Substitution (Extended part)

Verification

Final Result

Answer

Part 1: Committee Formation

Given Data

Solution

Part 2: Proof by Mathematical Induction

Base Case (n = 1)

Inductive Hypothesis

Inductive Step

Conclusion

GCD of 24 and 32 Using the Extended Euclidean Algorithm

Step 1 - Given Data

Step 2 - Solve

Euclidean Algorithm (successive division)

Back-Substitution (Extended part)

Verification

Final Result