Discrete Structures (CS21001)
Autumn Semester 2015
Instructor: Animesh Mukherjee (animeshm@cse.iitkgp.ernet.in)
Teaching Assistant: Soumya Sarkar, Manav Sethi, Sourav Sarkar
Mail your queries to: ds15autumn@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: Monday 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

Any time your attendance falls below 85%, you have 100% chance of being deregistered irrespective of your class performance, CGPA, DR, IR. No considerations!!

Rounds of deregistration > 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

Class Test (1+1): 20%

Tutorial: 10%

Midsem: 25%

Endsem: 45%
References
 Discrete Mathematics  Norman L. Biggs
 Discrete Mathematics  S. K. Chakraborty and B. K. Sarkar
 Apart from the above two books I shall also refer to course lectures from other universities.
Tutorial Problems with Solutions:
 Tutorial I, Solutions
 Tutorial II, Solutions
 Tutorial III, Solutions
 Quiz I, Solutions
 Tutorial IV, Solutions
 Tutorial V, Solutions
 Tutorial VI, Solutions
 Tutorial VII, Solutions
 Quiz II, Solutions
 Tutorial VIII, Solutions
 Tutorial IX, Solutions
 Tutorial X, Solutions
Syllabus
 Introduction
 DS for computer science
 Sets,
set operations, some general proofs on set operations, power sets, some
proofs on sets by induction
 Relations
 ordered pair, Cartesian product, reflexive, symmetric, antisymmetric,
equivalence relation, equivalence classes and equivalence partitions
 Partial
order relations, representing partial orders with Hasse Diagram, topological
sort
 Isomorphism,
bound, Lattice algebra
 Types
and properties of Lattices
 Functions
 types of functions, their properties, composition, Warshall's
theorem, special functions
 Proof
techniques  Induction (in details), contradiction, direct proofs
(proof by construction), contrapositive
 Principles
of counting  basic combinatorics (permutation, combination, binomial
theorem, binomial coefficients), countability  countable and uncountable
sets, inclusionexclusion principle, pigeon hole principle
 Recurrence
relation, golden ratio, generating functions
 Divisibility,
GCD, LCM, Prime numbers, modular arithmetic

Propositional logic  propositions, predicates, quantifiers, negation,
logical connectives, tautologies and logical inference, valid and invalid
arguments, modus ponen, modus tollen.
 Linear
algebra in brief  matrix space, rank, vector space, operations, spectral
properties

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.
 Notions
of Boolean algebra and Boolean connectives, errorcorrecting codes
 Symmetry,
dihedral symmetry, symmetry in 3D, Polya's theorem.