Currently Empty: ₹0.00
Gate 2025
DISCRETE STRUCTURE (CST-002) UTU
"Discrete Structure" covers mathematical concepts like sets, logic, graphs, and algorithms used in computer science and combinatorics.
- All Levels
- 5
- September 8, 2024
- Certificate of completion
About Course
COURSE OBJECTIVES: The objectives of the course are to:
- To introduce several Discrete Mathematical Structures to serve as tools in the development of theoretical computer science.
- Transform a given problem into a combination of several simpler statements, reach at a solution and prove it logically.
- Enhance the ability to reasoning and presenting the mathematically accurate argument.
- Apply the abstract concepts of graph theory in the modelling and solving of non-trivial.
COURSE OUTCOMES: On successful completion of the course, the student will be able to:
- Develop new models to represent and interpret the data.
- Apply knowledge of mathematics, probability & statistics, graph theory and logics.
- Interpret statements presented in disjunctive normal form and determine their validity by applying the rules and methods of propositional calculus.
- Reformulate statements from common language to formal logic using the rules of propositional and predicate calculus.
- Apply graph theory in solving computing problems.
Course Content :-
Unit 1- Set Theory:
Introduction to set theory, set operations, Algebra of Sets, Combination of sets, Duality, Finite and infinite sets, Classes of sets, Power sets, Multi sets, Cartesian Product, Representation of relations, Types of relation, Binary relation, Equivalence relations and partitions, Mathematics Induction.
Function and its types: Composition of function and relations, Cardinality and inverse relations, Functions, logic and proofs injective, surjective and bijective functions.
Unit 2- Propositional Calculus:
Basic operations; AND(^), OR(v), NOT(~), True value of a compound statement, propositions, tautologies, and contradictions. Partial ordering relations and lattices.
Lattice theory: Partial ordering, posets, lattices as posets, properties of lattices as algebraic systems, sublattices, and some special lattices.
Unit 3-Combinations:
The Basic of Counting, Pigeonhole Principles, Permutations and Combinations, Principle of Inclusion and Exclusion.
Recursion and Recurrence Relation: linear recurrence relation with constant coefficients, Homogeneous solutions, Particular solutions, and Total solution of a recurrence relation using generating functions.
Unit 4- Algebraic Structures:
Definition, elementary properties of Algebraic structures, examples of a Monoid, sunmonoid, semigroup, groups and rings, Homomorphism, Isomorphism and automorphism, Subgroups and Normal subgroups, Cyclic groups, Integral domain and fields, Rings, Division Ring.
Unit 5- Graphs and Trees:
Introduction to graphs, Directed and undirected graphs, Homomorphic and Isomorphic graphs, Subgraphs, cut points and bridges, Multigraph and Weighted graphs, Paths and circuits, Shortest path in a weighted graph, Eulerian path and circuits, Hamilton paths and circuits, Planar graphs, Euler’s formula, Trees, Rooted trees, Spanning trees and cut-sets, Binary trees and its traversals.
Course Content
Unit 1- Set Theory:
-
Introduction to set theory
-
Set operations
-
Algebra of Sets
-
Combination of sets
-
Duality
-
Finite and infinite sets
-
Classes of sets
-
Power sets
-
Multi sets
-
Cartesian Product
-
Representation of relations
-
Types of relation
-
Binary relation
-
Equivalence relations and partitions
-
Mathematics Induction
-
Function and its types:
-
Composition of function and relations
-
Cardinality and inverse relations
-
Functions
-
Logic and proofs injective
-
Surjective and bijective functions
Unit 2- Propositional Calculus:
Unit 3-Combinations:
Unit 4- Algebraic Structures:
Unit 5- Graphs and Trees:
No Review Yet
