CS21001: Discrete Structures
| CS21001 | |||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Course name | Discrete Structures | ||||||||||||||||||||||||||
| Offered by | Computer Science & Engineering | ||||||||||||||||||||||||||
| Credits | 4 | ||||||||||||||||||||||||||
| L-T-P | 3-1-0 | ||||||||||||||||||||||||||
| Previous Year Grade Distribution | |||||||||||||||||||||||||||
| |||||||||||||||||||||||||||
| Semester | Autumn | ||||||||||||||||||||||||||
Syllabus
Syllabus mentioned in ERP
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, Cantos diagonal argument and the power set theorem, Schroeder-Bernstein theorem.Introduction to counting: Basic counting techniques - inclusion and exclusion, pigeon-hole principle, permutation, combination, summations. Introduction to recurrence relation and generating function.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.Introduction to graphs: Graphs and their basic properties- degree, path, cycle, subgraphs, isomorphism, Eulerian and Hamiltonian walks, graph coloring, planar graphs, trees.References1.Kenneth H. Rosen, Discrete Mathematics and its Applications, Tata McGraw-Hill.2.C. L. Liu, Elements of Discrete Mathematics, Tata McGraw-Hill.3.Norman L. Biggs, Discrete Mathematics, Oxford University Press.4.Kenneth Bogart, Clifford Stein and Robert L. Drysdale, Discrete Mathematics for Computer Science, Key College Publishing.5.Thomas Koshy, Discrete Mathematics with Applications, Elsevier.6.Ralph P. Grimaldi, Discrete and Combinatorial Mathematics, Pearson Education, Asia.
Concepts taught in class
Student Opinion
How to Crack the Paper
If DRC is taking your course then don't miss out on the smaller topics like dearrangement, equivalence classes, relations. There will be more questions from these smaller topics than from major topics like pigeonhole and propositional logic.
Classroom resources
Additional Resources
Time Table
| Day | 8:00-8:55 am | 9:00-9:55 am | 10:00-10:55 am | 11:00-11:55 am | 12:00-12:55 pm | 2:00-2:55 pm | 3:00-3:55 pm | 4:00-4:55 pm | 5:00-5:55 pm | |
|---|---|---|---|---|---|---|---|---|---|---|
| Monday | NC441/444 | |||||||||
| Tuesday | NC441/444 | NC441/444 | ||||||||
| Wednesday | ||||||||||
| Thursday | NC441/444 | |||||||||
| Friday |