Syllabus

Introduction to Logic: Logical Operators – negation, conjunction, disjunction, XOR, conditional, biconditional. Precedence of logical operators. The conditional operator, examples of translating English sentences into compound propositions, logical equivalences, some examples of logic puzzles. Predicates, definitions, examples, Existential and Universal Quantifiers, Uniqueness quantification using existential and universal quantification, Restricting domain in case of existential and universal quantification. Logical Equivalences between predicates. Predicates with multiple variables. Examples. Nested Quantifiers. Order of Nesting of quantifiers. Examples where the order can be flipped and cases in which it cannot be. Thinking of quantifiers as loops. Nested Quantifiers, examples. Arguments, Argument Form. Valid arguments. Rules of Inference. Modus Ponens, Modus Tollens, Addition, Simplification. Why is a particular argument form valid or invalid? Rules of Inference. Arguments using these rules of inference. Examples.

Proof Techniques: Direct Proof, Proof by contradiction, proof by contraposition. Examples in each case. Pitfalls in proof by enumeration. Example. Some more examples of Proof by contrapositive, contradiction. Proof by cases, exhaustive proofs. Backward reasoning: examples arithmetic and geometric mean. Game of marbles. Existential proofs (non-constructive): examples. Chomp. Proof strategies: checkerboard and tilings. Examples.

Introduction to Sets: definitions, subsets, null-set, power-set, set operations, computer representation of sets. Russels paradox, barber’s puzzle. Cardinality of sets, infinite sets, cardinality of infinite sets. Detour to Cartesian Products, relations, function, one-one, onto, one-one onto functions. Countably infinite sets, Set of integers is countable, set of positive rationals is countable, set of reals is uncountable (Cantor’s diagonalization argument).

Mathematical induction: Why it works. Well ordering principle. Examples using induction and strong induction. Sequences.Well ordering principle, proofs using WOP, example on Tournaments and existence of GCD. Brief discussion on recursion and recursively defined objects. Trees. Recursion, recursive functions, height of a tree, number of nodes.

Proving program correctness: Pre-conditions, post-conditions, loop invariants. Program termination. Can termination be checked by a general algorithm? Discussion on the halting problem.

Relations revisited: Properties of relations. Reflexive, Symmetric, Antisymmetric, Transitive. Examples. Relations represented as matrices, diagraphs. closures of relations. Reflexive, symmetric, and transitive closures. Computing them. A naive method to compute transitive closure. Calculation of number of bit operations required for the algorithm. Warshall’s algorithm for computing transitive closure. Calculation of number of bit operations for Warshall’s algorithm. Equivalence relations, equivalence classes, partitions. Partial orders, examples, Hasse diagram, minimal, maximal elements, least and greatest elements, chains and antichains.

Graphs: Graphs as relations, directed graphs, undirected graphs, special types of graphs, paths, cycles, trees, cliques, bipartite graphs. Bipartite graphs continued, Matchings in bipartite graphs. Relation between Matching and Vertex cover. Halls theorem. Proof of Halls Theorem. Konig’s theorem and proof of it using Hall’s Theorem. Coloring of graphs. Bipartite graphs are 2-colorable. Existence of a K_s implies that the chromatic number is greater than s. Greedy coloring. Introduction to Planar graphs. Planar graphs and properties – Euler’s formula, proof, bound on number of edges of a planar graph. Coloring of planar graphs using 6 colors. Statement of Kuratowaski’s theorem (without proof). Definition of Homeomorphism.

Basics of Counting: Sum product rule. Pigeon Hole principle and applications of pigeon hole principle to various problems. Permutations and Combinations, Binomial theorem and identities. Proofs using combinatorial arguments. Permutations and combinations with repetition. Generating permutations and combinations. Algorithms for the same.

Introduction to discrete probability: Examples. Independence and conditional probability. Examples of independent events. Probabilistic reasoning. Monty Hall 3 Door puzzle. Random variables, expectation, linearity of expectation. Examples. Hatcheck Problem, Number of inversions in a permutation.

Advanced Counting techniques: Modelling problems with recurrences relations. Towers of Hanoi, Fibonacci, Catalan numbers. Catalan Numbers: Balanced Parenthesis, Number of rooted full binary trees, Diagonal Avoiding paths. Recursive formulation. Catalan Numbers – proof of closed form formula. Equivalence to number of mountain ranges with up and down strokes and the number of ways to parentheize.

Textbook(s)

  1. Discrete Mathematics and Applications by Kenneth Rosen (7th Edition, 2012), McGraw-Hill Education (ISBN-13: 978-0073383095)

  2. Discrete Mathematics by Norman L. Biggs (2nd Edition, 2002), Oxford University Press (ISBN-13: 978-0198507178)

Past Offerings

  • Offered in July-Dec, 2017 by Deepak
  • Offered in July-Dec, 2016 by Deepak

Course Metadata

Item Details
Course Title Discrete Mathematics for Computer Science
Course Code CS2100
Course Credits 3-0-0-3
Course Category PMT
Approved on Senate of IIT Palakkad