Verify Account

SYLLABUS

UNIT-1

The foundations: logic and proofs Propositional Logic - Applications of Propositional Logic - Propositional Equivalence - Predicates and Quantifiers - Nested Quantifiers - Rules of Inference - Introduction to Proofs - Proof Methods and Strategy.

UNIT-2

Basic structures, sets, functions, sequences, sums, matrices and relations Functions - Sequences & Summations - Cardinality of Sets and Matrices Relations - Relations and Their Properties - n-ary Relations and Their Applications - Representing Relations - Closures of Relations - Equivalence Relations - Partial Orderings.

UNIT-3

Algorithms, induction and recursion Algorithms - The Growth of Functions - Complexity of Algorithms, Induction and Recursion: Mathematical Induction - Strong Induction and Well-Ordering - Recursive Definitions and Structural Induction - Recursive Algorithms - Program Correctness

UNIT-4

Discrete probability and advanced counting techniques An Introduction to Discrete Probability - Probability Theory - Baye’s Theorem - Expected Value and Variance. Advanced Counting Techniques: Recurrence Relations - Solving Linear Recurrence Relations - Divide-and-Conquer Algorithms and Recurrence Relations - Generating Functions - Inclusion- Exclusion - Applications of Inclusion-Exclusion

UNIT-5

Graphs and trees Graphs: Graphs and Graph Models - Graph Terminology and Special Types of Graphs - Representing Graphs and Graph Isomorphism - Connectivity - Euler and Hamilton Paths - Shortest-Path Problems - Planar Graphs - Graph Coloring. Trees: Introduction to Trees - Applications of Trees - Tree Traversal - Spanning Trees - Minimum Spanning Trees