School:SET Batch:2019-20

Program: B.Tech Current Academic Year:2019-20

Branch:CSE Semester:

1 Course Code CSE245 Course Name: Discrete Structures

2 Course Title Discrete Structures
3 Credits 4
Contact
4 3-1-0
Hours(L-T-P)
Course Status
This course provides a mathematical foundation for subsequent study in
Course
5 Computer Science, as well as developing the skills necessary to solve practical
Objective
problems.
After the completion of this course, students will be able to:
CO-1. Apply the basic principles of sets and operations in sets.
CO-2. Classify logical notation and determine if the argument is or is not
valid.
Course
CO-3. Construct and prove models by using algebraic structures.
6 Outcomes (CO)
CO-4. Analyze basic principles of Boolean algebra with mathematical
description.
CO-5. Construct Permutations and combinations in counting techniques and
applications of Graph Theory.
CO-6. Compose computer programs in a formal mathematical manner.
7 Prerequisite Concepts of algebra
CO-Mapping
8 Course Contents
Unit 1 Introduction to Set Theory, Relations and Functions.
Set Theory: Introduction, Combination of sets, Multi sets,
A CO1
ordered pairs, Set Identities.
Relations: Definition, Operations on relations, Properties of
B relations, Composite Relations, Equality of relations, Order of CO1
relations.
Functions: Definition, Classification of functions, Operations on
C CO1
functions, Recursively defined functions.
Unit 2 Logics and Mathematical Induction
Propositional Logic: Proposition, well formed formula, Truth
A tables, Tautology, Satisfiability, Contradiction, Algebra of CO1,CO2
proposition, Theory of Inference, Natural Deduction.
Predicate Logic: First order predicate, well formed formula of
B CO1,CO2
predicate, quantifiers, Inference theory of predicate logic.
Natural Numbers: Introduction, Mathematical Induction,
C CO1,CO2
Variants of Induction, Induction with Nonzero Base cases.
Unit 3 Algebraic Structures
Definition, Groups, Subgroups and order, Cyclic Groups, Cosets,
A CO3
Lagrange's theorem, Normal Subgroups,
Homomorphism’s, Definition and elementary properties of Rings
B CO3
and Fields, Integers Modulo n.
 Partial order sets: Definition, Partial order sets, Combination
C CO3
of partial order sets, Hasse diagram.
Unit 4 Lattices and Applications
Definition, Properties of lattices – Bounded, Complemented,
A CO4
Modular and Complete Lattice, Morphisms of lattices.
Boolean Algebra: Introduction, Axioms and Theorems of
Boolean algebra, Algebraic manipulation of Boolean
B expressions. Simplification of Boolean Functions, Karnaugh CO4
maps, Logic gates, Digital circuits and Boolean algebra.
Combinational and sequential Circuits.
Recurrence Relation & Generating function: Recursive
C definition of functions, Recursive algorithms, Method of CO4
solving recurrences.
Unit 5 Graph Theory and Applications.
Trees: Definition, Binary tree, Binary tree traversal, Binary
A CO4,CO5
search tree.
Graphs: Definition and terminology, Representation of graphs,
Multi graphs, Bipartite graphs, Planar graphs, Isomorphism and
B CO4,CO5
Homeomorphism of graphs, Euler and Hamiltonian paths, Graph
colouring.
Combinatory: Introduction, Counting Techniques, Pigeonhole
C CO4,CO5
Principle
Mode of Theory
examination

Weightage CA MTE ETE

Distribution
30% 20% 50%

1) 1. C. L. Liu, Elements of Discrete Mathematics, second edition

1985, McGraw-Hill Book Company. Reprinted 2000.
2) Jean Paul Trembley, R Manohar, “Discrete Mathematical
 Text book*
Structures with Application to Computer Science”, McGraw-Hill.
3) K. H. Rosen, Discrete Mathematics and applications, fifth edition
2003, Tata McGraw Hill Publishing Company.
1) J .L. Mott, A. Kandel, T.P .Baker, Discrete Mathematics for Computer
Scientists and Mathematicians, second edition 1986, Prentice Hall of
 other references India.
2) W.K. Grassmann and J.P.Trembnlay, Logic and Discrete
Mathematics, A Computer Science
Syllabus: CSE 245, Discrete Structures

CO and PO Mapping
 S. Course Outcome Program Outcomes (PO) & Program
No. Specific Outcomes (PSO)
1. CO1: Apply the basic principles of sets and PO1,PO2,PO3,PO4,PO6,PO12,
operations in sets. PSO1,PSO2

2. CO2: Classify logical notation and determine if PO1,PO2,PO3,PO6,PO9,PO12

the argument is or is not valid. PSO1,PSO2
3. CO3: Construct and prove models by using PO1,PO2,PO3,PO4,PO5,PO9,PSO2
algebraic structures. PSO3
4. CO4: Analyze basic principles of Boolean PO1,PO2,PO3,PO4,PO5,PO11,PO12
algebra with mathematical description. PSO1, PSO3
5. CO5: Construct Permutations and combinations PO1,PO2,PO3,PO4,PO6,PO9,PO11,PO12,
in counting techniques and applications of PSO2,PSO3
Graph Theory.
6 CO6: Compose computer programs in a formal PO1,PO2,PO3, PO4, PO5,PO9,PO11,
mathematical manner. PSO1,PSO2,PSO3

PO and PSO mapping with level of strength for Course Name Discrete Structures (Course Code
CSE245)

PO PO PO PO PO PO PO PO PO PO PO PO PSO1 PSO2 PSO3

1 2 3 4 5 6 7 8 9 10 11 12
CO1 2 3 3 1 _ 3 _ _ 3 _ _ 3 3 3 _

CO2 2 2 3 _ _ 2 _ _ _ _ _ 3 3 2 _

CO3 3 2 3 3 3 _ _ _ 2 _ _ _ _ 3 2

CO4 2 2 3 3 3 _ _ _ _ _ 3 3 3 _ 3

CO5 2 2 2 3 _ 3 _ _ 3 _ 3 3 _ 2 3

CO6 1 2 1 2 3 _ _ _ 3 _ 3 _ 3 3 2

Average of non-zeros entry in following table (should be auto calculated).

Course Course PO PO PO PO PO PO PO PO PO PO PO PO PSO PSO
Code Name 1 2 3 4 5 6 7 8 9 10 11 12 1 2 PSO 3

CSE245 DS 2 2.1 2.5 2 1.5 1.3 0 0 1.8 0 1.8 2 2 2.1 1.6

Strength of Correlation

1. Addressed to Slight (Low=1) extent 2. Addressed to Moderate (Medium=2) extent

3. Addressed to Substantial (High=3) extent