JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech II MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE Previous Question Paper (November/December - 2017 - 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.
Part A
Represent the proposition “If you have the flee then you miss the final examination” into symbolic form and also its negation.
Answer
- Let p be the proposition "You have the flu".
- Let q be the proposition "You miss the final examination".
- The given statement is a conditional proposition of the form "If p, then q", which is represented symbolically as p → q.
- The negation of a conditional statement p → q is defined as ¬(p → q). Using the logical equivalence p → q ≡ ¬p ∨ q, the negation becomes ¬(¬p ∨ q). By applying De Morgan's Law, this simplifies to p ∧ ¬q.
- In natural language, the negation is: "You have the flu and you do not miss the final examination."
Provide a proof by direct method of the following statement, “If x is odd then x2 is odd”.
Answer
To prove the statement "If x is odd, then x2 is odd" using a direct proof, we proceed as follows:
- Assume the hypothesis is true: Let x be an odd integer.
- By the definition of an odd integer, there exists an integer k such that x = 2k + 1.
- To find x2, we square the expression: x2 = (2k + 1)2.
- Expanding the square, we get x2 = 4k2 + 4k + 1.
- We can factor out a 2 from the first two terms: x2 = 2(2k2 + 2k) + 1.
- Let m = 2k2 + 2k. Since k is an integer, m must also be an integer because the set of integers is closed under addition and multiplication.
- Substituting m back into the equation, we have x2 = 2m + 1.
- By definition, any number that can be written in the form 2m + 1 for some integer m is an odd integer.
- Therefore, x2 is odd, which completes the proof.
Differentiate partial ordering and total ordering relations.
Answer
Sign in to view the complete answer paper.
Define lattice and write its properties.
Answer
Sign in to view the complete answer paper.
Find out how many 5-digit numbers greater than 30,000 can be formed from the digits 1, 2, 3, 4 and 5.
Answer
Sign in to view the complete answer paper.
In how many ways can we draw a heart or queen from a pack of cards.
Answer
Sign in to view the complete answer paper.
Define recurrence relation and explain recurrence relation for towers of Hanoi.
Answer
Sign in to view the complete answer paper.
Solve recurrence relation an - 4an-1 + 4an-2 = 0, a0 = 0, a1 = 1.
Answer
Sign in to view the complete answer paper.
Define complete graph and wheel graph.
Answer
Sign in to view the complete answer paper.
Define planar graph and write conditions for testing planarity of the graph.
Answer
Sign in to view the complete answer paper.
Part B
State and explain the rules that can generate a well formed formula.
Answer
Sign in to view the complete answer paper.
Show that R → S can be derived from premises, P → (Q → S), (~R ∨ P) and Q.
Answer
Sign in to view the complete answer paper.
Define PDNF and find PDNF for (~P « R) ∧ (Q « P).
Answer
Sign in to view the complete answer paper.
Prove or disprove the validity of the following arguments using the rules of inference: All men are fallible, All kings are men, Therefore, all kings are fallible.
Answer
Sign in to view the complete answer paper.
If a, b are any two elements of a group (G, .) which commute, show that a-1 and b commute, b-1 and a commute, a-1 and b-1 commute.
Answer
Sign in to view the complete answer paper.
Let A = {1,2,3,4,6,8,12,24}, show that the relation 'divides' is partial ordering on A and draw Hasse diagram.
Answer
Sign in to view the complete answer paper.
Let G = {-1, 0, 1}, verify whether G forms a group under usual addition.
Answer
Sign in to view the complete answer paper.
Show that the sets of even numbers and odd numbers are both recursive.
Answer
Sign in to view the complete answer paper.
Find the number of integers between 1 and 250 which are divisible by any of the integers 2, 3, 5 or 7 and hence find the number of integers between 1 and 250 which are not divisible by 2, 3, 5 or 7.
Answer
Sign in to view the complete answer paper.
State and prove binomial theorem.
Answer
Sign in to view the complete answer paper.
The letters of the word VICTORY are rearranged in all possible ways and the words thus obtained are arranged as in a dictionary, what is the rank of the given word?
Answer
Sign in to view the complete answer paper.
Use multinomial theorem to expand (x1+x2+x3+x4)4.
Answer
Sign in to view the complete answer paper.
Solve the recurrence relation an – 5an-1 + 6an-2 = (n+1)2, a0=0, a1=1.
Answer
Sign in to view the complete answer paper.
Solve the recurrence relation an – 7an-1 + 10an-2 = 4n, a0=0, a1=1.
Answer
Sign in to view the complete answer paper.
Explain Fibonacci relation with suitable examples and also solve it.
Answer
Sign in to view the complete answer paper.
Solve an – 7an-1 + 10an-2 = 0, a0=10, a1=41 using generating functions.
Answer
Sign in to view the complete answer paper.
In any planar graph, show that |V| – |E| + |R| = 2.
Answer
Sign in to view the complete answer paper.
Prove that complete graph of 5 vertices is non planar.
Answer
Sign in to view the complete answer paper.
Write an algorithm for breadth-first search spanning tree.
Answer
Sign in to view the complete answer paper.
Write Kruskal’s Algorithm and explain it with an example.
Answer
Sign in to view the complete answer paper.