Department of Computer Science and Engineering

B.Tech. II (CO) Semester - 3

L

T

P

C

MH203 : DISCRETE MATHEMATICS (IS-III)

3

1

0

4
COURSE OBJECTIVES
  • Introduce students to the techniques, algorithms, and reasoning processes involved in the study of discrete mathematical structures.
  • Introduce students to set theory, inductive reasoning, elementary and advanced counting techniques, equivalence relations, recurrence relations, graphs, and trees.
  • Introduce students to prove mathematical statements by means of inductive reasoning.
    		•
    COURSE OUTCOMES
    After successful completion of this course, student will be able to
    • Understand discrete mathematical preliminaries.
    • Apply discrete mathematics in formal representation of various computing constructs
    • Recognize the importance of analytical problem solving approach in engineering problems.
    COURSE CONTENT
    Graph Theory

    (08 Hours)

    Graphs, Definition & basic concepts of finite & infinite graph, Incidence & Degree, Isomorphism, Subgraph, Walk, Path & circuits, Operations on graphs, connected graph, Disconnected graph & components, Complete graph, Regular graph, Bipertite graph, Euler’s graph, Hamiltonian paths & Circuits, Weighted graphs, Applications, Directed & Undirected graphs, Connectivity of graphs.
    Trees

    (06 Hours)

    Definition & properties of trees, Pendent vertices in a tree, Distance between two vertices Centre, Radius & diameter of a tree, Rooted & binary trees, Representation of Algebraic structure by Binary trees, Binary search trees, Spanning trees & fundamental circuits.
    Relation & Lattices

    (08 Hours)

    Definition & Basic properties, Graphs of relation, Matrices of relation, Equivalence relation, Equivalence classes, Partition, Partial ordered relation, Posets, Hasse diagram, Upper bounds, Lower bound, GLB & LUB of sets, Definition & properties of Lattice, Sub lattice, Distributive & modular lattices, complemented & Bounded Lattices, complete lattices & Boolean algebra
    Group theory

    (08 Hours)

    Basic properties of Group, Groupoid, semigroup & monoid, Abelian group, Subgroup, Cosets, Normal subgroup, Lagrange’s theorem, Cyclic group, Permutation group, Homomorphism & Isomorphism of groups, Basic properties, error correction & detection code.
    Mathematical logic and Program verification

    (12 Hours)

    Propositions, logical operators & propositional algebra, Predicates & quantifiers, Interaction of quantifiers with logical operators, Logical interference & proof techniques, Formal verification of computer programs (elements of Hoare logic).
  • Tutorials will be based on the coverage of the above topics separately

    • (14 Hours)

    (Total Contact Time: 44 Hours + 14 Hours = 58 Hours)
    BOOKS RECOMMENDED
    1. Rosen K.H., "Discrete Mathematics and Its Applications", 6/E, MGH, 2006.
    2. Kolman B., Busby R.C. & Ross S., "Discrete Mathematical Structure", 5/E, PHI, 2003.
    3. Tremblay J. P. & Manohar R., "Discrete Mathematical structure with applications to computer science", MGH, 1999.
    4. Deo Narsingh., "Graph theory with applications to Engineering & Computer Science", PHI, 2000.
    5. Liu C.L., "Elements of Discrete Mathematics", MGH, 2000.