CSC165 · TU past paper

Discrete Structures 2080.1 question paper

The complete TU 2080.1 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 marksmathematical InductionHideAnswer
How can you use mathematical induction to prove statements? Use mathematical induction to show that sum of first n positive integer is $\frac{n(n+1)}{2}$ [10]
How can you use mathematical induction to prove statements? Use mathematical induction to show that sum of first n positive integer is $\frac{n(n+1)}{2}$ [10]
Mathematical induction is a proof technique used to prove that a statement P(n) is true for all positive integers n. It works in two steps: Step 1: Basis Step (Base Case) Show that the statement P(1) is true (i.e., verify the statement h...
210 marksNumericalSolving Recurrence RelationsHideAnswer
Linear Homogeneous Recurrence Relation with Constant Coefficients

A linear homogeneous recurrence relation with constant coefficients is a recurrence relation of the form:

$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}$

where $c_1, c_2, \ldots, c_k$ are constants and $k$ is the order of the recurrence relation.

To solve such a recurrence relation, we use the characteristic equation method:

Assume a solution of the form $a_n = r^n$

Substitute into the recurrence relation to get the characteristic equation

Solve for the roots $r$

The general solution depends on the nature of the roots (distinct, repeated, or complex)
Linear Homogeneous Recurrence Relation with Constant Coefficients

A linear homogeneous recurrence relation with constant coefficients is a recurrence relation of the form:

$$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}$$

where $c_1, c_2, \ldots, c_k$ are constants and $k$ is the order of the recurrence relation.

To solve such a recurrence relation, we use the characteristic equation method:

Assume a solution of the form $a_n = r^n$

Substitute into the recurrence relation to get the characteristic equation

Solve for the roots $r$

The general solution depends on the nature of the roots (distinct, repeated, or complex)
Recurrence: $an = 6a{n-1} - 9a{n-2}$ - Initial conditions: $a0 = 1$ , $a1 = 6$ All data present. No missing values. A linear homogeneous recurrence relation of degree $k$ with constant coefficients has the form: $$an = c1 a{n-1} + c2 a{...

Recurrence: $an = 6a{n-1} - 9a{n-2}$ - Initial conditions: $a0 = 1$, $a1 = 6$ All data present. No missing values. A linear homogeneous recurrence relation of degree $k$ with constant coefficients has the form: $$an = c1 a{n-1} + c2 a{...
310 marksNumericalShortest Path AlgorithmHideAnswer
What is shortest path problem? Use Dijkstra's shortest path algorithm to find the shortest path between vertices a and z in the weighted graph below:[10]
Shortest Path Problem and Dijkstra's Algorithm

STEP 1 - EXTRACT: Given Data

Question requirements:
- Define the shortest path problem.
- Apply Dijkstra's algorithm to find the shortest path from vertex a to vertex z.
Critical data issue: the weighted graph itself is not reproduced in the text supplied here. The working below therefore uses an assumed standard graph with the following edge weights:

Edge Weight
a-b 4
a-d 2
a-e 7
b-c 2
b-e 1
c-f 5
d-e 3
e-f 4
e-z 6
f-z 3

Since the actual figure is not available, the answer (a) provides the definition, (b) states the algorithm, and (c) solves the problem using the assumed edge set above, which could not be verified against the original figure.

STEP 2 - SOLVE

Definition: Shortest Path Problem

A weighted graph is a graph in which every edge is assigned a non-negative number called its weight. The length of a path is the sum of the weights of the edges on that path. The shortest path problem is the problem of finding, between two specified vertices $a$ and $z$ , a path whose total weight (length) is minimum. Dijkstra's algorithm is a classic greedy method that solves this for graphs with non-negative weights.

Dijkstra's Algorithm
1. Set distance of source $= 0$ , all others $= \infty$ ; mark all unvisited.
2. Pick the unvisited vertex $u$ with smallest tentative distance; make it current.
3. Relax each unvisited neighbor $v$ : if $d(u)+w(u,v) < d(v)$ , update $d(v)$ .
4. Mark $u$ visited.
5. Repeat until the target $z$ is visited.
Execution (on the assumed edge set)

Init: $d(a)=0$ , others $=\infty$ .

Iteration 1: a (0): b = 4, d = 2, e = 7. Visit a. Next: d (2).

Iteration 2: d (2): e = $\min(7, 2+3)=5$ . Visit d. Next: b (4).

Iteration 3: b (4): c = $4+2 = 6$ ; e = $\min(5, 4+1)=5$ (unchanged). Visit b. Next: e (5).

Iteration 4: e (5): f = $5+4 = 9$ ; z = $5+6 = 11$ . Visit e. Next: c (6).

Iteration 5: c (6): f = $\min(9, 6+5)=9$ (unchanged). Visit c. Next: f (9).

Iteration 6: f (9): z = $\min(11, 9+3)=12$ ? Since $12 > 11$ , z stays 11. Visit f. Next: z (11).

Iteration 7: z (11): target reached.

Final Distance Table

Vertex a b c d e f z
Distance 0 4 6 2 5 9 11

Shortest Path and Length

$z$ received value $11$ from vertex $e$ (via $e\text{-}z = 6$ ), and $e = 5$ came from $d$ (via $d\text{-}e=3$ ), and $d = 2$ came from $a$ .

$\text{Shortest path: } a \to d \to e \to z$ $\text{Length} = 2 + 3 + 6 = \boxed{11}$

Trace the path back, do not stop at the distance: the final table gives $d(z)=11$ . The value $9$ at $f$ plus edge $f\text{-}z=3$ gives $12 > 11$ , so the $f\to z$ route does not improve $z$ . The shortest path is $a\to d\to e\to z$ with length $11$ , not one through $f$ .

Warning: the underlying graph was assumed, not read from the actual exam figure. If the real figure differs, the whole solution must be redone with the true weights.
Shortest Path Problem and Dijkstra's Algorithm

STEP 1 - EXTRACT: Given Data

Question requirements:
- Define the shortest path problem.
- Apply Dijkstra's algorithm to find the shortest path from vertex a to vertex z.
Critical data issue: the weighted graph itself is not reproduced in the text supplied here. The working below therefore uses an assumed standard graph with the following edge weights:

Edge Weight
a-b 4
a-d 2
a-e 7
b-c 2
b-e 1
c-f 5
d-e 3
e-f 4
e-z 6
f-z 3

Since the actual figure is not available, the answer (a) provides the definition, (b) states the algorithm, and (c) solves the problem using the assumed edge set above, which could not be verified against the original figure.

STEP 2 - SOLVE

Definition: Shortest Path Problem

A weighted graph is a graph in which every edge is assigned a non-negative number called its weight. The length of a path is the sum of the weights of the edges on that path. The shortest path problem is the problem of finding, between two specified vertices $a$ and $z$, a path whose total weight (length) is minimum. Dijkstra's algorithm is a classic greedy method that solves this for graphs with non-negative weights.

Dijkstra's Algorithm
1. Set distance of source $= 0$, all others $= \infty$; mark all unvisited.
2. Pick the unvisited vertex $u$ with smallest tentative distance; make it current.
3. Relax each unvisited neighbor $v$: if $d(u)+w(u,v) < d(v)$, update $d(v)$.
4. Mark $u$ visited.
5. Repeat until the target $z$ is visited.
Execution (on the assumed edge set)

Init: $d(a)=0$, others $=\infty$.

Iteration 1: a (0): b = 4, d = 2, e = 7. Visit a. Next: d (2).

Iteration 2: d (2): e = $\min(7, 2+3)=5$. Visit d. Next: b (4).

Iteration 3: b (4): c = $4+2 = 6$; e = $\min(5, 4+1)=5$ (unchanged). Visit b. Next: e (5).

Iteration 4: e (5): f = $5+4 = 9$; z = $5+6 = 11$. Visit e. Next: c (6).

Iteration 5: c (6): f = $\min(9, 6+5)=9$ (unchanged). Visit c. Next: f (9).

Iteration 6: f (9): z = $\min(11, 9+3)=12$? Since $12 > 11$, z stays 11. Visit f. Next: z (11).

Iteration 7: z (11): target reached.

Final Distance Table

Vertex a b c d e f z
Distance 0 4 6 2 5 9 11

Shortest Path and Length

$z$ received value $11$ from vertex $e$ (via $e\text{-}z = 6$), and $e = 5$ came from $d$ (via $d\text{-}e=3$), and $d = 2$ came from $a$.

$$\text{Shortest path: } a \to d \to e \to z$$ $$\text{Length} = 2 + 3 + 6 = \boxed{11}$$

Trace the path back, do not stop at the distance: the final table gives $d(z)=11$. The value $9$ at $f$ plus edge $f\text{-}z=3$ gives $12 > 11$, so the $f\to z$ route does not improve $z$. The shortest path is $a\to d\to e\to z$ with length $11$, not one through $f$.

Warning: the underlying graph was assumed, not read from the actual exam figure. If the real figure differs, the whole solution must be redone with the true weights.
45 marksEquivalence RelationsHideAnswer
Let us assume that R be a relation on the set of ordered pair of positive integers such that ((a,b),(c,d))∈R((a, b), (c, d)) \in R((a,b),(c,d))∈R if and only if ad = bc. Is R an equivalence relation? [5]
A relation R on a set A is an equivalence relation if and only if it satisfies three properties: 1. Reflexivity: (a, a) ∈ R for all a ∈ A 2. Symmetry: If (a, b) ∈ R then (b, a) ∈ R 3. Transitivity: If (a, b) ∈ R and (b, c) ∈ R then (a, c...
55 marksNumericalBasic ConceptHideAnswer
Define function. Let $f_1$ and $f_2$ be function from $\mathbb{R}$ to $\mathbb{R}$ such that $f_1(x) = x^2$ and $f_2(x) = x - x^2$ . What are the functions $f_1 + f_2$ and $f_1 \cdot f_2$ ? [5]
Define function. Let $f_1$ and $f_2$ be function from $\mathbb{R}$ to $\mathbb{R}$ such that $f_1(x) = x^2$ and $f_2(x) = x - x^2$. What are the functions $f_1 + f_2$ and $f_1 \cdot f_2$? [5]
$f1, f2 : \mathbb{R} \to \mathbb{R}$ - $f1(x) = x^2$ - $f2(x) = x - x^2$ - Required: $f1 + f2$ and $f1 \cdot f2$ All data present. --- A function $f$ from a set $A$ to a set $B$ is an assignment that maps to each element $x \in A$ exac...

$f1, f2 : \mathbb{R} \to \mathbb{R}$ - $f1(x) = x^2$ - $f2(x) = x - x^2$ - Required: $f1 + f2$ and $f1 \cdot f2$ All data present. --- A function $f$ from a set $A$ to a set $B$ is an assignment that maps to each element $x \in A$ exac...
65 marksFuzzy Sets and Membership FunctionsHideAnswer
Explain fuzzy set with example. How do you find complement of a fuzzy set? [5]
A fuzzy set is a set where each element has a degree of membership (also called membership value) that ranges between 0 and 1, rather than the classical (crisp) set where an element either belongs or does not belong to a set. In a classi...

Edge	Weight
a-b	4
a-d	2
a-e	7
b-c	2
b-e	1
c-f	5
d-e	3
e-f	4
e-z	6
f-z	3

Vertex	a	b	c	d	e	f	z
Distance	0	4	6	2	5	9	11

Edge	Weight
a-b	4
a-d	2
a-e	7
b-c	2
b-e	1
c-f	5
d-e	3
e-f	4
e-z	6
f-z	3

Vertex	a	b	c	d	e	f	z
Distance	0	4	6	2	5	9	11

75 marksNumericalIntegers and DivisionAnswer

What is congruent modulo? Determine whether 37 is congruent to 3 modulo 7 and whether -29 is congruent to 5 modulo 17. [5]

Congruent Modulo: Definition and Examples

Given Data

Check 1: Is $37 \equiv 3 \pmod{7}$ ?
Check 2: Is $-29 \equiv 5 \pmod{17}$ ?

STEP 1 - Definition

If $a$ and $b$ are integers and $m$ is a positive integer, then $a$ is congruent to $b$ modulo $m$ if $m$ divides $(a - b)$ .

Notation: $a \equiv b \pmod{m}$

If they are not congruent, we write $a \not\equiv b \pmod{m}$ .

Equivalent test: $a \equiv b \pmod{m}$ if and only if $a \bmod m = b \bmod m$ .

STEP 2 - Solve

Part 1: Is $37 \equiv 3 \pmod 7$ ?

Check if $7 \mid (37 - 3)$ : $37 - 3 = 34$ $34 = 7 \times 4 + 6$

Since $7$ does not divide $34$ (remainder $6 \neq 0$ ): $\boxed{37 \not\equiv 3 \pmod{7}}$

Verification:

$37 \bmod 7 = 2$ (since $37 = 7 \times 5 + 2$ )
$3 \bmod 7 = 3$
$2 \neq 3$ , confirmed NOT congruent.

Note: the difference method gives the correct result, and the check $37 \bmod 7 = 2$ confirms it. (The remainder of $34 \div 7$ is $6$ .)

Part 2: Is $-29 \equiv 5 \pmod{17}$ ?

Check if $17 \mid (-29 - 5)$ : $-29 - 5 = -34$ $-34 = 17 \times (-2) + 0$

Since $17$ divides $-34$ exactly: $\boxed{-29 \equiv 5 \pmod{17}}$

Verification:

$-29 = 17 \times (-2) + 5 \Rightarrow -29 \bmod 17 = 5$
$5 \bmod 17 = 5$
$5 = 5$ , confirmed congruent.

Summary

Check	Difference	Divisible by $m$ ?	Result
$37 \equiv 3 \pmod 7$	$34$	No ( $34 = 7\cdot4+6$ )	$37 \not\equiv 3 \pmod 7$
$-29 \equiv 5 \pmod{17}$	$-34$	Yes ( $-34 = 17\cdot(-2)$ )	$-29 \equiv 5 \pmod{17}$

Congruent Modulo: Definition and Examples

Given Data

Check 1: Is $37 \equiv 3 \pmod{7}$?
Check 2: Is $-29 \equiv 5 \pmod{17}$?

STEP 1 - Definition

If $a$ and $b$ are integers and $m$ is a positive integer, then $a$ is congruent to $b$ modulo $m$ if $m$ divides $(a - b)$.

Notation: $$a \equiv b \pmod{m}$$

If they are not congruent, we write $a \not\equiv b \pmod{m}$.

Equivalent test: $a \equiv b \pmod{m}$ if and only if $a \bmod m = b \bmod m$.

STEP 2 - Solve

Part 1: Is $37 \equiv 3 \pmod 7$?

Check if $7 \mid (37 - 3)$: $$37 - 3 = 34$$ $$34 = 7 \times 4 + 6$$

Since $7$ does not divide $34$ (remainder $6 \neq 0$): $$\boxed{37 \not\equiv 3 \pmod{7}}$$

Verification:

$37 \bmod 7 = 2$ (since $37 = 7 \times 5 + 2$)
$3 \bmod 7 = 3$
$2 \neq 3$, confirmed NOT congruent.

Note: the difference method gives the correct result, and the check $37 \bmod 7 = 2$ confirms it. (The remainder of $34 \div 7$ is $6$.)

Part 2: Is $-29 \equiv 5 \pmod{17}$?

Check if $17 \mid (-29 - 5)$: $$-29 - 5 = -34$$ $$-34 = 17 \times (-2) + 0$$

Since $17$ divides $-34$ exactly: $$\boxed{-29 \equiv 5 \pmod{17}}$$

Verification:

$-29 = 17 \times (-2) + 5 \Rightarrow -29 \bmod 17 = 5$
$5 \bmod 17 = 5$
$5 = 5$, confirmed congruent.

Summary

Check	Difference	Divisible by $m$?	Result
$37 \equiv 3 \pmod 7$	$34$	No ($34 = 7\cdot4+6$)	$37 \not\equiv 3 \pmod 7$
$-29 \equiv 5 \pmod{17}$	$-34$	Yes ($-34 = 17\cdot(-2)$)	$-29 \equiv 5 \pmod{17}$

85 marksHideAnswer
Define network flow with example. What are saturated edge, unsaturated edge and slack value? [5]
A network flow (also called a transport network) is a directed graph G = (V, E) where each edge e is associated with a capacity C(e) 0, and two special nodes: - Source node (S): has only outgoing flow - Sink/Destination node (D): has onl...
95 marksPropositional EquivalencesHideAnswer
Give an example of tautology and contradiction. Show that implication and contrapositive are equivalence. [5]
--- A tautology is a compound proposition that is always true, regardless of the truth values of its component propositions. Example: $p \lor \neg p \quad \text{("p or not p")}$ $p$ $\neg p$ $p \lor \neg p$ ----------------------------...
--- A tautology is a compound proposition that is always true, regardless of the truth values of its component propositions. Example: $$p \lor \neg p \quad \text{("p or not p")}$$ $p$ $\neg p$ $p \lor \neg p$ ----------------------------...

105 marksProof MethodsAnswer

What is direct proof? Give a direct proof that if m and n are both perfect squares, then mn is also a perfect square. [5]

Direct Proof: Product of Two Perfect Squares is a Perfect Square

Definition: Direct Proof

A direct proof is a method of proving a statement of the form "if P then Q" by assuming that P is true and then, using definitions, axioms, theorems, and logical reasoning step by step, showing that Q must also be true.

In other words, we start from the hypothesis and proceed forward through a chain of logical deductions until we reach the conclusion.

Definition: Perfect Square

An integer $n$ is called a perfect square if there exists an integer $k$ such that: $n = k^2$

Examples: $1, 4, 9, 16, 25, \ldots$ are perfect squares.

Theorem

If $m$ and $n$ are both perfect squares, then $mn$ is also a perfect square.

Direct Proof

Assume (hypothesis) that $m$ and $n$ are both perfect squares.

Step 1: Since $m$ is a perfect square, by definition there exists an integer $a$ such that: $m = a^2$

Step 2: Since $n$ is a perfect square, by definition there exists an integer $b$ such that: $n = b^2$

Step 3: Compute the product $mn$ : $mn = a^2 \cdot b^2$

Step 4: Using the properties of exponents and multiplication: $mn = a^2 \cdot b^2 = (ab)^2$

Step 5: Let $c = ab$ . Since $a$ and $b$ are integers, their product $c = ab$ is also an integer.

Step 6: Therefore: $mn = c^2$

where $c$ is an integer.

Conclusion: By the definition of a perfect square, $mn$ is a perfect square. $\blacksquare$

Summary Table

Step	Statement	Reason
1	$m = a^2$ for some integer $a$	$m$ is a perfect square (hypothesis)
2	$n = b^2$ for some integer $b$	$n$ is a perfect square (hypothesis)
3	$mn = a^2 b^2$	Substitution
4	$mn = (ab)^2$	Laws of exponents
5	Let $c = ab \in \mathbb{Z}$	Product of integers is an integer
6	$mn = c^2$	Definition of perfect square satisfied

Direct Proof: Product of Two Perfect Squares is a Perfect Square

Definition: Direct Proof

In other words, we start from the hypothesis and proceed forward through a chain of logical deductions until we reach the conclusion.

Definition: Perfect Square

An integer $n$ is called a perfect square if there exists an integer $k$ such that: $$n = k^2$$

Examples: $1, 4, 9, 16, 25, \ldots$ are perfect squares.

Theorem

If $m$ and $n$ are both perfect squares, then $mn$ is also a perfect square.

Direct Proof

Assume (hypothesis) that $m$ and $n$ are both perfect squares.

Step 1: Since $m$ is a perfect square, by definition there exists an integer $a$ such that: $$m = a^2$$

Step 2: Since $n$ is a perfect square, by definition there exists an integer $b$ such that: $$n = b^2$$

Step 3: Compute the product $mn$: $$mn = a^2 \cdot b^2$$

Step 4: Using the properties of exponents and multiplication: $$mn = a^2 \cdot b^2 = (ab)^2$$

Step 5: Let $c = ab$. Since $a$ and $b$ are integers, their product $c = ab$ is also an integer.

Step 6: Therefore: $$mn = c^2$$

where $c$ is an integer.

Conclusion: By the definition of a perfect square, $mn$ is a perfect square. $\blacksquare$

Summary Table

Step	Statement	Reason
1	$m = a^2$ for some integer $a$	$m$ is a perfect square (hypothesis)
2	$n = b^2$ for some integer $b$	$n$ is a perfect square (hypothesis)
3	$mn = a^2 b^2$	Substitution
4	$mn = (ab)^2$	Laws of exponents
5	Let $c = ab \in \mathbb{Z}$	Product of integers is an integer
6	$mn = c^2$	Definition of perfect square satisfied

115 marksNumericalBasics of CountingHideAnswer
What is product rule? How many strings are there of four lowercase letters that have the letter x in them? [5]
Alphabet size: 26 lowercase letters - String length: 4 - Condition: string must contain the letter 'x' (at least once) - Repetition of letters: allowed (standard assumption for such strings) All data required is present. --- Definition...
125 marksRepresenting RelationsHideAnswer
Explain the matrix representation of relations with example. [5]
Let R be a relation from set A = {a₁, a₂, ..., aₘ} to set B = {b₁, b₂, ..., bₙ}. The matrix representation of R is an m × n zero-one matrix MR = [mij] where: $$m{ij} = \begin{cases} 1 & \text{if } (ai, bj) \in R \ 0 & \text{if } (ai, bj...

Keep going

Important questions + predictions

Full syllabus Flashcards and practice

Other papers

2081 paper 2080 paper 2079 paper 2078 paper 2076 paper 2075 paper

Discrete Structures 2080.1 question paper

Shortest Path Problem and Dijkstra's Algorithm

STEP 1 - EXTRACT: Given Data

STEP 2 - SOLVE

Definition: Shortest Path Problem

Dijkstra's Algorithm

Execution (on the assumed edge set)

Final Distance Table

Shortest Path and Length

Shortest Path Problem and Dijkstra's Algorithm

STEP 1 - EXTRACT: Given Data

STEP 2 - SOLVE

Definition: Shortest Path Problem

Dijkstra's Algorithm

Execution (on the assumed edge set)

Final Distance Table

Shortest Path and Length

Congruent Modulo: Definition and Examples

Given Data

STEP 1 - Definition

STEP 2 - Solve

Part 1: Is 37≡3(mod7)37 \equiv 3 \pmod 737≡3(mod7)?

Part 2: Is −29≡5(mod17)-29 \equiv 5 \pmod{17}−29≡5(mod17)?

Summary

Congruent Modulo: Definition and Examples

Given Data

STEP 1 - Definition

STEP 2 - Solve

Part 1: Is $37 \equiv 3 \pmod 7$?

Part 2: Is $-29 \equiv 5 \pmod{17}$?

Summary

Direct Proof: Product of Two Perfect Squares is a Perfect Square

Definition: Direct Proof

Definition: Perfect Square

Theorem

Direct Proof

Summary Table

Direct Proof: Product of Two Perfect Squares is a Perfect Square

Definition: Direct Proof

Definition: Perfect Square

Theorem

Direct Proof

Summary Table

Shortest Path Problem and Dijkstra's Algorithm

STEP 1 - EXTRACT: Given Data

STEP 2 - SOLVE

Definition: Shortest Path Problem

Dijkstra's Algorithm

Execution (on the assumed edge set)

Final Distance Table

Shortest Path and Length

Congruent Modulo: Definition and Examples

Given Data

STEP 1 - Definition

STEP 2 - Solve

Part 1: Is 37≡3(mod7)37 \equiv 3 \pmod 737≡3(mod7)?

Part 2: Is −29≡5(mod17)-29 \equiv 5 \pmod{17}−29≡5(mod17)?

Summary

Direct Proof: Product of Two Perfect Squares is a Perfect Square

Definition: Direct Proof

Definition: Perfect Square

Theorem

Direct Proof

Summary Table

Part 1: Is $37 \equiv 3 \pmod 7$ ?

Part 2: Is $-29 \equiv 5 \pmod{17}$ ?

Part 1: Is $37 \equiv 3 \pmod 7$ ?

Part 2: Is $-29 \equiv 5 \pmod{17}$ ?