TABFlux

Home Courses Universities Programs Forum

© 2026 TABFlux. All rights reserved. Built for students, by students.

Forum Privacy Policy Terms of Service Contact Us Contributors

Discrete Structure

Discrete Structures introduces the mathematical foundations of computer science. It covers logic, sets, relations, functions, combinatorics, graphs, and trees, providing essential tools for problem-solving, algorithm design, and understanding theoretical concepts in computing.

Select University

Select Program

BSC-CSIT BDS BCA-NEW BIT BEI-NEW

TabFlux . Discrete Structure . TU . BEI-NEW

Discrete Structure

0%

Course Title: Discrete Structure

Course No: ENCT 251

Nature of the Course: THEORY

Semester: 4

Full Marks: 40 + 60

Pass Marks: 16 + 24

Credit Hours: 3

Course Description

Course Objectives

Course Contents

1. Logic and Induction

8 hrs10 marks

1.1. Review of set theory, relation and function

1.2. Proposition, connectives in proposition, types of propositions, truth function and propositional logic

1.3. Expressing statements in logic propositional logic, rules of inference in propositional logic, validity of an argument, methods of tableaux

1.4. Predicate logic and quantification, informal deduction in predicate logic

2. Proof Techniques

5 hrs7 marks

2.1. Formal proofs and informal proofs, mathematical reasoning- direct proof and indirect proof (Proof by contradiction and proof by contraposition)

2.2. Elementary induction and complete induction, strong induction

2.3. Proof by counter example, vacuous and trivial proofs, proof by cases, mistakes in proof

3. Automata Theory, Regular Language and Grammar

10 hrs14 marks

3.1. Alphabet, string, string operations and language, introduction to finite automata

3.2. Deterministic finite automata (DFA), representation and language of DFA

3.3. Non deterministic finite automata (NFA), equivalence of DFA and NFA

3.4. Regular expressions and its characteristics, regular language and its properties

3.5. Equivalence of regular expression and finite automata

3.6. Context free grammar and context free language

4. Recurrence Relation and Algorithmic Analysis

7 hrs9 marks

4.1. Recurrence relations, recurrence relation for tower of Hanoi (TOH) and Fibonacci series, solving linear recurrence relations (Homogeneous and non-homogeneous)

4.2. Algorithm and its properties, asymptotic notation of algorithm

4.3. Linear and binary search and their analysis; Bubble and insertion sorting and their analysis

5. Graph Theory and Tree

15 hrs20 marks

5.1. Graphs basics, graph terminologies, graph types (Directed, un-directed, simple, weighted, regular, complete, bipartite, planar graph) and special graphs

5.2. Subgraphs, graph representation, connectivity in graphs and its components, strongly and weakly connected graphs

5.3. Paths and circuits, Euler path and circuit, Hamiltonian path and circuit

5.4. Shortest path algorithm (Dijkstra's algorithm), graph coloring and four color theorem, applications of graph coloring

5.5. Graph as network, maximal flows and minimal cuts, the max flow-min cut theorem

5.6. Introduction and applications, tree traversals, spanning trees, minimum spanning trees (Prim's and Kruskal's algorithm)

Laboratory Works

Reference Books

1.Rosen, K. H. (2019). Discrete Mathematics and Its Applications. United Kingdom: McGraw-Hill.
2.Johnsonbaugh, R. (2007). Discrete Mathematics. Prentice Hall Inc.
3.Chartrand, G., Oellermann, O. R. (1993). Applied and Algorithmic Graph Theory. Singapore: McGraw-Hill.
4.Lewis, H. R., Papadimitriou, C. H. (1981). Elements of the Theory of Computation. United Kingdom: Prentice-Hall.
5.Cormen, T. H., Leiserson, C. E., Stein, C., Rivest, R. L. (2009). Introduction to Algorithms, Third Edition. France: MIT Press.

Notes:

Source:

Discrete Structure provides basic understanding in discrete mathematics and finite state machine. It builds fundamental and conceptual clarity in logic, reasoning, proof, recurrence relation, graph theory, theory of automata and algorithmic analysis.

The objective of this course is to provide basic understanding in discrete mathematics and finite state machine. It also emphasizes to build fundamental and conceptual clarity in the area of logic, reasoning, proof, recurrence relation, graph theory, theory of automata and algorithmic analysis.

This syllabus follows the official BEI curriculum of Tribhuwan University. In case of any doubt or revision, the university's published syllabus shall be considered authoritative. https://ioe.tu.edu.np/pages/electronics-engineering-curriculum-structure-2660