Discrete Mathematics - IIITB

Discrete mathematics is the study of mathematical structures that are discrete in the sense that they assume only distinct, separate values, rather than in a range of values. It deals with the mathematical objects that are widely used in all most all fields of computer science, such as programming languages, data structures and algorithms, cryptography, operating systems, compilers, computer networks, artificial intelligence, image processing, computer vision, natural language processing, etc. The subject enables the students to formulate problems precisely, solve the problems, apply formal proof techniques and explain their reasoning clearly.INTENDED AUDIENCE :The course is intended for any student from the computer science disciplinePREREQUISITES : NoneINDUSTRIES SUPPORT :None

Week 1:Logic: Proposition and Predicate Logic, introduction to proof techniques Week 2:Advanced proof techniques, resolution, induction Week 3:Set theory and relations Week 4:Various types of relations and functions
Week 5:Combinatorics Part I: permutations, combinations, sum rule, product rule, pigeon-hole principle, Ramsey numbers Week 6:Combinatorics Part II: Combinatorial proofs, Catalan numbers, counting using recursion, principal of inclusion-exclusion, advanced counting techniques Week 7:Recurrence equations and various methods of solving recurrence equations Week 8:Cardinality theory, countable and uncountable sets, Cantor’s diagonalization, uncomputable functions
Week 9:Graph theory Part I: basic definitions, Euler’s theorem, bipartite graphs and matching, Hall’s marriage theorem, various operations on graphs Week 10:Graph theory part II: isomorphism, vertex-connectivity, edge-connectivity, Euler graphs and Hamiltonian graphs, various characterizations, vertex and edge coloring Week 11:Abstract algebra: groups, rings, fields Week 12:Basic number theory: modular arithmetic, prime numbers and properties, GCD, Chinese remainder theorem, Fermat’s little theorem, RSA cryptosystem