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

Computer and Data Sciences

CDS 304:Discrete Structures and Computation

Course Contents:


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


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.


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


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


Arithmetic Algorithms: Computing GCD, primality testing, RSA.


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.


Probabilistic tools, Tail Bounds and Applications.


Linear Algebraic tools in Combinatorics.

Previous Back to Course List Next