Course Material
Course Material
Disclaimer:
The webpage is not to be considered the official webpage of the course Discrete mathematics. It is designed for ease of use to the students and nothing else. All the related links for the assignment, course materials, and forms are available here for Panel B and Panel E of AY 2021-22 T4.
-Prasad Purnaye
To understand the logic for solving problems using set theory and combinatorial problem using probability theory
To gain the knowledge of relations and functions to solve relevant problems in computer science
To learn Graph Theory for modelling computer science problems
To acquire knowledge of concepts and applications of Number Theory.
1. Analyze and Articulate the logic to solve a problem using set theory and combinatorial problem using probability theory
2. Apply knowledge of relations and functions to solve relevant problems in computer science
3. Model computer science problems using Graph theory
4. Demonstrate the concepts and applications of Number Theory in Computer Science.
SET THEORY: Sets, Combinations of sets, Venn Diagrams, Finite and Infinite sets: Uncountable and Countable, Principle of inclusion and exclusion, Multisets, Cartesian Product and Power Set
Fuzzy sets, Basic concepts and types of Fuzzy sets, Operations on Fuzzy sets
FUNCTIONS: Surjective, Injective and Bijective functions,
Inverse Functions and Compositions of Functions, Recursive Function.
RELATIONS: Relations and Their Properties, n-ary Relations and Their Applications, Representing Relations, Closures of Relations, Warshall’s Algorithm to find transitive closure, Equivalence Relations, Partial Orderings - Chain, Anti chain and Lattices.
COUNTING: The Basics of Counting, Permutations and Combinations, Binomial Coefficients, Algorithms for generating Permutations and Combinations, The Pigeonhole Principle, Introduction to groups, types of groups.
GRAPHS: Graph and Graph Models, Graph Terminology and Types of Graph, Representing Graph and Graph Isomorphism, vertex and edge Connectivity, Eulerian and Hamiltonian, Single source shortest path- Dijkstra's pseudo code algorithm, Planar Graph, Graph Coloring, digraphs.
Number Theory and Its Applications: Modular Arithmetic & its properties, The Euclidean Algorithm, Extended Euclidean algorithm, Solving Congruence equations, The Chinese Remainder Theorem, Fermat's Theorem, Primitive Roots and Discrete Logarithms