Discrete Structure (IT-302) - Important Questions

Define the pigeonhole principle and explain it with a suitable example.

Prove by mathematical induction that 5^{2n}-1 is divisible by 24 for any positive integer n.

Prove that congruence modulo m on integers is an equivalence relation. In particular show that divisibility of x-y by 3 defines an equivalence relation.

Prove that the set {0,1,...,n-1} under addition modulo n is an abelian group and identify identity and inverses. Illustrate for n=4.

What is a ring? Define elementary properties of a ring with example.

Prove or disprove that intersection of two normal subgroups is normal, and define subgroup, normal subgroup and quotient group with an example for each.

Construct truth table(s) for the given propositional formula(s) in p,q,r and determine whether they are tautologies, contradictions, or neither.

Explain the various Rules of Inference for Propositional Logic with suitable examples.

Define predicates and explain universal and existential quantifiers with examples.

Define a planar graph and prove Euler's formula v - e + r = 2 for any connected planar graph.

Explain complete digraph and Euler graph with suitable examples.

Prove that no graph exists with degree sequence 1, 3, 4, 2, 3 on 5 vertices.

Draw the Hasse diagram for a divisibility poset, e.g., for the set {1,2,3,6,9,18} under divides and for positive divisors of 36.

Define a lattice and prove monotonicity: if a <= b and c <= d then a ∨ c <= b ∨ d and a ∧ c <= b ∧ d.

Solve the second-order recurrence G(K)-7G(K-1)+10G(K-2)=8K+6 using generating function.

Using inclusion-exclusion with 2, 3, 5 and 7, find the count of integers divisible by at least one of them versus divisible by none of them between 1 to 500.