JNTU
JNTU B.Tech II MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE Previous Question Paper (April/May - 2018 - R16)
Note: This question paper contains two parts A and B. Part A is compulsory which carries 25 marks. Answer all questions in Part A. Part B consists of 5 Units. Answer any one full question from each unit. Each question carries 10 marks and may have a, b, c as sub questions.
Part A
Construct the truth table for the following formula:
Answer
| P | Q | R | Q∧R | P∨(Q∧R) | ¬(P∨(Q∧R)) | P∨Q | P∨R | (P∨Q)∧(P∨R) |
|---|---|---|---|---|---|---|---|---|
| T | T | T | T | T | F | T | T | T |
| T | T | F | F | T | F | T | T | T |
| T | F | T | F | T | F | T | T | T |
| T | F | F | F | T | F | T | T | T |
| F | T | T | T | T | F | T | T | T |
| F | T | F | F | F | T | T | F | F |
| F | F | T | F | F | T | F | T | F |
| F | F | F | F | F | T | F | F | F |
Explain duality law.
Answer
The duality law states that for any boolean expression, its dual is obtained by interchanging the OR (∨) and AND (∧) operators, and interchanging the identity elements 0 and 1. If two expressions are equivalent, their duals are also equivalent.
Give the formal definition for the composition of binary relations.
Answer
Sign in to view the complete answer paper.
What are the properties of a group?
Answer
Sign in to view the complete answer paper.
State addition principle and give an example of a problem solved by addition principle.
Answer
Sign in to view the complete answer paper.
State pigeon-hole principle.
Answer
Sign in to view the complete answer paper.
What is the general form of a first-order recurrence relation?
Answer
Sign in to view the complete answer paper.
What is the generating function of 1, -1, 1, -1, ...
Answer
Sign in to view the complete answer paper.
If a simple graph G contains n vertices and m edges, how many number of edges are present in Graph G' (complement of G).
Answer
Sign in to view the complete answer paper.
How many edges are present in a complete graph with n vertices? Explain.
Answer
Sign in to view the complete answer paper.
Part B
Show the following equivalence without constructing the truth table:
Answer
Sign in to view the complete answer paper.
Without constructing a truth table, show that A ∧ E is not a valid consequence of A ↔ B, B ↔ (C ∧ D), C ↔ (A ∨ E), A ∨ E.
Answer
Sign in to view the complete answer paper.
Obtain the principal disjunctive and conjunctive normal form of the following formula:
Answer
Sign in to view the complete answer paper.
For the following formulas, let the universe be ℜ. Translate each of the following sentences into a formula (using quantifiers):
i) There is a smallest number.
ii) Every positive number has a square root.
Answer
Sign in to view the complete answer paper.
Consider the Hasse diagram of a partially ordered set P, {x1, x2, x3, x4, x5}. Find the least, greatest, maximal, and minimal elements. Find the upper/lower bounds and LUB/GLB for specified subsets.
Answer
Sign in to view the complete answer paper.
Show that the direct product of groups G1, G2, ..., Gn is a group.
Answer
Sign in to view the complete answer paper.
Find the transitive closure of the relation R = {(1,2),(2,3),(3,4),(4,1)}. Show iR for all values of i that give new elements.
Answer
Sign in to view the complete answer paper.
Find all the subgroups of (i) (Z12, +12); and (ii) (Z7*, ×7).
Answer
Sign in to view the complete answer paper.
In the United States and Canada, a telephone number is a 10-digit number of the form NXX-NXX-XXXX. Calculate the total possible phone numbers, number of area codes needed for a city with 23,000,000 phones, and the difference between the new and old formats.
Answer
Sign in to view the complete answer paper.
How many four letter words can be formed using the letters a,a,a,b,b,c,c,c,c,d,d?
Answer
Sign in to view the complete answer paper.
Expand (2x - y)^7 using the Binomial Theorem.
Answer
Sign in to view the complete answer paper.
Solve the recurrence relation an = 2an-1 + 3an-2 for n ≥ 2 where a0 = 2 and a1 = 2.
Answer
Sign in to view the complete answer paper.
Using generating function find an in terms of n if a0 = 1, a1 = 2 and an+2 = 5an+1 - 4an for n ≥ 0.
Answer
Sign in to view the complete answer paper.
Solve the recurrence relation T(n) = 4T(n-1) + 2, with T(0) = 6.
Answer
Sign in to view the complete answer paper.
Find the coefficient of x^2005 in the generating function 1 / (1 + 5x^2).
Answer
Sign in to view the complete answer paper.
Determine whether the given pair of graphs is isomorphic.
Answer
Sign in to view the complete answer paper.
Determine whether the following graph has an Euler circuit or path.
Answer
Sign in to view the complete answer paper.
How do you test the planarity of a graph? Explain.
Answer
Sign in to view the complete answer paper.
What are the chromatic numbers of the graph G and H?
Answer
Sign in to view the complete answer paper.