UPTU Discrete Mathematics Syllabus

Please provide me the detailed syllabus for the Uttar Pradesh Technical university discrete syllabus for the Mathematics subject?

[pawan]

The detailed syllabus for the Uttar Pradesh Technical university discrete syllabus for the Mathematics subject is as follows:

Unit-I
Set Theory: Introduction , Combination of sets , Multisets , Ordered pairs.
Proofs of some general identities on sets.
Relations: Definition , Operations on relations , Properties of relations , Composite Relations , Equality of relations , Recursive definition of relation , Order of relations.
Functions: Definition , Classification of functions , Operations on functions , Recursively defined functions. Growth of Functions.
Natural Numbers: Introduction , Mathematical Induction , Variants of Induction , Induction with Nonzero Base cases.
Proof Methods , Proof by counter – example , Proof by contradiction.

Unit-II
Algebraic Structures: Definition , Groups , Subgroups and order , Cyclic Groups , Cosets ,
Lagrange's theorem , Normal Subgroups , Permutation and Symmetric groups ,
Group Homomorphisms , Definition and elementary properties of Rings and Fields , Integers Modulo n.

Unit-III
Partial order sets: Definition , Partial order sets , Combination of partial order sets ,
Hasse diagram , Lattices: Definition , Properties of lattices – Bounded , Complemented , Modular and Complete lattice.
Boolean Algebra: Introduction , Axioms and Theorems of Boolean algebra , Algebraic manipulation of Boolean expressions.
Simplification of Boolean Functions , Karnaugh maps , Logic gates , Digital circuits and Boolean algebra.

Unit-IV
Propositional Logic: Proposition , well formed formula , Truth tables , Tautology , Satisfiability , Contradiction , Algebra of proposition , Theory of Inference , Predicate Logic: First order predicate, well formed formula of predicate , quantifiers , Inference theory of predicate logic.

Unit-V
Trees : Definition , Binary tree , Binary tree traversal , Binary search tree.
Graphs: Definition and terminology , Representation of graphs , Multigraphs , Bipartite graphs , Planar graphs , Isomorphism and Homeomorphism of graphs , Euler and Hamiltonian paths , Graph coloring.
Recurrence Relation & Generating function: Recursive definition of functions , Recursive algorithms , Method of solving recurrences.
Combinatorics: Introduction, Counting Techniques, Pigeonhole Principle

References:
1. Liu and Mohapatra, “Elements of Distcrete Mathematics”, McGraw Hill
2. Jean Paul Trembley, R Manohar, Discrete Mathematical Structures with Application to Computer Science, McGraw-Hill
3. R.P. Grimaldi, Discrete and Combinatorial Mathematics, Addison Wesley,
4. Kenneth H. Rosen, Discrete Mathematics and Its Applications, McGraw-Hill,
5. B. Kolman, R.C. Busby, and S.C. Ross, Discrete Mathematical Structures, PHI

UPTU Previous Year Exam Papers
B Tech 3rd Semester
Discrete Mathematics 2010-11
Note : (I) Attempt all questions.
(2) Each question carries equal marks.

1. Attempt any four parts of the following:—
(a) If R is an equivalence relation on a set A, then show that R_l is also an equivalence relation on A.
(b) If R = {(a, b), (b, c), (c, a)} and A = {a, b, c}, then find reflexive, symmetric and transitive closure of R by the composition of relation R.
(c) Show that for any two sets A and B
A – (A n B) = A – B, without Venn diagram.
(d) What are the recursively defined functions ? Give the recursive definition of factorial function.
(e) Let f, g, h e R be defined as
f(x) = x + 2, g(x) = x – 2, h(x) = 3x v x e R.
Find g o f, h o f and f o h o g.
(f) State and prove Pigeon hole principle.
2. Attempt any four parts of the following:-
(a) Consider the operator * defined on z, the set of integers As a * b = a + b + I for all x, y e z. Show that (z, *) is an abelian group.
(b) Show that every cyclic group is abelian but the converse is not true.
(c) For a Group G prove that G is abelian iff
(ab)2 = a2 b2 v a, b e G
(d) If H and K are any two subgroups of a group G, then show that HuK will be a subgroup iff H c K or K c H.
(e) Define field with one example.
(f) Consider a ring (R, +, •) defined by a • a = a. Determine whether the ring is commutative or not.
3. Attempt any two parts of the following:—
(a) Construct the truth table :
(i) (P -» Q) v R) v (P -> Q -> R)
(ii) (P Q) a (P -> R).
(b) Is the statement
((P -> Q) a (Q -► R)) -» (P -> R) a tautology ?
(c) Find out whether the following formula are equivalent or not:—
(i) (P a (P-*<?))-» Q 00 (P->Q)^(lPvQ).
4. Attempt any four parts of the following:—
(a) If x and y denote the pair of real numbers for which 0 < x < y, prove by mathematical induction 0 < x” < y” for all natural number n.
(b) Show that: “C + “C = n+lC. r r-l r
(c) Solve the recurrence relation : a=a_, +a_2,r>2 with a0 = 1, a, – 1.
(d) Find the solution of recurrence relation by generating function method:
3,-2a, , +a,J = 2‘’rS2’a0 = 2’ a! = L
(e) Use quantifiers to say that V3 is not a rational number.
(f) (i) How many selections any number at a time may be
made from three white balls, four green balls, one red ball and one black ball if at least one must be chosen.
(ii) In how many ways can a five-card hand be dealt from a deck of 52 cards ?
5. Attempt any two parts of the following:—
(a) (i) Differentiate between Euler graph and Hamiltonian
graph with examples.
(ii) Show that a Hamiltonian path is a spanning tree.
(b) Define the fol lowing with one example:
(i) Bipartite graph.
(ii) Complete graph.
(iii) Binary tree.
(iv) Chromatic number of a graph.
(v) Isomorphic graphs.
(c) (i) Define degree of a vertex. Prove that the sum of degrees of all vertex of a graph is equal to the twice of the number of edges in a graph.
(ii) Define tree. Show that in a tree of n vertex will have n-I edges.