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
-
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!!
-
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
-
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
- Tutorial IV, Solutions
- Quiz I
- Tutorial V, Solutions
- Tutorial VI, Solutions
- Tutorial VII, Solutions
- Tutorial VIII, Solutions
- Tutorial IX, Solutions
- Tutorial X, Solutions
- Tutorial XI, Solutions
- Quiz II
- Tutorial XII, 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, anti-symmetric,
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, inclusion-exclusion 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, error-correcting codes
- Symmetry,
dihedral symmetry, symmetry in 3-D, Polya's theorem.