**CDS 304****:Discrete Structures and Computation **

*Course Contents*:

*Module-1*:

Review of Sets, Operations, Principles of Inclusion and Exclusion. Functions, relations, Equivalence relations. Countable and uncountable sets. Review of Pigeonhole principle.

*Module-2*:

Introduction to Propositional Logic, Equivalence and Implications. Truth tables, De Morgan’s Law, Quantifiers, Inference and Proofs. Introduction to First Order Logic, Syntax and Semantics, Soundness and Completeness.

*Module-3*:

Mathematical Induction, Recursions, First order linear recurrence, Geometric series, Recursion trees and growth rates of solutions to recurrences, Master Theorem. Generating Functions.

*Module-4*:

Introduction to counting, sum and product principles, counting subsets. Binomial coefficients and Pascal’s triangles. Polya’s theory of counting (optional).

*Module-5*:

Arithmetic Algorithms: Computing GCD, primality testing, RSA.

*Module-6*:

Graph Theory: Graphs, representations, connectivity, cycles, trees, Spanning tree of a graph, Algorithms to find minimum spanning trees. Eulerian Cycle and Hamiltonian paths, independence number and clique number, chromatic number, Dominating Sets, and Covering Sets. Planar Graphs. Directed Graphs and tournaments.

*Module-7*:

Probabilistic tools, Tail Bounds and Applications.

*Module-8*:

Linear Algebraic tools in Combinatorics.

Previous | Back to Course List | Next |