Fresher Jobs

Our fresher job section is exclusively for fresh graduates! Find jobs for freshers in major Indian cities including Bangalore, Chennai, Hyderabad, Pune or Kochi

Resources

Find educational articles, blogs, discussion threads and other resources.

Colleges

Find details about any college in India or search for courses.

Download Model question papers & previous years question papers

Posted Date: 31 Oct 2009 Posted By: Sree.... Member Level: Platinum

2007 Andhra Pradesh State Jawaharlal Nehru Technological University Code No: RR210501 II B.Tech I Semester Supplimentary Examinations, November 2007 DISCRETE STRUCTURES AND GRAPH THEORY [Set No. 3] Question paper

Course: B.Tech

University: Jawaharlal Nehru Technological University

Code No: RR210501 Set No. 3
II B.Tech I Semester Supplimentary Examinations, November 2007
DISCRETE STRUCTURES AND GRAPH THEORY
( Common to Computer Science & Engineering, Information Technology,
Computer Science & Systems Engineering and Electronics & Computer
Engineering)
Time: 3 hours Max Marks: 80
Answer any FIVE Questions
All Questions carry equal marks

1. With reference to automatic theorem proving, show that SVR is tautologically
implied by (P_Q) ^ (P ! R)^(Q!S) [16]
2. (a) What are the properties of the relation r = ( i, j ) / |i - j| = 2 on the set
A = { 1, 2, 3, 4, 5, 6 }. [8+8]
(b) Determine all the bijections from { 1, 2, 3 } on to {a, b, c, d}.
3. (a) If f : X!Y and g : Y!Z and both f and g are onto; show that g • f is also
onto. Is g • f is one to one if both g and f are one to one? Justify. [8+8]
(b) Let D(x) denote the number of divisions of x. Show that D(x) is primitive
recursive.
4. Prove that any 2 simple connected graphs with n vertices, all of degree 2, are
isomorphic. [16]
5. (a) Prove that the Kuratowskis second graph consisting of 6 vertices and 9 edges
is non-planar.
(b) State criteria to detect the planarity of a connected graph and give an example
also. [8+8]
6. (a) Write the Algorithm for traversing a tree in preorder. Give an example. [8+8]
(b) What are the application areas where preorder traversal can be implemented.
Give at least four examples.
7. (a) Explain about Enumerating permutations with constrained repetitions. [8+8]
(b) Compute the number of 10-digit numbers which contain only the digits 1,2
and 3 with the digit 2 appearing in each number exactly twice.
8. Solve the recurrence relation an-7an-1+26an-2 - 24an-3=0 for n 2. [16]

1 of 1

Return to question paper search

Next Question Paper: Code No: RR210501 II B.Tech I Semester Supplimentary Examinations, November 2007 DISCRETE STRUCTURES AND GRAPH THEORY [Set No. 2]

Previous Question Paper: Code No: RR210501 II B.Tech I Semester Supplimentary Examinations, November 2007 DISCRETE STRUCTURES AND GRAPH THEORY [Set No. 4]