Discrete Structures and Graph Theory- JNTU Kakinada First Year Syllabus 2009 |
UNIT-I |
Mathematical Logic: Statements and notations, Connectives, Well formed formulas, Truth Tables, tautology,
equivalence implication, Normal forms, Theory of inference for the statement calculus
|
UNIT-II |
Rules of inference, Consistency of premises and indirect method of proof, Automatic Theorem Proving
Predicate calculus: Predicates, statement functions, variables and quantifiers, predicate formulas, free & bound
variables, universe of discourse, inference theory of predicate calculus
|
UNIT III |
Set theory & Relations:Introduction, Relations and ordering, Properties of binary Relations, Equivalence,
Compatibility Relations, Partial ordering, Hasse diagram.
Functions: composition of functions, Inverse Function, Recursive Functions, Lattice and its Properties, Pigeon hole
Principles and its application.
|
UNIT IV |
Algebraic structures: Algebraic systems, Examples and general properties, Semi groups and monoids, groups, sub
groups, Definitions, Examples, homomorphism, Isomorphism and related problems
|
UNIT V |
Elementary Combinatorics: Basis of counting, Enumeration of Combinations & Permutations, Enumerating of
Combinations & Permutations with repetitions and constrained repetitions, Binomial Coefficients, Binomial
Multinomial theorems, principles of Inclusion Exclusion.
|
UNIT VI |
Recurrence Relations: Generating Function of Sequences, Calculating Coefficient of generating functions,
Recurrence relations, Solving recurrence relation by substitution and Generating functions, The method of
Characteristic roots, Solution of Inhomogeneous Recurrence Relation.
|
UNIT VII |
Graph Theory: Representation of Graph, Spanning Trees, BFS, DFS, Kruskals Algorithm, Binary trees, Planar
Graphs
|
UNIT VIII |
Graph Theory and Applications, Basic Concepts, Isomorphism and Sub graphs, Multi graphs and Euler circuits,
Hamiltonian graphs, Chromatic Numbers
|
REFERENCES |
Text Books: |
1. Discrete Mathematical Structures with Applications to computer science J.P Tremblery, R.Manohar, TMH
2. Discrete Mathematical for computer Scientists & Mathematicians J.L. Molt, A.Kandel ,T.P.Baker, PHI
|
Reference Books |
1. Elements of Discrete Mathematics, C L Liu, D P Mohanpatra,TMH
2. Discrete Mathematics, Schaums Outlines,Lipschutz,Lipson TMH.
3. Discrete Mathematical Structures, Kolman, Busby, Ross, 6th ed., PHI, 2009
4. Discrete Mathematics, Johnsonbaugh, 6th ed., Pearson, 2005
5. Discrete Mathematics, Malik, Sen, 6th ed., Cengage Learning, 2004
6. Discrete Mathematics for computer science, Bogart, Stein and Drysdale, Springer, 2005
7. Discrete Mathematics and Combinatorics, Sengadir, Pearson, 2009
8. Discrete and Combinatorial Mathematics, Grimaldi, Ramana, 5th ed., Pearson. 2006
9. Mathematical Foundations of Computer Science, Rajendra Prasad, Rama Rao et al., USP, 2009
10. Discrete Mathematics, J K Sharma, 2nd ed., Macmillan, 2005
11. Discrete Mathematics with Combinatorics and Graph Theory, Santha, Cengage Learning, 2009
12. Applied Discrete Structures For Computer Science, Alan Doerr, Levassure, GP, 2005
13. Discrete Mathematics with Applications, Koshy, Elsevier,2006.
14. Discrete Mathematics and its Applications, Rosen, 5th ed, T M Graw-Hill ed, 2006.
15. Discrete Mathematics for Computer Science, Gary Haggard, John Schlipf, Sue Whitesides, Cengage.,2006.
16. Discrete Mathematical, Kevin Ferland, Cengage,2008.
17. Discrete Mathematical Structures, Jayant Ganguly, Sanguine, 2007.
|
|