CT-22                                      Discrete Mathematical Structures

# StructureNo of hours (40)

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. Formal Logic

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

1. Set Theory

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

1. Boolean Algebras

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

1. Graph Theory

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

1. J.P.Tremblay and  R.Manohar, Discrete Mathematical Structures with Applications to Computer Science, McGraw-Hill Publishing , 1999
2. Kenneth Rosen, Discrete Mathematics and its Applications, 5th Edition, Tata McGraw-Hill Publishing
3. S.Witala, Discrete Mathematics-A unified Approach, McGraw-Hill Publishing
4. J.E.Hopcrat and J.D.Ullman, Introduction to Automata Theory, Languages and Computation, Narosa Publishing House
5. C.L.Liu, Elements of Discrete Mathematics, Mc-Graw Hill Publishing
6. N.Deo, Graph Theory with Applications to Engineering and Computer Sciences, Prentice Hall of India