CT-22 Discrete
Mathematical Structures
1. Formal
Logic 4
2. Set
Theory 4
3. Boolean
Algebras 6
4. Graph
Theory 6
5. Trees 5
6. Weighted
Graphs 5
7. Introductory
Computability Theory 8
8. Notations
of Syntax Analysis 2
1.1
Proof
1.2
Statements
1.3
Symbolic
representation
1.4
Predicates
& Quantifiers
1.5
Well
formed formulas
1.6
Tautologies
1.7
Validity
1.8
Propositional
Logic
1.9
Normal
forms
1.10
Principal
CNF
1.11
Principal
DNF
2.1
Sets
and Operations on sets
2.2
Binary relations
2.3
Partitions and Equivalence relations
2.4
Partial orders
2.5
Principle of Inclusion-Exclusion
2.6
Pigeon hole principle
3.1
Lattices
as partially ordered sets
3.2
Lattices
as Algebraic Systems
3.3
Distributive
and complemented lattices
3.4
Boolean
Algebras as Lattices – Definitions
3.5
examples
and properties
4.1 Graphs
4.2 Paths
4.3 Circuits
4.4 Subgraphs
4.5 Induced subgraphs
4.6 Degree of a vertex
4.7 Euler Path and graphs
4.8 Hamiltonian path and circuits
4.9 Connected graph
4.10 Complete graphs
4.11 Isomorphism of graphs
4.12 Planar graphs – Definitions
4.13 Examples and properties
4.14 Euler’s formula for connected Planar graphs
4.15 Kuratoski’s theorem and its applications
5. Trees
5.1
Spanning
trees, Cut-sets
5.2
Fundamental
cut-sets
5.3
Minimal
spanning trees
5.4
Kurskal’s and Prim’s algorithms
5.5
Directed
graph, In-degree and out-degree of a vertex
5.6
Weighted
graphs
5.7
Dijkstra’s algorithm
5.8
Strong
connectivity and Warshall’s algorithm
5.9
Binary
search trees
5.10
Tree
traversal procedures with examples
6 Introductory
Computability Theory
6.1
Finite
State Machines and their transition table diagrams
6.2
Equivalence
of Finite State Machines
6.3
Finite
Automata
6.4
Acceptors
6.5
Non-Deterministic
Finite Automata
6.6
Conversion
of Non-Deterministic Finite Automata into Deterministic Automata and their
equivalence
7 Notations
of Syntax Analysis
7.1
Polish
Notations
7.2
Conversion
of Infix expressions to Polish notation
References