IOE PapersTU
PYQs & Syllabus Archive
ENCT 251Bachelor in Electronics, Communication and Information Engineering · Semester 42 Papers Available

Discrete Structure

Past examination question papers and complete curriculum syllabus for Discrete Structure (ENCT 251), Bachelor in Electronics, Communication and Information Engineering Semester 4 under Institute of Engineering (IOE), Tribhuvan University.

Past Question Papers (PDF)

Switch tabs to view different exam papers
Available Papers:

4th-sem_Discrete Structure.pdf

IOE Past Examination Paper

Download PDF
Served via fast CDN. Read in full view or download for offline study.
Drive Mirror ↗Direct Download ↓

Document information: This past examination paper is identified as an IOE/TU academic document and was cataloged from a public Google Drive archive. This independent website did not create the examination paper and is not affiliated with TU or IOE.

Rights holders can request correction or removal by emailing subeshgaming@gmail.com with this page URL and supporting details.

Most Frequently Asked Questions

Top recurring IOE board exam questions for Discrete Structure with verified mark schemes, formula notation, and recurrence frequency.

Showing 30 of 30 top repeated questions

Logic and Induction

7 Questions
#1Repeated 2 Times[2 Marks]Logic and Induction
State the converse, contrapositive and inverse of the conditional statement: "My insurance company will pay me only if the flood destroys my house or the fire destroys my house".
Appeared in:2083 Baishakh2082 Bhadra
#2Repeated 2 Times[6 Marks]Logic and Induction
Show that $(p \to q) \land (p \to r)$ is logically equivalent to $p \to (q \land r)$ using truth tables and using laws of logical equivalence.
Appeared in:2082 Kartik2081 Chaitra
#3Repeated 2 Times[6 Marks]Logic and Induction
Using mathematical induction, prove that $1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}$ for all positive integers $n \ge 1$.
Appeared in:2082 Kartik2080 Chaitra
#4Repeated 2 Times[6 Marks]Logic and Induction
Using mathematical induction, prove that $n^3 - n$ is divisible by 6 for every positive integer $n$.
Appeared in:2081 Chaitra2079 Chaitra
#5Repeated 1 Times[4 Marks]Logic and Induction
Using mathematical induction show that $1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}$.
Appeared in:2083 Baishakh
#6Repeated 1 Times[3 Marks]Logic and Induction
Use the Principle of Mathematical Induction to verify that, for any positive integer $n$, $n^3 + 2n$ is divisible by 3.
Appeared in:2082 Bhadra
#7Repeated 1 Times[5 Marks]Logic and Induction
Using rules of inferences, show that the hypotheses "If you send me an e-mail message, then I will finish writing the program", "If you do not send me an e-mail message, then I will go to sleep early", and "If I go to sleep early, then I will wake up feeling refreshed" lead to the conclusion "If I do not finish writing the program, then I will wake up feeling refreshed". Show each step and give reasons.
Appeared in:2082 Bhadra

Proof Techniques

4 Questions
#1Repeated 2 Times[6 Marks]Proof Techniques
Prove by direct proof and contraposition: If $n$ is an integer and $3n + 2$ is odd, then $n$ is odd.
Appeared in:2082 Kartik2081 Chaitra
#2Repeated 2 Times[6 Marks]Proof Techniques
State the Pigeonhole Principle and Generalized Pigeonhole Principle. Show that in any group of 367 people, there must be at least two who share the same birthday.
Appeared in:2082 Shrawan2078 Bhadra
#3Repeated 1 Times[3 Marks]Proof Techniques
Prove that $\sqrt{2} + \sqrt{3}$ is irrational using proof by contradiction.
Appeared in:2083 Baishakh
#4Repeated 1 Times[4 Marks]Proof Techniques
Prove that $\sqrt{2}$ is irrational by giving a proof by contradiction.
Appeared in:2082 Kartik

Automata Theory, Regular Language and Grammar

6 Questions
#1Repeated 2 Times[8 Marks]Automata Theory, Regular Language and Grammar
Design a Deterministic Finite Automaton (DFA) that accepts the language $L = \{w \in \{0, 1\}^* \mid w \text{ contains an even number of 0s and an odd number of 1s}\}$. Draw the state transition diagram and transition table.
Appeared in:2082 Kartik2081 Chaitra
#2Repeated 2 Times[8 Marks]Automata Theory, Regular Language and Grammar
Design a Non-deterministic Finite Automaton (NFA) for the regular expression $(0+1)^*01$ and convert the NFA to an equivalent DFA using subset construction method.
Appeared in:2082 Kartik2080 Chaitra
#3Repeated 2 Times[6 Marks]Automata Theory, Regular Language and Grammar
Explain Chomsky hierarchy of formal grammars (Type 0, Type 1, Type 2, Type 3). Define Context-Free Grammar (CFG) and write a CFG for the language $L = \{a^n b^n \mid n \ge 1\}$.
Appeared in:2081 Chaitra2079 Baishakh
#4Repeated 1 Times[7 Marks]Automata Theory, Regular Language and Grammar
Give formal definition of DFA. Design a deterministic finite automata that accepts all the strings that does not start with aba over $\Sigma = \{a, b\}$. Also check if string $w_1 = \text{abbabab}$ and $w_2 = \text{abaabaaab}$ are accepted or rejected.
Appeared in:2082 Bhadra
#5Repeated 1 Times[7 Marks]Automata Theory, Regular Language and Grammar
Write a regular expression for the language that accepts all strings that do not contain three consecutive b over $\Sigma = \{a, b\}$. Write a CFG that generates palindrome strings of even length over $\Sigma = \{0, 1\}$, and generate the string $w = 10100101$ using rightmost derivation with its parse tree.
Appeared in:2083 Baishakh
#6Repeated 1 Times[3 Marks]Automata Theory, Regular Language and Grammar
Show that regular language is closed under Kleene star and complement operation.
Appeared in:2083 Baishakh

Recurrence Relation and Algorithmic Analysis

6 Questions
#1Repeated 2 Times[6 Marks]Recurrence Relation and Algorithmic Analysis
Solve the linear homogeneous recurrence relation: $a_n - 7a_{n-1} + 12a_{n-2} = 0$ with initial conditions $a_0 = 2, a_1 = 7$.
Appeared in:2082 Kartik2081 Chaitra
#2Repeated 2 Times[8 Marks]Recurrence Relation and Algorithmic Analysis
Solve the non-homogeneous recurrence relation: $a_n - 5a_{n-1} + 6a_{n-2} = 2^n$ with initial conditions $a_0 = 1, a_1 = 2$.
Appeared in:2082 Kartik2080 Chaitra
#3Repeated 2 Times[6 Marks]Recurrence Relation and Algorithmic Analysis
State the Master Theorem for divide-and-conquer recurrences. Use the Master Theorem to find the asymptotic complexity of: (i) $T(n) = 4T(n/2) + n$, (ii) $T(n) = 2T(n/2) + n \log n$.
Appeared in:2081 Chaitra2078 Bhadra
#4Repeated 1 Times[4 Marks]Recurrence Relation and Algorithmic Analysis
Solve the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2} + 2^n$ with initial conditions $a_0 = 1$ and $a_1 = 4$.
Appeared in:2083 Baishakh
#5Repeated 1 Times[4 Marks]Recurrence Relation and Algorithmic Analysis
Derive the explicit formula for the Fibonacci series using recurrence relation.
Appeared in:2082 Bhadra
#6Repeated 1 Times[8 Marks]Recurrence Relation and Algorithmic Analysis
Set up a recurrence relation for the sequence representing the Tower of Hanoi puzzle and find its solution.
Appeared in:2082 Kartik

Graph Theory and Tree

7 Questions
#1Repeated 2 Times[6 Marks]Graph Theory and Tree
Define isomorphic graphs. Check whether the two given graphs are isomorphic or not by comparing number of vertices, edges, degree sequences, and adjacency matrices.
Appeared in:2082 Kartik2081 Chaitra
#2Repeated 2 Times[8 Marks]Graph Theory and Tree
Differentiate between Eulerian graph and Hamiltonian graph. State the necessary and sufficient condition for a connected graph to be Eulerian. Check whether the complete bipartite graph $K_{3,3}$ and $K_{2,4}$ are Eulerian.
Appeared in:2082 Kartik2080 Chaitra
#3Repeated 2 Times[6 Marks]Graph Theory and Tree
Explain graph coloring and chromatic number $\chi(G)$. State the Four Color Theorem. Find the chromatic number of $K_n$, $C_n$, and $K_{m,n}$.
Appeared in:2081 Chaitra2079 Chaitra
#4Repeated 1 Times[4 Marks]Graph Theory and Tree
State and prove Euler's Formula for planar graph.
Appeared in:2082 Bhadra
#5Repeated 1 Times[6 Marks]Graph Theory and Tree
State Dirac's and Ore's theorem. Is $K_5$ and $K_{3,3}$ planar graph? Justify your answer.
Appeared in:2083 Baishakh
#6Repeated 1 Times[5 Marks]Graph Theory and Tree
Define wheel graph. Draw 3-dimensional hypercube ($Q_3$). Show that the total number of edges in any complete graph is $\frac{n(n-1)}{2}$.
Appeared in:2082 Bhadra
#7Repeated 1 Times[5 Marks]Graph Theory and Tree
Find the shortest distance from vertex A to all other vertices using Dijkstra's algorithm on the given weighted graph.
Appeared in:2082 Bhadra

Curriculum Syllabus & Course Topics

Sourced from TU curriculum portal
Full Syllabus (PDF)
Chapter-wise Units & Micro-Syllabus Topics (5 Units)

  1. 1. Logic and Induction

    • 1.1Review of set theory, relation and function
    • 1.2Proposition, connectives in proposition, types of propositions, truth function and propositional logic
    • 1.3Expressing statements in logic propositional logic, rules of inference in propositional logic, validity of an argument, methods of tableaux
    • 1.4Predicate logic and quantification, informal deduction in predicate logic

  2. 2. Proof Techniques

    • 2.1Formal proofs and informal proofs, mathematical reasoning- direct proof and indirect proof (Proof by contradiction and proof by contraposition)
    • 2.2Elementary induction and complete induction, strong induction
    • 2.3Proof by counter example, vacuous and trivial proofs, proof by cases, mistakes in proof

  3. 3. Automata Theory, Regular Language and Grammar

    • 3.1Alphabet, string, string operations and language, introduction to finite automata
    • 3.2Deterministic finite automata (DFA), representation and language of DFA
    • 3.3Non deterministic finite automata (NFA), equivalence of DFA and NFA
    • 3.4Regular expressions and its characteristics, regular language and its properties
    • 3.5Equivalence of regular expression and finite automata
    • 3.6Context free grammar and context free language

  4. 4. Recurrence Relation and Algorithmic Analysis

    • 4.1Recurrence relations, recurrence relation for tower of Hanoi (TOH) and Fibonacci series, solving linear recurrence relations (Homogeneous and non-homogeneous)
    • 4.2Algorithm and its properties, asymptotic notation of algorithm
    • 4.3Linear and binary search and their analysis; Bubble and insertion sorting and their analysis

  5. 5. Graph Theory and Tree

    • 5.1Graphs basics, graph terminologies, graph types (Directed, un-directed, simple, weighted, regular, complete, bipartite, planar graph) and special graphs
    • 5.2Subgraphs, graph representation, connectivity in graphs and its components, strongly and weakly connected graphs
    • 5.3Paths and circuits, Euler path and circuit, Hamiltonian path and circuit
    • 5.4Shortest path algorithm (Dijkstra’s algorithm), graph coloring and four color theorem, applications of graph coloring.
    • 5.5Graph as network, maximal flows and minimal cuts, the max flow-min cut theorem
    • 5.6Introduction and applications, tree traversals, spanning trees, minimum spanning trees (Prim’s and Kruskal’s algorithm)

Examination Scheme & Marks Distribution

Evaluation Structure

  • Final Board Theory Exam: 60 Marks (Pass mark: 24)
  • Internal Assessment: 40 Marks (Pass mark: 16)
  • Practical / Lab Exam: 25 or 50 Marks (Continuous lab evaluation + viva, where applicable)

* This is the general current IOE 60/40 scheme; verify course-specific details in the syllabus above.

Exam Preparation Guidelines

  • Review the 2 available past examination papers to identify recurring patterns, core problem types, and chapter weightage.
  • Cross-reference key answers with official syllabus units, standard textbooks, and lecture notes.
  • Structure answers with labeled diagrams, concise bullet points, and highlight final answers in numerical solutions.

Frequently Asked Questions (Discrete Structure)

Q: How can I download Discrete Structure past question papers?

You can preview or download the Discrete Structure question papers (PDF) directly using the built-in viewer on this page with zero redirects or paywalls.

Q: What is the pass mark for Discrete Structure?

The general current scheme is a 60-mark final theory exam and a 40-mark internal assessment, with pass marks of 24 and 16. Verify the course-specific syllabus above.

Q: Where can I find the complete syllabus for this subject?

The available chapter-wise syllabus and topic breakdown is indexed in the Syllabus section above, with links to the curriculum PDF source.

Authentic IOE Past Papers
Free Direct PDF Download
Curriculum Syllabus & Marking Scheme