CS/B.
TECH(N)/EVEN/SEM-4/4407/2023-2024/I007
MAULANA ABUL KALAM AZAD UNIVERSITY OF TECHNOLOGY, WEST BENGAL
Paper Code : PCC- CS401/PCC-CS401/PCCCS 401/PCCCS401 Discrete Mathematics
UPID : 004407
Time Allotted : 3 Hours Full Marks :70
The Figures in the margin indicate full marks.
Candidate are required to give their answers in their own words as far as practicable
Group-A (Very Short Answer Type Question)
1. Answer any ten of the following : [ 1 x 10 = 10 ]
(I) Explain the difference between a permutation and a combination, and provide an example of each.
(II) What is the truth value of ¬(P∧Q)¬(P ∧Q) if P is true and Q is false?
(III) What is an abelian group?
(IV) What is the chromatic number of a graph?
(V) What is composition of mapping?
(VI) If you have 6 different colors of socks, how many ways can you choose 2 pairs (4 socks total)?
(VII) What is the truth value of (P∧¬Q)∨(Q∧¬P)(P ∧¬Q)∨(Q∧¬P ) if P and Q are both true?
(VIII) Define a group in abstract algebra and explain the group axioms.
(IX) What is the minimum number of edges required for a connected graph with n vertices to be a tree?
(X) Define the union of two sets.
(XI) In a city, there are 30 traffic lights. If each traffic light can be either red, yellow, or green, what can you
guarantee about the colors of some traffic lights?
(XII) If p→(q∧r) and r→s are both true, what can you conclude about p→s?
Group-B (Short Answer Type Question)
Answer any three of the following : [ 5 x 3 = 15 ]
2. Prove by mathematical induction 3n<n! for all positive integers n≥6 [5]
3. A drawer contains ten black and ten white socks. You reach in and pull some out without looking at [5]
them. What is the least number of socks you must pull out to be sure to get a matched pair? Explain
how the answer follows from the pigeonhole principle.
4. What is De Morgan's Law in propositional logic? Provide both forms of the law. [5]
5. In a ring R if x3 = x for all x ∈ R, then show that R is commutative. [5]
6. Consider a connected undirected graph G with n vertices and m edges. Prove that if G has no cycles, then [5]
m must be less than n.
Group-C (Long Answer Type Question)
Answer any three of the following : [ 15 x 3 = 45 ]
7. (a) Let G be a group in which for some integer n > 1, (ab)n =anbn for all a, b ∈ G. Show that [5]
a) Gn = { xn | x ∈ G } is a normal subgroup of G.
b) Gn−1 = { xn−1 | x ∈ G } is a normal subgroup of G.
(b) If ϕ : G → H is a homomorphism and G is abelian, then Imϕ = { ϕ(g) | g ∈ G } is abelian. [5]
(c) Prove that any group of order 15 is cyclic. [5]
8. (a) prove that (p→q)∧(q→r)→(p→r) is a tautology [5]
(b) Without truth table find the DNF and CNF of the expression [ 10 ]
~(p ∨ q) ↔ (p ∧ q)
9. (a) State and prove Division Algorithm [8]
(b) Determine the Recursive formula for the sequance 3,9,21..........Also find the 11th term [7]
10. (a) By principle of inclusion and exclusion find the number of 10 combinations of the elements of the [8]
set S containing 5 a's, 4 b's 5 c's and 7 d's
(b) State the first form of Pigeonhole Principle and the prove that in a party where guests are [7]
handshaking among [Link] will always be at least two guests who have shaken hands the
same number of times.
1/2
11. (a) Consider the following directed weighted graph G with vertices V={A,B,C,D,E} and edges with their [8]
corresponding weights:
(A,B,5)
(A,C,3)
(B,C,2)
(B,D,6)
(C,D,7)
(C,E,4)
(D,E,5)
Apply Dijkstra's shortest path algorithm to find the shortest paths from vertex AA to all other
vertices in the graph.
(b) Prove that a simple graph with n vertices and k components can have atmost 1/2(n-k)(n-k+1) edges [7]
*** END OF PAPER ***
2/2
