Discrete Mathematics

GANPAT UNIVERSITY

FACULTY OF ENGINEERING & TECHNOLOGY

Programme

Bachelor of Technology

Branch/Spec.

Computer Science & Engineering (BDA)

Semester

VI

Version

1.0.0.1

Effective from Academic Year

2022-23

Effective for the batch Admitted in

June 2019

Subject code

2CSE607

Subject Name

DISCRETE MATHEMATICS

Teaching scheme

Examination scheme (Marks)

(Per week)

Lecture (DT)

Practical (Lab.)

Total

CE

SEE

Total

L

TU

P

TW

Credit

2

0

1

0

3

Theory

40

60

100

Hours

2

0

2

0

4

Practical

30

20

50

Pre-requisites:

Engineering Mathematics, Data structures and Algorithms

Learning Outcome:

After learning the course, the students will be able to:

• Describe mathematical arguments using logical connectives and quantifiers.
• Identify the correctness of an argument using propositional, predicate logic and truth tables.
• Develop the ability to solve problems using counting techniques, combinatorics, recurrence relations, and generating functions in the context of discrete probability.
• Apply graphs and trees as tools to visualize various scenarios.

Theory syllabus

Unit

Content

Hrs

1

Sets, Propositions, and Principles of Counting

Introduction of sets and Proposition with real-life examples, Principles of Counting: the principle of inclusion-exclusion, the addition and multiplication rules, the pigeonhole principle, Permutation and combination, Binomial Coefficients

5

2

Relations and functions

Properties of binary relations, equivalence relation, partitions, partial ordering, Functions: domain and range of a function, the identity function, one-to-one, onto and one-to-one correspondence functions, some discrete and Continuous variable examples, inverse function, composition of functions.

5

3

Graphs

Basic terminology, Graph Representation, multi- and weighted graphs, paths, circuits, shortest path, subgraphs, pseudographs, connected graphs, bipartite graphs, Eulerian path, isomorphism, factors of a graph, planar graphs, theorems on Eulerian circuits and Eulerian trails, Hamiltonian cycles with examples

8

4

Discrete numerical functions

manipulations of numerical functions, asymptotic behaviour, generating functions, combinatorial problems, recurrence relations

3

5

Group

groups and sub-groups, generators, evaluation of powers, cosets, Lagrange's theorem, permutation group and Burnside's theorem, group codes, isomorphism, automorphism, homomorphism, normal subgroups, rings, integral domains and fields, ring homomorphism, polynomial rings

6

6

Lattices

Lattices and algebraic systems, principle of duality

3

Practical content

Practical based on sets, functions, relations, counting techniques, combinatorics, graphs, trees, recurrence relations, generating functions, groups, rings, and lattices.

Text Books

1

"Elements of Discrete Mathematics", C.L. Liu, McGraw-Hill

Reference Books

1

Modern Applied Algebra", Birkoff and Bartee, McGraw-Hill, CBS.

2

"Discrete Mathematics - A Unified Approach", Stephen A. Wiitala, Computer Science Series, McGraw- Hill

3

“Discrete Mathematics and Its Applications”, Kenneth H. Rosen, McGraw-Hill Higher Education

Course Outcomes:

COs

Description

CO1

Describe mathematical arguments using logical connectives and quantifiers.

CO2

Identify the correctness of an argument using propositional, predicate logic and truth tables.

CO3

Develop the ability to solve problems using counting techniques, combinatorics, recurrence relations, and generating functions in the context of discrete probability.

CO4

Apply graphs and trees as tools to visualize various scenarios.

Mapping of CO and PO: