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.
