Discrete Structure (CS-302) - Important Questions

Define the pigeonhole principle and write the contrapositive of the implication "if it is Sunday then it is a holiday".

State the pigeonhole principle and prove it by mathematical induction, including the application that among 15 people at least two share the same birth month.

Prove that congruence modulo $m$ (in particular $x-y$ is a multiple of $3$) on integers is an equivalence relation.

Show that the relation $(a,b) R (c,d)$ iff $a+d = b+c$ is an equivalence relation.

Using Venn diagrams for given finite sets, determine and shade specified set operations and verify equivalence by listing elements.

Define countable and uncountable sets and prove that the set of rational numbers is countable.

Define an equivalence relation and illustrate it on $S=\{1,2,3,4,5,6\}$ by same remainder upon division by $3$.

Using Venn diagram, prove:

$$A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$$

Define relation and explain equivalence relation and partial ordering relation with suitable examples.

Explain a recursively defined function. Solve the recurrence relation $f(n) = f(n - 1) + 3$ with initial condition $f(0) = 2$.

Check whether the given relation on $A=\{1,2,3\}$ is an equivalence relation and find its equivalence classes.

Define one-one, onto and bijective functions and prove that the inverse of a function exists if and only if the function is bijective.

Find the identity element of the group $\mathbb{Z}$ with operation $a * b = a+b-2$.

Show that every Cyclic group is Abelian. Prove that a lattice with 5 elements is not a Boolean algebra.

Prove that a given finite modular set is an abelian group and identify identity and inverses.

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

Prove or disprove that the intersection of two normal subgroups of a group $G$ is again a normal subgroup of $G$.

Define a homomorphism between groups and verify whether $f:\mathbb{R}\to\mathbb{R}$ given by $f(x)=2x$ is a homomorphism under addition.

Define group and Abelian group and prove that the identity element of a group is unique.

Find all subgroups of the group $Z_8$.

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

Show that $f:(S,*)\to(\mathbb{Q},\times)$ defined by $f(a,b)=a/b$ is a homomorphism and find the congruence relation $x\sim y$ iff $f(x)=f(y)$.

Define group and explain the properties of groups.

Prove that $F = \{a + b\sqrt{2}; a, b \text{ rational}\}$ is a field.

Define finite state machine and explain FSM as a language recognizer.

Explain the various Rules of Inference for Propositional Logic.

Construct the truth table for $(p \to q) \to r$ and determine whether it is a tautology or contradiction.

Construct the truth table for $(p \to q) \leftrightarrow (\neg p \lor q)$ and show it is a tautology.

Define predicates in propositional logic and define universal and existential quantifiers with examples.

Convert the statement "Every student studies Discrete Mathematics" into predicate logic and write its negation.

Design a finite state machine that accepts all binary strings ending with 01.

Find the principal / conjunctive normal form (PCNF/CNF and PDNF) of a given propositional formula

Prove that $p \wedge q \implies q \vee p$ is a tautology and that $(p \vee q) \wedge (\sim p) \wedge (\sim q)$ is a contradiction.

Prove the validity of the propositional argument: if the races are fixed then casinos are crooked, tourist trade declines, police will be happy, police are never happy, therefore races are not fixed.

Explain the various rules of inference for propositional logic.

Prove the validity of the argument: if the races are fixed so the casinos are crooked, then the tourist trade will decline; if the tourist trade decreases, then the police will be happy; the police force is never happy; therefore, the races are not fixed.

Explain complete digraph and Euler graph with suitable examples.

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

Show that no graph exists with vertex degrees 1, 3, 4, 2, 3.

Define graph isomorphism, give an example, and explain steps to discover or verify isomorphism including via adjacency matrices.

Define graph theory and explain basic terminology such as vertices, edges, degree and adjacency.

For a given graph, determine whether it has an Eulerian path or circuit and find all Hamiltonian circuits.

Define Euler path and Euler circuit and state necessary and sufficient conditions for their existence.

Explain Dijkstra's Algorithm and find the shortest path from a given source vertex in a weighted graph.

Explain Euler graph, isomorphic graphs, minimal spanning tree, and height of a tree

Consider the complete weighted graph $G$ in the following figure with 5 vertices. Find a Hamiltonian circuit of minimal weight.

Discuss the various applications of graph colouring.

State Euler's formula for a planar graph and verify it with an example having 5 vertices and 5 regions.

Draw the Hasse diagram of a given finite set under the divisibility relation.

Obtain the generating function for a finite constant sequence of 4's and explain a complete digraph.

Count numbers from 1 to 500 not divisible by 2, 3, 5 or 7.

Count ways to select a sample of 4 bulbs from 10 bulbs with 3 defective under given good/defective compositions.

Solve the recurrence $G(K) - 7G(K-1) + 10G(K-2) = 8K + 6$ using generating functions.

In a distributive lattice, prove cancellation: if $a \wedge b = a \wedge c$ and $a \vee b = a \vee c$ then $b = c$.

Count permutations of the word MATHEMATICS with all vowels together.

Define a lattice and prove that every finite lattice has a unique least upper bound and greatest lower bound.

Prove that the complement of each element in a Boolean algebra B is unique.

Draw the Hasse diagrams of $(P(A), \subseteq)$ for finite sets $A$.

Draw the directed graph and the Hasse diagram of $\le$ on $A = \{4,5,6,7\}$.

For the given lattice M, find the non-zero join-irreducible elements and atoms, and determine whether M is distributive and complemented.

Discuss in brief any two of the following:

i) Partial ordering relation ii) Cosets iii) Disjunctive normal form iv) Pigeonhole principle