Unit No | Topics |
---|---|

Sets and propositions | combination, finite, uncountably infinite and infinite sets, mathematical induction, principles of inclusion and exclusion, propositions |

Permutations, combinations, discrete probabilities | rules of sums and products, permutations, combinations, generation, discrete probability, conditional probability, information |

Relations and functions | relational model of data bases, properties of binary relations, equivalence relation, partitions, partial ordering, lattices, chains and antichains, functions and pigeon-hole principle |

Graphs | Basic terminology, multi- and weighted graphs, paths, circuits, shortest path, Eulerian path, Travelling Salesman problem, factors of a graph, planar graphs |

Trees | trees, rooted trees, path length, prefix codes, binary search trees, spanning trees and cut-sets, minimum spanning trees, transport networks |

Finite-state machines | FSM as models of physical systems, equivalent machines, FSM as language recognizer |

Analysis of algorithms | time complexity of algorithms, example of shortest path algorithm, complexity, tractable and non-tractable problems |

Computability and Formal languages | Russel's paradox and non-computability, ordered sets, languages, phrase structured grammars, types of grammars and languages |

Recurrence relations | linear recurrence relations with constant coefficient, homogeneous, particular and total solutions, generating functions, sorting algorithms, matrix multiplication |

Discrete numerical functions | manipulations of numerical functions, asymptotic behavior, generating functions, combinatorial problems |

Group | groups and sub-groups, generators, evaluation of powers, cosets, Lagrange's theorem, permutation group and Burnsides theorem, group codes, isomorphism, automorphism, homomorphism, normal subgroups, rings, integral domains and fields, ring homomorphism, polynomial rings and cyclic codes |

Lattices and Boolean algebras | Lattices and algebraic systems, principle of duality, properties of algebraic systems, distributive lattices, boolean algebras, uniqueness, boolean functions and expressions, propositional calculus |

Attachment | Size |
---|---|

ELECTIVE VI (Discrete Mathematics) .pdf | 109.79 KB |