Office of Academic Affairs
Indian Institute of Science Education and Research Berhampur

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