CS21001 Discrete Structures Autumn 2019, L-T-P: 3-1-0

Schedule

Instructors     Section 1: Abhijit Das
Section 2: Aritra Hazra
Timing     Slot D4 [MON(12:00–12:55), TUE(10:00–11.55), THU(08:00–08:55)]
Venue     Section 1: NR223
Section 2: NR424
Teaching Assistants     Anirban Chakraborty, Debranjan Pal, Himanshu Verma, Nishant Baranwal Somy, Pritam Pallab, Souvik Sur

Notices and Announcements

July 17, 2019, 1:00pm
We have accepted all additional applications received so far. Interested students may proceed with the completion of their registration.

July 14, 2019
Sectioning scheme: As per the Institute's convention, the students with odd first-year section numbers will go to Section 1, and the students with even first-year section numbers will go to Section 2.

July 14, 2019
We will decide about the additional registrants from non-CS departments little later. If there are too many external applicants, we have to go for a CGPA-based shortlisting.

Syllabus

Propositional logic

Syntax, semantics, valid, satisfiable and unsatisfiable formulas, encoding and examining the validity of some logical arguments.

Proof techniques

Forward proof, proof by contradiction, contrapositive proofs, proof of necessity and sufficiency.

Sets, relations
and functions

Operations on sets, relations and functions, binary relations, partial ordering relations, equivalence relations, principles of mathematical induction.

Size of a set

Finite and infinite sets, countable and uncountable sets, Cantor's diagonal argument and the power set theorem, Schröder-Bernstein theorem.

Combinatorics

Basic counting techniques: inclusion and exclusion, pigeon-hole principle, permutation, combination, summations. Introduction to recurrence relations and generating functions.

Algebraic structures
and morphisms

Algebraic structures with one binary operation - semigroups, monoids and groups, congruence relation and quotient structures. Free and cyclic monoids and groups, permutation groups, substructures, normal subgroups. Algebraic structures with two binary operations - rings, integral domains and fields. Boolean algebra and Boolean ring.

Graphs and trees

Graphs and their basic properties - degree, path, cycle, subgraphs, isomorphism, Eulerian and Hamiltonian walks, graph coloring, planar graphs, trees.

Books and References

We will mostly follow this textbook. Supplementary materials will be provided on topics not covered by this book.

Ralph P Grimaldi, Discrete and Combinatorial Mathematics, 5th Edition, Pearson, 2004.
Some other references are listed below.
  1. Michel O Albertson and Joan P Hutchinson, Discrete Mathematics with Algorithms, Wiley.
  2. Norman L Biggs, Discrete Mathematics, Oxford University Press.
  3. Winfried Karl Grassmann and Jean-Paul Tremblay, Logic and Discrete Mathematics, Pearson.
  4. Richard Johnsonbaugh, Discrete Mathematics, 8th Edition, Pearson.
  5. Bernard Kolman, Robert C Busby, and Sharon Cutler Ross, Discrete Mathematical Structures, 6th Edition, Pearson.
  6. Thomas Koshy, Discrete Mathematics with Applications, Elsevier.
  7. C L Liu, Elements of Discrete Mathematics, 4th Edition, Tata McGraw-Hill.
  8. Kenneth H Rosen (Editor-in-chief), Handbook of Discrete and Combinatorial Mathematics, 2nd Edition, CRC Press.
  9. Cliff L Stein, Robert Drysdale, and Kenneth Bogart, Discrete Mathematics for Computer Scientists, Pearson.
  10. Jean-Paul Tremblay and R Manohar, Discrete Mathematical Structures with Applications to Computer Science, Tata McGraw-Hill.

Tutorials and Practice Problems

Tests

Previous course pages: 2007 | 2006 | 2005

 CS21001 Discrete Structures Autumn 2019, L-T-P: 3-1-0