JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech II Year MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE Previous Question Paper (September/October - 2023 - R13)

List the applications of propositional logic.

Write Converse, opposite for the statement “If 2+2=8 then sun rises in the east”.

Define a Function.

Represent the following relation R on the set X={1,2,3} in matrix form and graph form R = {(1,1),(2,2),(3,3),(2,3),(3,1),(1,3)}.

List the applications of Pigeonhole principle.

How many 4-digit numbers are possible with the digits 1,3,4,6,7,9 if repetition of digits are allowed.

A sequence is given as 1,1,1,2,2,2,3,4,4,5. Compute generating function for this sequence.

Solve the following recurrence relation by substitution method : a_n = a_n-1 + n.

A connected graph G contains 5 vertices and 10 edges. What is the number of edges that has to be deleted from G to form a tree?

Graph can be represented with adjacency matrix and adjacency list. Give differences between these two methods.

Convert (P→Q) ∧ (P→¬Q) in principal conjunctive normal form.

Show that R → S can be derived from the premises P → ( Q → S ) , ¬R ∨ P and Q.

Derive P → ¬S from P → (Q ∨ R) , Q → ¬P , S → ¬R , P by applying inference rules.

Obtain Principal Conjunctive Normal Form (PCNF) for the following formula: (P∨Q) ∧ (¬Q∨R) ∧ (Q→R).

Draw the Hasse diagram for the divisibility on the set {1,2,3,6,12,24,36,48,96}.

Consider the following relation R on the set {1, 2, 3, 4}. Determine whether it is reflexive, irreflexive, symmetric, anti-symmetric and transitive : R={(1,1),(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}.

Let X = {1,2,3,4,5,6} and relation R on set X is defined as R = {(a,b) | a-b is divisible by 3} . Show that R is an equivalence relation.

Show that the relation R = {(a,b) | if a divides b} on set X={1,2,3,4,6,8,12,16,32,36} is partial ordered relation and draw Hasse diagram for it.

Find the number of ways of distributing 50-similar balls into 4 distinct boxes such that first two boxes should contain atleast two balls and next two boxes must contain atleast three ball.

List 3-combinations and 3-permutations of {4a,5b,1c,2d}.

Expand the multinomial (2x₁+4x₂+x₃)⁴.

Find the number of integral solutions to x₁+x₂+x₃+x₄ = 50, where x₁ ≥ 4, x₂ ≥ 7, x₃ ≥ 1, x₄ ≥ 10.

Solve the following recurrence relation using generating function: a_n - 5 a_n-1 + 6 a_n-2 = 0 for n ≥ 2, and a₀ = 1 and a₁ = - 2.

Solve the following recurrence relation F_n = F_n-1 + F_n-2, where F₀=1, F₁=1.

Solve a_n - a_n-1 = 2ⁿ for n ≥ 1, where a₀ = 2.

Find a general expression for a_n using generating functions a_n - 2a_n-1 + a_n-2 = 0, n ≥ 2.

Verify the graphs K₅ (Complete Graph with 5 vertices), K₄(Complete Graph with 4 vertices), K_4,3 (Complete Bi-Partite Graph), K_2,4(Complete Bi-Partite Graph) are planar graphs or not? Explain.

Verify whether the following two graphs are isomorphic or not? Justify your answer.

Apply Kruskal's algorithm and Prime's algorithm to find minimal spanning tree on the following graph and compare these two methods.

Define Chromatic number of a graph. Compute the chromatic number of the following graph.