## Discrete Structures (CS21001)

### Autumn Semester 2014

#### 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:
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.