Discrete Structure (CT 551) - Past Exam Questions Analysis

Contents
1 Logic and Proofs 1
1.1 Using Rules of Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Proof by Contradiction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Tableau Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.5 Summary and Study Tips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Automata Theory 3
2.1 Design Finite State Automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Regular Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Grammar and Automata Conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.4 Summary and Study Tips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3 Recurrence Relations 5
3.1 Solving Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2 Summary and Study Tips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

4 Graph Theory 5
4.1 Dijkstra’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.2 Euler and Hamilton Paths/Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.3 Graph Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.4 Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.5 Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.6 Max-flow Min-cut Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4.7 Summary and Study Tips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

Overview
This document organizes past exam questions for the Discrete Structure (CT 551) subject from
Tribhuvan University, Institute of Engineering, Examination Control Division, spanning 2068 to 2080
(Regular and Back exams). Questions are categorized by syllabus topics: Logic and Proofs, Automata
Theory, Recurrence Relations, and Graph Theory. Each section provides question types with detailed
descriptions, mark ranges, frequencies, pitfalls, and examples from specific years. Summary tables and
study tips are included to optimize preparation for high exam performance. The document uses advanced
LaTeX formatting for clarity and professionalism.

1 Logic and Proofs

1.1 Using Rules of Inference
• Title: Derive a conclusion using rules of inference
• Mark Range: 8–10 marks

• Exam Type: Regular and Back

• Frequency: 13/13 years

1
 • Description: Given a set of hypotheses, derive a conclusion step-by-step using rules like modus
ponens or modus tollens, justifying each step.
• Pitfalls: Skipping steps, misapplying rules, or not providing justifications.

• Examples:
– 2080 Chaitra (Regular, 8 marks, p. 1): ”Using rules of inference, derive the conclusion
to the given hypothesis: ‘If today is Sunday then I will have a test in Discrete Structure
and Microprocessor. If my Microprocessor instructor is busy then I will not have a test in
Microprocessor. Today is Sunday and my Microprocessor instructor is busy’. Conclusion: ‘I
will have a test in Discrete Structure’. Show each step and give reasons for those steps.”
– 2079 Chaitra (Regular, 8 marks, p. 3): ”Construct an argument using rules of inference
to show that the hypotheses ‘if it does not rain or if it is not foggy, then the sailing race will be
held and the lifesaving demonstration will go on’, ‘If the sailing race is held, then the trophy
will be awarded’, and ‘The trophy was not awarded’ imply the conclusion ‘It rained’.”
– 2078 Chaitra (Regular, 8 marks, p. 4): ”Use rules of inference to show that the hy-
pothesis ‘No humans can fly.’, ‘Tweety is a bird or a human.’, ‘Tweety can fly’ implies the
conclusion ‘Tweety is a bird’.”

1.2 Mathematical Induction

• Title: Prove a statement using mathematical induction
• Mark Range: 8 marks
• Exam Type: Regular and Back

• Frequency: 12/13 years

• Description: Prove a statement for all positive or non-negative integers using a base case and
inductive step, often involving summation or divisibility.
• Pitfalls: Weak base case, incorrect inductive assumption, or algebraic errors.

• Examples:
– 2080 Chaitra (Regular, 8 marks, p. 1): ”Use mathematical induction to show that
12 + 22 + . . . + n2 = n(n+1)(2n+1)
6 where n is a positive integer.”
– 2079 Chaitra (Regular, 8 marks, p. 3): ”Use mathematical induction to prove that
7n+2 + 82n+1 is divisible by 57 for every nonnegative integer n.”
– 2077 Chaitra (Regular, 8 marks, p. 5): ”Use mathematical induction to prove: 13 +
23 + 33 + . . . + n3 = n2 (n + 1)2 /4 for all positive integer n.”

1.3 Proof by Contradiction

• Title: Prove a statement using contradiction

• Mark Range: 3–8 marks

• Exam Type: Regular and Back
• Frequency: 6/13 years

• Description: Prove a statement (e.g., irrationality) by assuming its negation and deriving a logical
contradiction.
• Pitfalls: Unclear initial assumption or weak contradiction.
• Examples:
√
– 2080 Chaitra (Regular, 3 marks, p. 1): ”Prove that 2 is irrational using proof by
contradiction.”

2
 √
– 2077 Chaitra (Regular, 8 marks, p. 5): ”Prove that 2 is irrational by giving a proof
by contradiction.”
– 2073 Bhadra (Regular, 8 marks, p. 17): ”Prove that if n is an integer and 3n + 2 is
odd, then n is odd.”

1.4 Tableau Method

• Title: Draw a tableau for a formula set
• Mark Range: 4–8 marks

• Exam Type: Regular and Back

• Frequency: 5/13 years
• Description: Construct a semantic tableau to test the consistency or satisfiability of a set of
logical formulas.

• Pitfalls: Incorrect rule application or incomplete branching.

• Examples:
– 2078 Chaitra (Regular, 8 marks, p. 4): ”Draw Tableau for formula set: ϕ = {(P ∧ Q) ∨
R, P → ¬Q, ¬P }”
– 2076 Bhadra (Regular, 8 marks, p. 9): ”Draw Tableau for formula set: Φ = {P →
Q ∨ R, P ∨ ¬R, ¬(Q ∨ R)}”

1.5 Summary and Study Tips

Question Type Frequency

Rules of Inference 13/13
Mathematical Induction 12/13
Proof by Contradiction 6/13
Tableau Method 5/13

Trend: Rules of inference and mathematical induction are tested every year, while contradiction and
tableau are less frequent.
Study Tips: Prioritize mastering rules of inference (e.g., modus ponens) and
√ mathematical induction
with examples like n2 sums. Practice at least 3 contradiction proofs (e.g., 2 irrationality). Tableau
can be secondary if time is limited.

2 Automata Theory
2.1 Design Finite State Automata
• Title: Design a DFA or NFA for a given language
• Mark Range: 6–8 marks
• Exam Type: Regular and Back

• Frequency: 12/13 years

• Description: Construct DFA or NFA for languages defined by patterns (e.g., ending with ”ing”),
including transition diagrams and tables.
• Pitfalls: Missing states or incorrect transitions.

• Examples:

3
 – 2080 Chaitra (Regular, 6 marks, p. 1): ”Draw a transition diagram for Deterministic
and Non-deterministic finite automata which accept a string containing ’ing’ at the end of a
string in a string of {a − z}, e.g., ’anything’ but not ’anywhere’.”
– 2079 Chaitra (Regular, 8 marks, p. 3): ”Design a Finite State automata that accepts
precisely those strings over {a, b} that contains the substring ’bba’.”
– 2073 Bhadra (Regular, 8 marks, p. 17): ”Design a finite state automation that accepts
precisely those strings over {a, b} that end with substring aa.”

2.2 Regular Expressions

• Title: Write a regular expression for a language
• Mark Range: 2–8 marks
• Exam Type: Regular and Back

• Frequency: 7/13 years

• Description: Provide a regular expression for a specified language (e.g., at most 2 ’a’s).
• Pitfalls: Missing cases or incorrect use of operators (*, +, ∪).
• Examples:

– 2079 Chaitra (Regular, 8 marks, p. 3): ”Give regular expressions for following language
L = {w ∈ {a, b}∗ : contains at-most 2 ’a’}”
– 2078 Chaitra (Regular, 2 marks, p. 4): ”Given a Language L = {w ∈ {a, b}∗ :
w ends with ’ba’}. Write a regular expression.”

2.3 Grammar and Automata Conversion

• Title: Convert a regular grammar to NFA/DFA
• Mark Range: 8 marks

• Exam Type: Regular and Back

• Frequency: 10/13 years
• Description: Build an NFA from a regular grammar and optionally convert it to a DFA.

• Pitfalls: Incorrect mapping of productions to transitions or missing epsilon moves.

• Examples:
– 2080 Chaitra (Regular, 8 marks, p. 1): ”Construct a Non-deterministic Finite Automata
equivalent to the given regular grammar and convert it into Deterministic Finite Automata.”
– 2079 Chaitra (Regular, 8 marks, p. 3): ”Given a grammar make NDFA and convert it
to equivalent DFA: A → sA, A → bB, A → b, P → sP, P → bA, P → s”

2.4 Summary and Study Tips

Question Type Frequency

Design DFA/NFA 12/13
Regular Expressions 7/13
Grammar Conversion 10/13

Trend: DFA/NFA design and grammar conversion are highly consistent; regular expressions are
moderately frequent.
Study Tips: Focus on designing automata for patterns (e.g., ”ing” endings) and converting grammars
to DFA. Practice regular expressions with examples like ”ends with ba”.

4
3 Recurrence Relations
3.1 Solving Recurrence Relations
• Title: Solve a linear recurrence relation
• Mark Range: 8 marks
• Exam Type: Regular and Back

• Frequency: 12/13 years

• Description: Find the general solution to a recurrence relation (homogeneous or non-homogeneous)
using characteristic equations and initial conditions.
• Pitfalls: Errors in characteristic roots or mishandling non-homogeneous terms (e.g., 3n ).

• Examples:
– 2080 Chaitra (Regular, 8 marks, p. 1): ”Find all the solution of recurrence relation:
an = 5an−2 − 16an−4 with initial conditions a0 = 1, a1 = 4, a2 = 28 and a3 = 32.”
– 2079 Chaitra (Regular, 8 marks, p. 3): ”Find all solutions of the recurrence relation:
an = 2an−1 + 2n2 with initial condition a1 = 4.”
– 2073 Bhadra (Regular, 8 marks, p. 17): ”Find all the solutions of recurrence relation:
an = 7an−1 − 12an−2 + 3n with initial conditions a0 = 1 and a1 = 4.”

3.2 Summary and Study Tips

Question Type Frequency

Solve Recurrence Relations 12/13

Trend: Consistently tested with a mix of homogeneous and non-homogeneous relations.

Study Tips: Master characteristic equations for homogeneous cases and particular solutions for terms
like n2 or 3n . Practice with varied initial conditions.

4 Graph Theory
4.1 Dijkstra’s Algorithm
• Title: Find the shortest path using Dijkstra’s algorithm
• Mark Range: 8 marks
• Exam Type: Regular and Back

• Frequency: 12/13 years

• Description: Apply Dijkstra’s algorithm to a weighted graph, showing steps and the final path.
• Pitfalls: Incorrect distance updates or vertex selection.
• Examples:

– 2080 Chaitra (Regular, 8 marks, p. 1): ”Use Dijkstra’s algorithm to find the cost of
shortest path from a to z and also find the shortest path.”
– 2079 Chaitra (Regular, 8 marks, p. 3): ”Use Dijkstra’s algorithm to find the length of
shortest path from vertex a to vertex e in the following weighted graph.”
– 2071 Bhadra (Regular, 8 marks, p. 24): ”Use Dijkstra’s algorithm to find the length of
the shortest path between the vertices a and z in the weighted graph displayed below.”

5
4.2 Euler and Hamilton Paths/Circuits
• Title: Explain Euler and Hamilton paths/circuits
• Mark Range: 4–8 marks
• Exam Type: Regular and Back
• Frequency: 8/13 years
• Description: Define concepts, state conditions, and sometimes identify in graphs.
• Pitfalls: Confusing Euler and Hamilton conditions.
• Examples:
– 2080 Chaitra (Regular, 8 marks, p. 1): ”Explain the Euler circuit and Hamilton circuit
with an example. State if there is/are any necessary and the sufficient conditions for a graph
to have Euler’s and Hamilton’s paths and circuits.”
– 2071 Bhadra (Regular, 7 marks, p. 24): ”Explain the Hamiltonian path and Hamiltonian
circuit with the help of a diagram. State the necessary and sufficient conditions for Euler
circuits and paths.”

4.3 Graph Coloring

• Title: Define graph coloring and find chromatic number
• Mark Range: 2–8 marks
• Exam Type: Regular and Back
• Frequency: 9/13 years
• Description: Define coloring and compute chromatic numbers for graphs like Kn or Q3 .
• Pitfalls: Miscalculating chromatic numbers.
• Examples:
– 2079 Chaitra (Regular, 4 marks, p. 3): ”Draw clear and labeled diagrams of Complete
graph with 6 Vertices (K6 ) and 3-dimensional Hypercube (Q3 ). Also write their Chromatic
Numbers.”
– 2073 Bhadra (Regular, 8 marks, p. 17): ”Draw the figure for the complete graph with 5
vertices (K5 ). Define the term graph coloring and the chromatic number of a graph in graph
coloring. What is the chromatic number of the complete graph K5 and complete bipartite
graph K3,3 ?”

4.4 Planar Graphs

• Title: Prove planarity or non-planarity of graphs
• Mark Range: 4–6 marks
• Exam Type: Regular and Back
• Frequency: 7/13 years
• Description: Use Euler’s formula or edge counts to prove graphs like K3,3 are non-planar.
• Pitfalls: Misapplying Euler’s formula.
• Examples:
– 2079 Chaitra (Regular, 4 marks, p. 3): ”Are the graphs K6 and Q3 planar? Give proof
for your answer.”
– 2078 Chaitra (Regular, 4 marks, p. 4): ”Prove that K3,3 is non-planar graph.”

6
4.5 Spanning Trees
• Title: Define and find spanning trees

• Mark Range: 4–8 marks

• Exam Type: Regular and Back
• Frequency: 10/13 years
• Description: Define spanning trees and find minimal ones using Kruskal’s or Prim’s algorithms.

• Pitfalls: Incorrect algorithm application.

• Examples:
– 2080 Chaitra (Regular, 8 marks, p. 2): ”Define Binary Tree, M-ary tree and Spanning
tree. Find the minimal spanning tree from the graph given below.”
– 2079 Chaitra (Regular, 2 marks, p. 3): ”Define Spanning Tree with example.”

4.6 Max-flow Min-cut Theorem

• Title: Explain the Max-flow Min-cut Theorem

• Mark Range: 3–4 marks

• Exam Type: Regular and Back
• Frequency: 10/13 years
• Description: State and explain the theorem, often as a short note.

• Pitfalls: Vague explanations or missing key ideas.

• Examples:
– 2080 Chaitra (Regular, 4 marks, p. 2): ”Write short notes on: a) Max-flow min-cut
theorem”
– 2079 Chaitra (Regular, 4 marks, p. 3): ”Write short notes on: a) Max Flow and Min
cut Theroem”

4.7 Summary and Study Tips

Question Type Frequency

Dijkstra’s Algorithm 12/13
Euler and Hamilton 8/13
Graph Coloring 9/13
Planar Graphs 7/13
Spanning Trees 10/13
Max-flow Min-cut 10/13

Trend: Dijkstra’s algorithm and spanning trees are highly frequent; Euler/Hamilton and coloring
are common.
Study Tips: Master Dijkstra’s algorithm with weighted graphs and spanning tree algorithms (Kruskal’s).
Review conditions for Euler/Hamilton and chromatic numbers for Kn .