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

## Schedule

InstructorsSection 1: Abhijit Das

Section 2: Aritra HazraTimingSlot D4 [MON(12:00–12:55), TUE(10:00–11.55), THU(08:00–08:55)] VenueSection 1: NR223

Section 2: NR424Teaching AssistantsAnirban 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, 2019Sectioning 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 logicSyntax, semantics, valid, satisfiable and unsatisfiable formulas, encoding and examining the validity of some logical arguments.

Proof techniquesForward proof, proof by contradiction, contrapositive proofs, proof of necessity and sufficiency.

Sets, relations

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

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

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

Algebraic structures

and morphismsAlgebraic 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 treesGraphs 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 PSome other references are listed below.Grimaldi,Discrete and Combinatorial Mathematics, 5th Edition, Pearson, 2004.

- Michel O
Albertsonand Joan PHutchinson,Discrete Mathematics with Algorithms, Wiley.- Norman L
Biggs,Discrete Mathematics, Oxford University Press.- Winfried Karl
Grassmannand Jean-PaulTremblay,Logic and Discrete Mathematics, Pearson.- Richard
Johnsonbaugh,Discrete Mathematics, 8th Edition, Pearson.- Bernard
Kolman, Robert CBusby, and Sharon CutlerRoss,Discrete Mathematical Structures, 6th Edition, Pearson.- Thomas
Koshy,Discrete Mathematics with Applications, Elsevier.- C L
Liu,Elements of Discrete Mathematics, 4th Edition, Tata McGraw-Hill.- Kenneth H
Rosen(Editor-in-chief),Handbook of Discrete and Combinatorial Mathematics, 2nd Edition, CRC Press.- Cliff L
Stein, RobertDrysdale, and KennethBogart,Discrete Mathematics for Computer Scientists, Pearson.- Jean-Paul
Tremblayand RManohar,Discrete Mathematical Structures with Applications to Computer Science, Tata McGraw-Hill.## Tutorials and Practice Problems

- Basic counting, logic, induction
- Induction, loop invariance
- Functions, relations, pigeon-hole principle
- Equivalence relations, partial orders, lattices
- Countable and uncountable sets
- Generating functions
- Recurrence relations
- Divide-and-conquer recurrences, introduction to rings
- Rings, subrings, ideals, modular arithmetic, ring homomorphisms
- Rings (conclusion), groups (introduction)
- Groups
## Tests

- Class Test 1: 05-Sep-2019, 06:15pm–07:30pm, F-116/F-142
- Class Test 2: 04-Nov-2019, 06:15pm–07:20pm, F-116/F-142
- Mid-Semester Test: 24-Sep-2019, 02:00pm–04:00pm, Nalanda [Evaluation strategy and common mistakes]
- End-Semester Test: 27-Nov-2019, 09:00am–12:00noon, Nalanda [Evaluation strategy and common mistakes]
## Previous course pages: 2007 | 2006 | 2005

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