Discrete Structures – BCA

DISCRETE STRUCTURES – BCA 1st Semester NEP Syllabus 2021 Bangalore City University

UNIT – I

Set Theory and Logic: Fundamentals of Set theory, Set Operations and the Laws of Set Theory, Counting and Venn Diagrams, Cartesian Products and Relations, Functions–One-to-One, Onto Functions, Function Composition and Inverse Functions.

Mathematical Induction, The well ordering principle, Recursive Definitions, Structural Induction, Recursive algorithms. Fundamentals of Logic, Propositional Logic, Logical Connectives and Truth Tables, Logic Equivalence, Predicates and Quantifiers.

UNIT – II

Counting and Relations: Basics of counting, Pigeonhole Principle, Permutation and Combinations, Binomial coefficients. Recurrence relations, Modeling with recurrence relations with examples of Fibonacci numbers and the tower of Hanoi problem.

Divide and Conquer relations with examples (no theorems). Definition and types of relations, Representing relations using matrices and digraphs

UNIT – III

Matrices: Definition, order of a matrix, types of matrices, operations on matrices, determinant of a matrix, inverse of a matrix, rank of a matrix, linear transformations, applications of matrices to solve system of linear equations.

UNIT – IV  

Graph Theory: Graphs: Introduction, Representing Graphs, Graph Isomorphism, Operations on graphs. Trees: Introduction, Applications of Trees, Tree Traversal, Spanning Trees, Minimum Spanning Trees

Prim’s and Kruskul’s Algorithms. Connectivity, Euler and Hamilton Paths, Planar Graphs. Directed graphs: Fundamentals of Digraphs, Computer Recognition – Zero-One Matrices and Directed Graphs, Out-degree, in-degree, connectivity, orientation, Eulerian and Hamilton directed graphs, tournaments.