Course Details

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

Subject Nature : Theory

Coordinator : 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:
1. Understand set theory, propositions, predicate calculus which will help to improve their mathematical reasoning.
2. Improving skills on permutations and combinations, relations and functions and their applications in Problem solving.
3. Learn concepts of groups, rings and field along with basics of graph theory.
4. Understand recurrence relations and the methods to find out their solutions.
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