Course

Unit 1

Relations and Their Properties – Representing Relations, Closure of Relations, Partial Ordering, Equivalence Relations and partitions, Functions- definition, types, and composition.

Unit 2

Advanced Counting Techniques and Relations – Recurrence Relations, Generating Functions, solving linear Recurrence Relations, Divide and Conquer algorithm, Inclusion-Exclusion.

Unit 3

Graph Theory – Graphs and subgraphs, isomorphism, matrices associated with graphs, degrees, walks, connected graphs, shortest path algorithm, Euler and Hamilton Graphs: Euler graphs, Euler’s theorem, Hamilton cycles, Chinese-postman problem, approximate solutions of traveling salesman problem.

Unit 4

Definition of Groups, Basic Examples – Symmetric Groups, Matrix Groups, Subgroups, Cyclic Group, and Factor Groups; Lagrange’s Theorem; Normal Subgroups; Quotients of Groups.

Unit 5

Linear Transformations, Eigen values and vectors, Diagonalization, Orthogonal Diagonalization, Inner Products, Angle and Orthogonality in Inner Product Spaces, Length of a Vector, Orthogonal Vectors, Orthogonal Complement.

Objective:

• Learn different types of relations, functions, and their properties.
• Familiarize yourself with the advanced counting techniques and graph theory.
• Understand the fundamentals of group theory.
• Learn to implement the concepts of linear transformation, eigenvalues, diagonalization, inner product space, and orthogonality.

Course Outcomes:

CO-PO Mapping

Textbooks:

1. Kenneth H. Rosen, “Discrete Mathematics and its Applications”, Tata McGraw- Hill Publishing Company Limited, New Delhi, Sixth Edition, 2007.
2. I N. Herstein, ‘Topics in Algebra’, Second Edition, John Wiley and Sons, 2000.
3. Gilbert Strang,’ Linear Algebra and its Applications, Fourth Edition, Cengage Learning, 2014
4. Howard Anton and Chris Rorres, ‘Elementary Linear Algebra’, 9th Edition, Wiley, 2005.

References:

1. P. Grimaldi, “Discrete and Combinatorial Mathematics”, Pearson Education, Fifth Edition, 2007.
2. Liu, “Elements of Discrete Mathematics”, Tata McGraw- Hill Publishing Company Limited, 2004.
3. John B. Fraleigh, ‘A First Course in Abstract Algebra’, Narosa Publishing House, 2003.