Unit I
Logic and Proofs
Propositions, Conditional Propositions, Logical Connectivity, Prepositional calculus, Universal and Existential Quantifiers, Proofs, Proof Techniques, Mathematical Induction
Set Theory - Set, Combination of sets, Finite and Infinite sets, Un-countably infinite sets, Principle of inclusion and exclusion (8 Hrs)
Unit II
Combinatorics and Discrete Probability
Permutations and Combinations: rule of sum and product, Permutations, Combinations, Algorithms for generation of Permutations and Combinations.
Discrete Probability, Conditional Probability, Information and Mutual Information, Binomial Coefficients and Combinatorial Identities. (8 Hrs)
Unit III
Relations
Definitions, Properties of Binary Relations, Equivalence Relations and partitions, Partial ordering relations and lattices, Chains and Anti chains.
Functions
Definitions, domain, Range, One-to-One and OnTo, Inverse and Composition, Pigeonhole Principle, Discrete Numeric functions and Generating functions, Job scheduling Problem.
Recurrence Relations
Recurrence Relation, Linear Recurrence Relations With constant Coefficients, Homogeneous Solutions, Total solutions, solutions by the method of generating functions (10 Hrs)
Unit IV
Graphs
Basic terminology, multi graphs and weighted graphs, paths and circuits, shortest path in weighted graph, Hamiltonian and Eulerian paths and circuits, factors of a graph, planer graph and Traveling salesman problem. (8 Hrs)
Unit V
Trees
Trees, rooted trees, path length in rooted trees, prefix codes, binary search trees, spanning trees and cut set, minimal spanning trees, Kruskal’s and prime’s algorithms for minimal spanning tree, The Max flow –Min cut theorem (transport network). (8 Hrs)
Unit VI
Groups and Rings
Algebraic Systems, Groups, Semi Groups, Monoid, Subgroups, Permutation Groups, Codes and Group codes, Isomorphism and Automorphisms, Homomorphism and Normal Subgroups, Ring, Integral Domain, Field, Ring Homomorphism, Polynomial Rings and Cyclic Codes (8 Hrs)
Reference http://www.unipune.ac.in/university_files/syllabi.htm
|
No responses found. Be the first to respond...
|