Discrete Structures (CS21001)

Autumn Semester 2014

Instructor: Animesh Mukherjee (animeshm@cse.iitkgp.ernet.in)

Teaching Assistant: Abhrajit Sengupta, Akash Shah, Mayank Singh

Mail your queries to: ds14autumn@gmail.com

Class Timings: Monday 9:30 -- 10:25 (FN), Wednesday 8:30 -- 9:25 (FN) and Thursday 9:30 -- 10:25 (FN).
Tutorial Hour: Tuesday 5:30 -- 6:30 (AN)
Location (Theory): CSE 120.
Location (Turotrial): Room CSE 119 (Odd roll numbers), Room CSE 120 (Even roll numbers).
Ofice of the Instructor: Room 102, CSE

Course Rules
  1. Any time your attendance falls below 85%, you have 100% chance of being de-registered irrespective of your class performance, CGPA, DR, IR. No considerations!!
  2. Rounds of de-registration --> Round 1: Within two weeks from the commencement of the semester; Round 2: One week before midsem; Round 3: Two weeks after midsem.

Marks Division
  1. Class Test (1+1): 20%
  2. Tutorial: 10%
  3. Midsem: 25%
  4. Endsem: 45%

References
  1. Discrete Mathematics -- Norman L. Biggs
  2. Discrete Mathematics -- S. K. Chakraborty and B. K. Sarkar
  3. Apart from the above two books I shall also refer to course lectures from other universities.

Tutorial Problems with Solutions:
  1. Tutorial I, Solutions
  2. Tutorial II, Solutions
  3. Tutorial III, Solutions
  4. Tutorial IV, Solutions
  5. Quiz I
  6. Tutorial V, Solutions
  7. Tutorial VI, Solutions
  8. Tutorial VII, Solutions
  9. Tutorial VIII, Solutions
  10. Tutorial IX, Solutions
  11. Tutorial X, Solutions
  12. Tutorial XI, Solutions
  13. Quiz II
  14. Tutorial XII, Solutions

Syllabus
  1. Introduction -- DS for computer science
  2. Sets, set operations, some general proofs on set operations, power sets, some proofs on sets by induction
  3. Relations -- ordered pair, Cartesian product, reflexive, symmetric, anti-symmetric, equivalence relation, equivalence classes and equivalence partitions
  4. Partial order relations, representing partial orders with Hasse Diagram, topological sort
  5. Isomorphism, bound, Lattice algebra
  6. Types and properties of Lattices
  7. Functions -- types of functions, their properties, composition, Warshall's theorem, special functions
  8. Proof techniques -- Induction (in details), contradiction, direct proofs (proof by construction), contrapositive
  9. Principles of counting -- basic combinatorics (permutation, combination, binomial theorem, binomial coefficients), countability - countable and uncountable sets, inclusion-exclusion principle, pigeon hole principle
  10. Recurrence relation, golden ratio, generating functions
  11. Divisibility, GCD, LCM, Prime numbers, modular arithmetic
  12. Propositional logic -- propositions, predicates, quantifiers, negation, logical connectives, tautologies and logical inference, valid and invalid arguments, modus ponen, modus tollen.
  13. Linear algebra in brief -- matrix space, rank, vector space, operations, spectral properties
  14. Group theory -- notions of group, Abelian group, permutation groups and cycles, generators, orbits and stabilizers, rings, fields, polynomials, finite fields, finite geometry and projective planes.
  15. Notions of Boolean algebra and Boolean connectives, error-correcting codes
  16. Symmetry, dihedral symmetry, symmetry in 3-D, Polya's theorem.