Attempt all the questions.Each question carries equal marks. Parts of a question must be answered together.
Q1. Show that the necessary condition for a simple connected graph to be planar is e ≤ 3n - 6 where e and n denote total number of edges and vertices of the graph respectively.
Q2. Solve the following recurrence using Master theorem method:
T(n) = 4 T(n/2) + n2
Q3. Describe CONVOLUTION of two numeric functions with suitable example.
Q4. Show that the following premises are inconsistent:
(a) If Jack misses many classes through illness ,then he fails high school.
(b) If Jack fails high school ,then he is uneducated.
(c) If Jack reads a lot of books ,then he is not uneducated.
(d) Jack misses many classes through illness and reads a lot of books.
Q5. Solve the following recurrence:ar = ( ar-1 )7 / ( ar-2 )12 , a0 = 1 , a1 = 2
Q6. Prove that a graph with n vertices and n - 1 edges and no circuit is connected or prove that a tree is a connected graph.
Q7. If a simple graph has vertices ,find the maximum and minimum number of edges in that graph. Q8.Prove that in a tree with two or more vertices ,there are at least two pendant vertices (leaves).
Q9. Determine an equivalent numeric function of the generating function A(Z) = 1 / ( 1- 4Z2 ).
Q10. Let f(n) = 2n2 + 5n + 5. Express f(n) in Big oh notation .Also find the necessary constants.
Q11. What do you mean by chromatic number of a graph ? Explain with a suitable example.
Q12. Use Kruskal's algorithm to determine a minimal spanning tree of the following connected weighted graph:
Q13. Check the validity of the following arguments:
All intelligent persons are Engineers.
John is not an Engineer.
Therefore, John is not intelligent.
Q14. How many people among 200,000 people are born at the same time ( hour, minute ,seconds) ?
Q15. Use mathematical induction to show that n! ≥ 2n-1 , n = 1 ,2 ,3,......