RK COLLEGE OF ENGINEERING
(Approved by AICTE, New Delhi and Affiliated to JNTU Kakinada)
(An ISO 9001:2015 Certified Institution)
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
II B.TECH I SEM A.Y: 2018-19
COURSE HANDOUT
Course No. : B.Tech
Course Title : MFCS
Name of the Faculty : Dr.K.Rama Krishnaiah
Course description:
This course teaches the students who complete the course will have demonstrated the ability to
do the following:
To introduce the students to the topics and techniques of discrete methods and
combinatorial reasoning. To introduce a wide variety of applications. The algorithmic approach
to the solution of problems is fundamental in discrete mathematics, and this approach reinforces
the close ties between this discipline and the area of computer science.
Scope and Objective of the course:
Upon completion of this course, students will be able to do the following:
Analyze the asymptotic performance computations
Write rigorous correctness proofs for mathematical foundations.
Demonstrate a familiarity with major fundamentals.
Apply important algorithmic design paradigms and methods of analysis.
.
COURSE CONTENTS
Syllabus:
UNIT -I:
Mathematical Logic: Propositional Calculus: Statements and Notations, Connectives, Well
Formed Formulas, Truth Tables, Tautologies, Equivalence of Formulas, Duality Law,
Tautological Implications, Normal Forms, Theory of Inference for Statement Calculus,
Consistency of Premises, Indirect Method of Proof. Predicate Calculus: Predicative Logic,
Statement Functions, Variables and Quantifiers, Free and Bound Variables, Inference Theory for
Predicate Calculus.
UNIT -II:
Set Theory: Introduction, Operations on Binary Sets, Principle of Inclusion and Exclusion,
Relations: Properties of Binary Relations, Relation Matrix and Digraph, Operations on Relations,
Partition and Covering, Transitive Closure, Equivalence, Compatibility and Partial Ordering
Relations, Hasse Diagrams, Functions: Bijective Functions, Composition of Functions, Inverse
Functions, Permutation Functions, Recursive Functions, Lattice and its Properties.
UNIT- III:
Algebraic Structures and Number Theory: Algebraic Structures:Algebraic Systems,
Examples, General Properties, Semi Groups and Monoids, Homomorphism of Semi Groups and
Monoids, Group, Subgroup, Abelian Group, Homomorphism, Isomorphism, Number
Theory:Properties of Integers, Division Theorem, The Greatest Common Divisor, Euclidean
Algorithm, Least Common Multiple, Testing for Prime Numbers, The Fundamental Theorem of
Arithmetic, Modular Arithmetic (Fermat’s Theorem and Euler’s Theorem)
UNIT -IV:
Combinatorics: Basic of Counting, Permutations, Permutations with Repetitions, Circular
Permutations, Restricted Permutations, Combinations, Restricted Combinations, Generating
Functions of Permutations and Combinations, Binomial and Multinomial Coefficients, Binomial
and Multinomial Theorems, The Principles of Inclusion–Exclusion, Pigeonhole Principle and its
Application.
UNIT -V:
Recurrence Relations: Generating Functions, Function of Sequences, Partial Fractions,
Calculating Coefficient of Generating Functions, Recurrence Relations, Formulation as
Recurrence Relations, Solving Recurrence Relations by Substitution and Generating Functions,
Method of Characteristic Roots, Solving Inhomogeneous Recurrence Relations
UNIT -VI:
Graph Theory: Basic Concepts of Graphs, Sub graphs, Matrix Representation of Graphs:
Adjacency Matrices, Incidence Matrices, Isomorphic Graphs, Paths and Circuits, Eulerian and
Hamiltonian Graphs, Multigraphs, Planar Graphs, Euler’s Formula, Graph Colouring and
Covering, Chromatic Number, Spanning Trees, Algorithms for Spanning Trees (Problems Only
and Theorems without Proofs).
Text Books:
1.Discrete Mathematical Structures with Applications to Computer Science, J. P. Tremblay
and P. Manohar, Tata McGraw Hill.
2. Elements of Discrete Mathematics-A Computer Oriented Approach, C. L. Liu and D. P.
Mohapatra, 3rdEdition, Tata McGraw Hill.
3. Discrete Mathematics and its Applications with Combinatorics and Graph Theory, K. H.
Rosen, 7th Edition, Tata McGraw Hill.
REFERENCE BOOKS
1. Discrete Mathematics for Computer Scientists and Mathematicians, J. L. Mott, A. Kandel,
T.P. Baker, 2nd Edition, Prentice Hall of India.
2. Discrete Mathematical Structures, BernandKolman, Robert C. Busby, Sharon Cutler
Ross, PHI.
3. Discrete Mathematics, S. K. Chakraborthy and B.K. Sarkar, Oxford, 2011..
Course Plan
Lect. Learning Objectives Chapter in the
Date Topics to be covered
No. (Student learns about) text book
UNIT-I
Mathematical Logic
1 Propositional Calculus Propositional Calculus: TI: Chapter1
Statements and Notations
Connectives, Well Connectives, Well
2 TI: Chapter1
Formed Formulas Formed Formulas
3 Truth Tables, Tautologies Truth Tables, Tautologies TI: Chapter1
4 Equivalence of Formulas Equivalence of Formulas TI: Chapter1
5 Duality Law Duality Law TI: Chapter1
6 Tautological Implications Tautological Implications TI: Chapter1
7 Theory of Inference for Statement Theory of Inference for TI: Chapter3
Calculus, Statement Calculus,
8 Consistency of Premises Consistency of Premises TI: Chapter3
Predicate Calculus: Predicative Predicate Calculus: Predicative TI: Chapter3
9
Logic Logic
10 Statement Functions Statement Functions TI: Chapter3
11 Discussed assignment Questions TI: Chapter3
12 Revision
UNIT – II
Set Theory
Introduction, Operations on Introduction, Operations on TI: Chapter6
13
Binary Sets Binary Sets
Principle of Inclusion and Principle of Inclusion and TI: Chapter6
14
Exclusion Exclusion
15 Relations: Properties of Binary Relations: Properties of Binary TI: Chapter6
Relations
16 Relation Matrix and Digraph Relation Matrix and Digraph TI: Chapter6
17 Operations on Relations Operations on Relations TI: Chapter6
18 Partition and Covering Partition and Covering TI: Chapter6
Transitive Closure, TI: Chapter6
19 Transitive Closure, Equivalence
Equivalence
Compatibility and Partial Compatibility and Partial TI: Chapter6
20
Ordering Ordering
21 Hasse Diagrams, Hasse Diagrams, TI: Chapter6
Bijective Functions, Composition Bijective Functions, TI: Chapter6
22
of Functions Composition of Functions
23 Inverse Functions, Permutation Inverse Functions, Permutation TI: Chapter6
Functions Functions
UNIT-III
Algebraic Structures and Number Theory
Algebraic Systems, Algebraic Systems, TI: Chapter7
24
Examples Examples
General Properties, Semi Groups General Properties, Semi TI: Chapter7
25
and Monoids Groups and Monoids
26 Homomorphism of Semi Groups Homomorphism of Semi TI: Chapter7
andMonoids, Groups and Monoids,
27 Group, Subgroup, Abelian Group Group, Subgroup, Abelian TI: Chapter7
Group
28 Homomorphism, Isomorphism Homomorphism,Isomorphism TI: Chapter7
Properties of Integers, Division Properties of Integers, Division TI: Chapter7
29
Theorem Theorem
30 The Greatest Common Divisor The Greatest Common Divisor TI: Chapter7
31 Euclidean Algorithm Euclidean Algorithm TI: Chapter7
32 Least Common Multiple Least Common Multiple TI: Chapter8
33 Testing for Prime Numbers Testing for Prime Numbers TI: Chapter8
34 Discussed assignment TI: Chapter8
35 Revision
UNIT-IV
Combinatorics
36 Basic of Counting, Permutations Basic of Counting, TI: Chapter10
Permutations
37 Permutations with Repetitions Permutations with Repetitions TI: Chapter10
38 Circular Permutations, Restricted Circular Permutations, TI: Chapter10
Permutations Restricted Permutations
39 Combinations, Restricted Combinations, Restricted TI: Chapter10
Combinations Combinations
Generating Functions of Generating Functions of TI: Chapter10
40 Permutations and Combinations Permutations and
Combinations
Binomial and Multinomial Binomial and Multinomial TI: Chapter10
41 Coefficients,
Coefficients,
42 Binomial and Multinomial Binomial and Multinomial TI: Chapter10
Theorems Theorems
The Principles of Inclusion– The Principles of Inclusion– TI: Chapter10
43
Exclusion Exclusion
Pigeonhole Principle and its Pigeonhole Principle and its TI: Chapter10
44
Application. Application.
45 Discussed assignment TI: Chapter11
Questions
46 Revision
UNIT-V
Recurrence Relations
47 Generating Functions, Generating Functions, TI: Chapter12
Function of Sequences
48 Partial Fractions, Partial Fractions, TI: Chapter12
Calculating Coefficient of Calculating Coefficient of TI: Chapter12
49
Generating Functions Generating Functions
50 Recurrence Relations, Recurrence Relations, TI: Chapter12
51 Formulation as Formulation as TI: Chapter12
Recurrence Relations Recurrence Relations
56 Solving Recurrence Relations by Solving Recurrence Relations TI: Chapter12
Substitution and Generating by Substitution and Generating
Functions Functions
57 Discussed assignment
Questions
58 Revision
UNIT-VI
Graph Theory
Basic Concepts of Graphs, Sub Basic Concepts of Graphs, Sub TI: Chapter13
59
graphs, graphs,
60 Matrix Representation of Graphs Matrix Representation of TI: Chapter13
Graphs
Adjacency Matrices, Incidence Adjacency Matrices, Incidence TI: Chapter13
61
Matrices Matrices
Isomorphic Graphs, Paths and Isomorphic Graphs, Paths and TI: Chapter13
62
Circuits Circuits
Eulerian and Eulerian and TI: Chapter13
63
Hamiltonian Graphs Hamiltonian Graphs
64 Multigraphs, Planar Graphs Multigraphs, Planar Graphs TI: Chapter13
65 Euler’s Formula, Graph Colouring Euler’s Formula, Graph TI: Chapter14
Colouring
66 Chromatic Number Chromatic Number TI: Chapter14
67 Spanning Trees, Spanning Trees, TI: Chapter14
68 Algorithms for Spanning Trees Algorithms for Spanning Trees TI: Chapter14
69 Discussed assignment TI: Chapter14
Questions
70 Revision
Self Study Topics
UNIT TOPIC SOURCE
T1: 1.Discrete Mathematical Structures with
I Mathematical Logic Applications to Computer Science, J. P.
Tremblayand P. Manohar, Tata McGraw Hill
T1: 1.Discrete Mathematical Structures with
II Set Theory Applications to Computer Science, J. P.
Tremblayand P. Manohar, Tata McGraw Hill
T1: 1.Discrete Mathematical Structures with
Algebraic Structures
III and Number Theory Applications to Computer Science, J. P.
Tremblay and P. Manohar, Tata McGraw Hill
T1: 1.Discrete Mathematical Structures with
IV Combinatorics Applications to Computer Science, J. P.
Tremblay and P. Manohar, Tata McGraw Hill
Recurrence Relations T1: 1.Discrete Mathematical Structures with
V Applications to Computer Science, J. P.
Tremblay and P. Manohar, Tata McGraw Hill
T1: 1.Discrete Mathematical Structures with
VI Graph Theory Applications to Computer Science, J. P.
Tremblay and P. Manohar, Tata McGraw Hill
Evaluation pattern:
Internal Marks : 30
External Marks : 70
EVALUATION SCHEME:
Component Duration(minutes) Marks Date & Time
Test – I 90 15
Test – II 90 15
Quiz-I 20 10
Quiz-II 20 10
Home Assignments 5
Comprehensive Examination 180 70
Chamber Consultation Hour:
Computer Science and Engineering Department
Room No:
Contact hours: 12:50 to 1:10 and 3:05 to 4:40.
E-mail Id:
Notices:
All notices regarding this subject will be displayed in the department notice board.
Signature of Faculty
