CSC165 · TU past paper

Discrete Structures 2080 question paper

The complete TU 2080 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 marksStrong Induction and Well OrderingHideAnswer
Explain strong induction in detail. What is recursively defined function? Use mathematical induction to prove $7^{n+2} + 8^{2n+1}$ is divisible by 57.[10]
Explain strong induction in detail. What is recursively defined function? Use mathematical induction to prove $7^{n+2} + 8^{2n+1}$ is divisible by 57.[10]
--- Strong Induction (also called the Second Principle of Mathematical Induction or Complete Induction) is a variant of mathematical induction where, to prove that a statement P(n) is true for all positive integers n, we assume that P(k)...
210 marksNumericalPigeonhole PrincipleHideAnswer
State pigeonhole principle. Solve the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2}$ , with initial conditions $a_1 = 1$ and $a_2 = 3$ .[10]
State pigeonhole principle. Solve the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2}$, with initial conditions $a_1 = 1$ and $a_2 = 3$.[10]
Recurrence: $an = 5a{n-1} - 6a{n-2}$ - Initial conditions: $a1 = 1$ , $a2 = 3$ --- Statement: If $k+1$ or more objects are placed into $k$ boxes, then at least one box contains two or more objects. Generalized form: If $N$ objects are p...

Recurrence: $an = 5a{n-1} - 6a{n-2}$ - Initial conditions: $a1 = 1$, $a2 = 3$ --- Statement: If $k+1$ or more objects are placed into $k$ boxes, then at least one box contains two or more objects. Generalized form: If $N$ objects are p...
310 marksNumericalThe Max Flow-Min Cut TheoremHideAnswer
State max flow min cut theorem. Find the value of maximal flow in the graph below:[10]
The question asks to: 1. State the Max Flow Min Cut Theorem. 2. Find the value of maximal flow "in the graph below." Missing data: The actual flow network graph (vertices, directed edges, and edge capacities) is not provided in the text....
45 marksNumericalInclusion-Exclusion PrincipleHideAnswer
Explain the principle of inclusion and exclusion. How many integers from 1 to 30 are multiples of 2 or 3? [5]
Principle of Inclusion and Exclusion

Given Data
- Range of integers: 1 to 30
- Divisibility conditions: multiples of 2 or multiples of 3
Statement of the Principle

The Principle of Inclusion and Exclusion is a counting technique for finding the number of elements in the union of finite sets. When we add the sizes of individual sets, elements common to more than one set get counted multiple times. The principle corrects this overcounting by systematically including individual set sizes, excluding pairwise intersections, including triple intersections, and so on.

For Two Sets:

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

For Three Sets:

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

The alternating signs (add odd-order intersections, subtract even-order... precisely: single sets +, pairs -, triples +) ensure each element is counted exactly once.

Application: Multiples of 2 or 3 from 1 to 30

Step 1: Define sets
- $A$ = multiples of 2 in $[1,30]$
- $B$ = multiples of 3 in $[1,30]$
We need $n(A \cup B)$ .

Step 2: Multiples of 2 $n(A) = \left\lfloor \frac{30}{2} \right\rfloor = 15$

Step 3: Multiples of 3 $n(B) = \left\lfloor \frac{30}{3} \right\rfloor = 10$

Step 4: Multiples of both 2 and 3 (i.e. multiples of $\text{lcm}(2,3)=6$ ) $n(A \cap B) = \left\lfloor \frac{30}{6} \right\rfloor = 5$

Step 5: Apply the principle $n(A \cup B) = n(A) + n(B) - n(A \cap B) = 15 + 10 - 5 = 20$

$\boxed{n(A \cup B) = 20}$

Verification list: $\{2,3,4,6,8,9,10,12,14,15,16,18,20,21,22,24,26,27,28,30\}$ Counting these gives exactly 20 integers. ✓

Conclusion

There are 20 integers between 1 and 30 that are multiples of 2 or 3.
Principle of Inclusion and Exclusion

Given Data
- Range of integers: 1 to 30
- Divisibility conditions: multiples of 2 or multiples of 3
Statement of the Principle

The Principle of Inclusion and Exclusion is a counting technique for finding the number of elements in the union of finite sets. When we add the sizes of individual sets, elements common to more than one set get counted multiple times. The principle corrects this overcounting by systematically including individual set sizes, excluding pairwise intersections, including triple intersections, and so on.

For Two Sets:

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

For Three Sets:

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

The alternating signs (add odd-order intersections, subtract even-order... precisely: single sets +, pairs -, triples +) ensure each element is counted exactly once.

Application: Multiples of 2 or 3 from 1 to 30

Step 1: Define sets
- $A$ = multiples of 2 in $[1,30]$
- $B$ = multiples of 3 in $[1,30]$
We need $n(A \cup B)$.

Step 2: Multiples of 2 $$n(A) = \left\lfloor \frac{30}{2} \right\rfloor = 15$$

Step 3: Multiples of 3 $$n(B) = \left\lfloor \frac{30}{3} \right\rfloor = 10$$

Step 4: Multiples of both 2 and 3 (i.e. multiples of $\text{lcm}(2,3)=6$) $$n(A \cap B) = \left\lfloor \frac{30}{6} \right\rfloor = 5$$

Step 5: Apply the principle $$n(A \cup B) = n(A) + n(B) - n(A \cap B) = 15 + 10 - 5 = 20$$

$$\boxed{n(A \cup B) = 20}$$

Verification list: $${2,3,4,6,8,9,10,12,14,15,16,18,20,21,22,24,26,27,28,30}$$ Counting these gives exactly 20 integers. ✓

Conclusion

There are 20 integers between 1 and 30 that are multiples of 2 or 3.
55 marksFunctions for Computer ScienceHideAnswer
Give the example of ceiling, floor and boolean function. How do you plot the graph of the function? [5]
The floor function for any real number x is defined as the greatest integer less than or equal to x. It is denoted by ⌊x⌋. Expression Value Reason --------- ⌊3.5⌋ 3 Greatest integer ≤ 3.5 is 3 ⌊-2.4⌋ -3 Greatest integer ≤ -2.4 is -3 ⌊3.1...
65 marksNumericalApplications of Number TheoryHideAnswer
Using Chinese remainder theorem solve the following congruences.x = 1 (MOD 3), x = 3 (MOD 5), x = 6 (MOD 7) [5]
System of congruences: $x \equiv 1 \pmod{3}, \quad x \equiv 3 \pmod{5}, \quad x \equiv 6 \pmod{7}$ - Residues: $a1 = 1,\ a2 = 3,\ a3 = 6$ - Moduli: $m1 = 3,\ m2 = 5,\ m3 = 7$ --- $3, 5, 7$ are distinct primes, so they are pairwise copr...
System of congruences: $$x \equiv 1 \pmod{3}, \quad x \equiv 3 \pmod{5}, \quad x \equiv 6 \pmod{7}$$ - Residues: $a1 = 1,\ a2 = 3,\ a3 = 6$ - Moduli: $m1 = 3,\ m2 = 5,\ m3 = 7$ --- $3, 5, 7$ are distinct primes, so they are pairwise copr...
75 marksNumericalExtended Euclidean AlgorithmHideAnswer
Find the multiplicative inverse of 4 in $\mathbb{Z}_{11}$ using extended euclidean algorithm. [5]
Find the multiplicative inverse of 4 in $\mathbb{Z}_{11}$ using extended euclidean algorithm. [5]
Modulus: $n = 11$ - Element: $a = 4$ - Goal: find $x$ such that $4x \equiv 1 \pmod{11}$ We seek integers $s, t$ satisfying: $s \cdot 4 + t \cdot 11 = \gcd(4, 11)$ Since $\gcd(4,11) = 1$ , the inverse exists, and $s \bmod 11$ is the in...

Modulus: $n = 11$ - Element: $a = 4$ - Goal: find $x$ such that $4x \equiv 1 \pmod{11}$ We seek integers $s, t$ satisfying: $$s \cdot 4 + t \cdot 11 = \gcd(4, 11)$$ Since $\gcd(4,11) = 1$, the inverse exists, and $s \bmod 11$ is the in...
85 marksPredicates and QuantifiersHideAnswer
Express the following sentences using quantifier. 1) Not all people are loyal. 2)Everybody loves somebody. 3). Someone has passed the exam 4). Aquatic animals can't live without water 5). Some subjects are not interesting. [5]
Definitions used: Let the domain of discourse be the set of all people/subjects/animals unless stated otherwise. --- Let L(x) = "x is loyal" Logical Expression: $\neg \forall x \; L(x)$ This is equivalent to: $\exists x \; \neg L(x)$ ...
Definitions used: Let the domain of discourse be the set of all people/subjects/animals unless stated otherwise. --- Let L(x) = "x is loyal" Logical Expression: $$\neg \forall x ; L(x)$$ This is equivalent to: $$\exists x ; \neg L(x)$$...
95 marksProof MethodsHideAnswer
What is proof by contradiction? Give a proof by contradiction to show that if 3n+2 is odd then n is odd. [5]
Proof by Contradiction

Definition

Proof by contradiction is a method of mathematical proof in which we assume that the statement to be proved is false, and then show that this assumption leads to a logical contradiction (an impossibility). Since the assumption leads to a contradiction, the original statement must be true.

The general structure is:
1. Assume the negation of what we want to prove.
2. Use logical reasoning to derive a contradiction.
3. Conclude that the original statement is true.
Theorem to Prove

If 3n + 2 is odd, then n is odd.

Proof

Step 1: Identify the structure
- Hypothesis (p): 3n + 2 is odd
- Conclusion (q): n is odd
- We want to prove: p → q
Step 2: Assume the negation of the conclusion

For proof by contradiction, we assume:
- 3n + 2 is odd (hypothesis holds)
- n is NOT odd, i.e., n is even (negation of conclusion)
Step 3: Use the assumption

Since n is even, by definition of even integers, we can write:

$n = 2k \quad \text{for some integer } k$

Step 4: Substitute into 3n + 2

$3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1)$

Step 5: Analyze the result

Since $3k + 1$ is an integer, the expression $2(3k + 1)$ is of the form $2m$ where $m = 3k + 1$ .

By definition of even numbers, $3n + 2$ is even.

Step 6: Identify the contradiction

We assumed that 3n + 2 is odd, but our derivation shows that 3n + 2 is even.

This is a contradiction because a number cannot be both odd and even at the same time.

Step 7: Conclusion

Since assuming "n is even" leads to a contradiction, our assumption must be false. Therefore:

$\boxed{n \text{ is odd}}$

This completes the proof by contradiction. $\blacksquare$
Proof by Contradiction

Definition

Proof by contradiction is a method of mathematical proof in which we assume that the statement to be proved is false, and then show that this assumption leads to a logical contradiction (an impossibility). Since the assumption leads to a contradiction, the original statement must be true.

The general structure is:
1. Assume the negation of what we want to prove.
2. Use logical reasoning to derive a contradiction.
3. Conclude that the original statement is true.
Theorem to Prove

If 3n + 2 is odd, then n is odd.

Proof

Step 1: Identify the structure
- Hypothesis (p): 3n + 2 is odd
- Conclusion (q): n is odd
- We want to prove: p → q
Step 2: Assume the negation of the conclusion

For proof by contradiction, we assume:
- 3n + 2 is odd (hypothesis holds)
- n is NOT odd, i.e., n is even (negation of conclusion)
Step 3: Use the assumption

Since n is even, by definition of even integers, we can write:

$$n = 2k \quad \text{for some integer } k$$

Step 4: Substitute into 3n + 2

$$3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1)$$

Step 5: Analyze the result

Since $3k + 1$ is an integer, the expression $2(3k + 1)$ is of the form $2m$ where $m = 3k + 1$.

By definition of even numbers, $3n + 2$ is even.

Step 6: Identify the contradiction

We assumed that 3n + 2 is odd, but our derivation shows that 3n + 2 is even.

This is a contradiction because a number cannot be both odd and even at the same time.

Step 7: Conclusion

Since assuming "n is even" leads to a contradiction, our assumption must be false. Therefore:

$$\boxed{n \text{ is odd}}$$

This completes the proof by contradiction. $\blacksquare$
105 marksNumericalGraph IsomorphismHideAnswer
State the necessary conditions for two graphs to be isomorphic. How many different words from 'MANAGER' can be generated with or without meaning? [5]
Two graphs $G1 = (V1, E1)$ and $G2 = (V2, E2)$ are isomorphic if there exists a bijection (one-to-one and onto mapping) $f: V1 \to V2$ such that any two vertices $u$ and $v$ are adjacent in $G1$ if and only if $f(u)$ and $f(v)$ are adjac...
Two graphs $G1 = (V1, E1)$ and $G2 = (V2, E2)$ are isomorphic if there exists a bijection (one-to-one and onto mapping) $f: V1 \to V2$ such that any two vertices $u$ and $v$ are adjacent in $G1$ if and only if $f(u)$ and $f(v)$ are adjac...
115 marksNumericalClosure of RelationsHideAnswer
Define symmetric closure. What is the symmetric closure of the relation R = {(1,1), (1,2), (2,2), (2,3), (3,1), (2,1)} on the set A = {1,2,3}? [5]
Set $A = \{1, 2, 3\}$ - Relation $R = \{(1,1),\ (1,2),\ (2,2),\ (2,3),\ (3,1),\ (2,1)\}$ --- The symmetric closure of a relation $R$ on a set $A$ is the smallest symmetric relation on $A$ that contains $R$ . It is formed by adding to

Set $A = {1, 2, 3}$ - Relation $R = {(1,1),\ (1,2),\ (2,2),\ (2,3),\ (3,1),\ (2,1)}$ --- The symmetric closure of a relation $R$ on a set $A$ is the smallest symmetric relation on $A$ that contains $R$. It is formed by adding to
125 marksNumericalGraph RepresentationHideAnswer
Represent following graph using adjacency matrix. [5]
Given data: - The question asks to represent "following graph" using an adjacency matrix. - The actual graph figure (vertices, edges, directedness, weights) is NOT provided in the text given to me. Missing data: The specific graph image ...

Keep going

Important questions + predictions

Full syllabus Flashcards and practice

Other papers

2081 paper 2080.1 paper 2079 paper 2078 paper 2076 paper 2075 paper

Discrete Structures 2080 question paper

Principle of Inclusion and Exclusion

Given Data

Statement of the Principle

For Two Sets:

For Three Sets:

Application: Multiples of 2 or 3 from 1 to 30

Conclusion

Principle of Inclusion and Exclusion

Given Data

Statement of the Principle

For Two Sets:

For Three Sets:

Application: Multiples of 2 or 3 from 1 to 30

Conclusion

Proof by Contradiction

Definition

Theorem to Prove

Proof

Proof by Contradiction

Definition

Theorem to Prove

Proof

Principle of Inclusion and Exclusion

Given Data

Statement of the Principle

For Two Sets:

For Three Sets:

Application: Multiples of 2 or 3 from 1 to 30

Conclusion

Proof by Contradiction

Definition

Theorem to Prove

Proof