Course Details

Subject {L-T-P / C} : CS2003 : Discrete Structures { 3-0-0 / 3}

Subject Nature : Theory

Coordinator : Prof. Anup Nandy

Syllabus

Logic and Proofs – Propositional logic, equivalences, Predicates and quantifiers, Nested quantifiers, Rules of inference, Introduction to proofs, Proof methods.
Basic structures – Sets and their operations, functions, sequences and summations.
Algorithms, integers and matrices – Growth of functions, Complexity of integers and divisions, Primes and GCD, Matrices.
Induction and Recursion – Mathematical induction, Strong induction, Recursive defintions and well ordering.
Counting – Basics, Pigeonhole principle, Permutation and Combinations, Binomial Coefficeints, Generalized Permuations and Combinations.
Recurrence relations, Divide and Conquer algorithms, Generating functions and inclusion-exclusion.
Relations- Relations and their properties, n-ary relations, representations, closure, equivalence relations, partial orders.
Graph theory- Graph representation, terminalogy, isomorphism, Connectivity, Euler and Hamiltonial paths, Shortest paths, Planar Graphs. Trees.
Algebraic structures and coding theory- Introduction, structure of algebras, Semigroups, monoids, Groups, Fields, Rings, Integral domains

Course Objectives

Course Outcomes

After reading this subject, students will be able to: <br />1. Understand set theory, propositions, predicate calculus which will help to improve their mathematical reasoning. <br />2. Improving skills on permutations and combinations, relations and functions and their applications in Problem solving. <br />3. Learn concepts of groups, rings and field along with basics of graph theory. <br />4. Understand recurrence relations and the methods to find out their solutions. <br />5. Enhance skills in Modeling and algorithmic thinking with discrete mathematics to develop their own models in computer science and data networking applications.

Essential Reading

Supplementary Reading