 # 2CSE60E18: Discrete Mathematics

Learning Outcomes:
After learning the course the students should be able to:
Construct mathematical arguments using logical connectives and quantifiers.
Verify the correctness of an argument using propositional and predicate logic and truth tables.
Demonstrate the ability to solve problems using counting techniques and combinatorics in the context of discrete probability.
Solve problems involving recurrence relations and generating functions.
Use graphs and trees as tools to visualize and simplify situations.
Perform operations on discrete structures such as sets, functions, relations, and sequences.
Construct proofs using direct proof, proof by contraposition, proof by contradiction, proof by cases, and mathematical induction.
Apply algorithms and use definitions to solve problems to prove statements in elementary number theory.
Syllabus:
Unit NoTopics
Sets and propositions

combination, finite, uncountably infinite and infinite sets, mathematical induction, principles of inclusion and exclusion, propositions

Permutations, combinations, discrete probabilities

rules of sums and products, permutations, combinations, generation, discrete probability, conditional probability, information

Relations and functions

relational model of data bases, properties of binary relations, equivalence relation, partitions, partial ordering, lattices, chains and antichains, functions and pigeon-hole principle

Graphs

Basic terminology, multi- and weighted graphs, paths, circuits, shortest path, Eulerian path, Travelling Salesman problem, factors of a graph, planar graphs

Trees

trees, rooted trees, path length, prefix codes, binary search trees, spanning trees and cut-sets, minimum spanning trees, transport networks

Finite-state machines

FSM as models of physical systems, equivalent machines, FSM as language recognizer

Analysis of algorithms

time complexity of algorithms, example of shortest path algorithm, complexity, tractable and non-tractable problems

Computability and Formal languages

Russel's paradox and non-computability, ordered sets, languages, phrase structured grammars, types of grammars and languages

Recurrence relations

linear recurrence relations with constant coefficient, homogeneous, particular and total solutions, generating functions, sorting algorithms, matrix multiplication

Discrete numerical functions

manipulations of numerical functions, asymptotic behavior, generating functions, combinatorial problems

Group

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

Lattices and Boolean algebras

Lattices and algebraic systems, principle of duality, properties of algebraic systems, distributive lattices, boolean algebras, uniqueness, boolean functions and expressions, propositional calculus

Text Books:
Name :
Elements of Discrete Mathematics
Author:
C.L. Liu
Publication:
McGraw-Hill
Edition:
2nd Ed
Reference Books:
Name:
Modern Applied Algebra
Author:
Birkoff and Bartee
Publication:
McGraw-Hill
Name:
Discrete Mathematics - A Unified Approach
Author:
Stephen A. Wiitala
Publication:
McGraw- Hill.
Syllabus PDF:
AttachmentSize ELECTIVE VI (Discrete Mathematics) .pdf109.79 KB
branch:
BDA
Course:
2016
Stream:
B.Tech