Updated Zero Lecture MTH136

MTH136
DISCRETE STRUCTURES
#Zero Lecture
LTP and credit details
Teaching Model:
L-T-P: 3-1-0 (3 Lectures, 1 Tutorial, 0 Practical)

Total Credit = 4
Bloom’s Taxonomy
Course Outcomes
Through this course students should be able to
• Recalling basic concepts of sets, relations and functions and

understand the formal logical arguments using propositional logics.
• Determine the problem solving through the basics of combinatorics
• Analyse the basic discrete structures and algorithms.
• Study the concepts of trees to find the shortest path
• Inferring properties of graphs and be able to relate these to practical
examples.
• Implementing recurrence and problem solving skills to solve
mathematical problems
Program Objectives
• Objective-1 Apply fundamentals of technical knowledge in
multidisciplinary areas related to computer application to participate
as top professionals in leading Industries.
• Objective-2 Be sensitive to professional and ethical responsibilities,
including the societal impact of computer application as successful
innovators, consultants and entrepreneurs.
• Objective-3 Pursue advanced education, research and development in
Computer science as well as other professional endeavors.
• Objective-4 Ability to compete in national and international technical
events and building the competitive spirit
Syllabus Distribution:
Unit-1
Set Theory, Relation and Function
• Sets, Types of sets, Subsets, Power set,
• Venn diagrams, operation on sets, laws of set theory.
• Cartesian product of sets,
• Relations,
• Functions, some functions and their graphs.
• One-one and onto functions
Unit-2
Logic Calculus
• Introduction to logic, propositions and compound propositions
• Basic logical operations
• Propositions and truth tables
• Tautologies and contradiction
• logical equivalence
• Conditional and biconditional statements
Unit-3
Logic Gates and Recurrence Relations
• Introduction to logic gates, Combinations of gates

• Implementation of logic expressions with logic gates and switching
circuits
• Introduction to recursion, recurrence relation
• Solving recurrence relation
• Linear homogenous recurrence relation with constant coefficient and
their solution
Unit-4
Graph Theory-I
• Introduction and basic terminology

• Graphs, Multigraphs, degree of a vertex
• Handshaking theorem, sub graphs
• Homeomorphic and Isomorphic graphs
• Paths, connectivity, connected components,
• Distance and diameter,
• Cut points and bridges
Unit-5
Graph Theory-II
• Eulerian graphs, Hamiltonian graphs,
• Euler theorem,
• Planar graphs, maps, regions, Euler formula,
• Non planar graphs, Kuratowski's theorem (without proof).
• Graph coloring, chromatic number of a graph,
• Complete graph and its coloring,
• Regular and bipartite graphs and their coloring.
Unit-6
Shortest Paths & Trees
• Labelled and weighted graph,
• Shortest path in weighted graphs,
• Dijkstra’s algorithm to find shortest path,
• Introduction to tree, rooted tree, binary tree,
• Spanning tree, minimum spanning tree,
• Kruskal and Prims algorithms to find minimum spanning tree
Why to study logics and Proof ?
Computer programs are written in special, symbolic languages, e.g., Fortran, C++,
Lisp, Prolog. These languages contain features of logical symbolism, and Lisp and
Prolog are derived from formal languages for logic. Through such connections, the
study of logic can help one in the design of programs.
The Seven Bridges of Königsberg
Is it possible to start at some location in the town, travel across all the
bridges once without crossing any bridge twice, and return to the starting
point.
Application of graph theory
Consider the problem of joining three
houses to each of three separate utilities,
as shown in Figure .
Is it possible to join these houses and
utilities so that none of the connections
cross?
In this section we will study the question of

whether a graph can be drawn in the plane
without edges crossing. In particular, we
will answer the houses-and-utilities
problem.
Determining if two compounds with the same formula are identical.
Application of Minimum Spanning Tree
Problem laying Telephone Wire
Assignment problem
There are 50 students in the class and

teacher needs to prepare minimum
number of class test for them in a way
such that no two consecutive students get
the same assignment.
It can be done via graph coloring , teacher

can find chromatic no. of graphical
representation of students
Evaluation Criteria
Marks Breakup:
Attendance 5
CA (2 best out of 3 Subjective Tests) 25
MTE (MCQ) 20
ETE (Subjective & MCQ) 50
Total 100
Relevant Resources Which Could Be Used
for Better Understanding of the Course.
Books Required
Text Book:
DISCRETE MATHEMATICS (SCHAUM'S OUTLINES) (SIE) by SEYMOUR LIPSCHUTZ,
MARC LIPSON, VARSHA H. PATIL, MCGRAW HILL EDUCATION
References Books:
DISCRETE MATHEMATICS & ITS APPLICATIONS by KENNETH H ROSEN, MCGRAW
HILL EDUCATION
NCERT MATHEMATICS TEXTBOOK FOR CLASS XI by NCERT, NCERT

MOOCs
DISCRETE MATHEMATICS
https://onlinecourses.nptel.ac.in/noc22_cs123/preview
https://onlinecourses.nptel.ac.in/noc22_cs85/preview
Get Set Go!!!
Gear up
Explore your Mathematical abilities
Build futuristic solutions of

problems of Computer application…
Next Class: Sets

Updated Zero Lecture MTH136

Uploaded by

Copyright:

Available Formats

Updated Zero Lecture MTH136

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Updated Zero Lecture MTH136

Uploaded by

Copyright:

Available Formats

MTH136

L-T-P: 3-1-0 (3 Lectures, 1 Tutorial, 0 Practical)

• Recalling basic concepts of sets, relations and functions and

• Introduction to logic gates, Combinations of gates

• Introduction and basic terminology

In this section we will study the question of

There are 50 students in the class and

It can be done via graph coloring , teacher

NCERT MATHEMATICS TEXTBOOK FOR CLASS XI by NCERT, NCERT

Build futuristic solutions of

You might also like