CS1200 - Discrete Mathematics for Computer Science

#### Syllabus:

• Sets and Sequences : Data Models. - 3L+1T
Finite Sets, Power Set, Cardinality of finite sets, Cartesian Product, Properties of Sets, Vector Implementations of Sets.
• Describing Sets : Logic & Proofs - 15L + 3T
Introduction to Logic. Propositional Logic, Truth tables, Deduction, Resolution, Predicates and Quantifiers, Mathematical Proofs. Infinite sets, well-ordering. Countable and Uncountable sets, Cantor's diagonalization. Mathematical Induction - weak and strong induction.
• Relational Structures on Sets : Relations & Graphs - 9L + 2T
Relations, Equivalence Relations. Functions, Bijections. Binary relations and Graphs. Trees (Basics). Posets and Lattices, Hasse Diagrams. Boolean Algebra.
• Sizes of Sets : Counting & Combinatorics - 12L + 3T
Counting, Sum and product rule, Principle of Inclusion Exclusion. Pigeon Hole Principle, Counting by Bijections. Double Counting. Linear Recurrence relations - methods of solutions. Generating Functions. Permutations and counting.
• Structured Sets : Algebraic Structures - 6L + 2T
Structured sets with respect to binary operations. Groups, Semigroups, Monoids. Rings, and Fields. Vector Spaces, Basis.

#### Textbook:

• Discrete Mathematics and its Applications - Kenneth H. Rosen 7th Edition -Tata McGraw Hill Publishers - 2007

#### References:

• Elements of Discrete Mathematics, C. L Liu, McGraw-Hill Inc, 1985. Applied Combinatorics, Alan Tucker, 2007.
• Concrete Mathematics, Ronald Graham, Donald Knuth, and Oren Patashnik, 2nd Edition - Pearson Education Publishers - 1996.
• Combinatorics: Topics, Techniques, Algorithms by Peter J. Cameron, Cambridge University Press, 1994 (reprinted 1996).
• Topics in Algebra, I.N. Herstein, Wiley, 1975.

#### Learning Outcomes Expected:

After completing the course, the student will be able to:
• Use logical notation to define and reason mathematically about the fundamental data types and structures (such as numbers, sets) used in computer algorithms and systems.
• Comprehend and Evaluate rigor in the definitions and conclusions about mathematical models and identify fallacious reasoning and statements. Identify and Apply properties of combinatorial structures and properties - know the basic techniques in combinatorics and counting.
• Analyze sets with operations, and identify their structure. Reason and Conclude properties about the structure based on the observations.
• Gain the conceptual background needed to be able to identify structures of algebraic nature, and discover, prove and use properties about them.

None

#### Parameters

 Credits Type Date of Introduction 3-1-0-0-6-10 Core Jul 2015

#### Previous Instances of the Course

© 2016 - All Rights Reserved - Dept of CSE, IIT Madras