My Profile
Active Members
TodayLast 7 Days
more...
Awards & Gifts
Online Exams
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: Diamond
|
2007 Andhra Pradesh State Jawaharlal Nehru Technological University, Hyderabad Code No: RR210501 II B.Tech I Semester Supplimentary Examinations, November 2007 DISCRETE STRUCTURES AND GRAPH THEORY [Set No. 4] Question paper
Code No: RR210501 Set No. 4
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) Prove that the relation “congruence modulo m “ given by
= {< x, y > /x - y is divisible by m} over the set of positive integers is
an equivalence relation. [8+8]
(b) Let A be given finite set and ?(A) its power set. Let be the inclusion relation
on the elements of ?(A). Draw Hasse diagram of < ?(A) > for
i. A = {a}
ii. A = {a, b}
iii. A = {a, b, c, d}
3. (a) Define the term ‘lattice’, clearly stating the axioms. [6]
(b) Let C be a collection of sets which are closed under intersection and union.
Verify whether (C, \, [) is a lattice. [10]
4. A graph is said to be self-complementary, if it is isomorphic to its complement.
(a) Draw a self - complementary graph with 4 vertices.
(b) Is there a self-complementary graph with 6 vertices. [8+8]
5. Km,n represents a complete bi partite graph. [5+5+6]
(a) Is there a Hamiltonian circuit in K4,6?
(b) Is there a Hamiltonian path in K4,5?
(c) State a necessary and sufficient condition for the existence of Hamiltonian
circuit in Km,n .
6. Prove whether it is always, never, or some times the nodes are added to the min-
imum spanning tree by the Dijkstra-Prim algorithm is the same as the order in
which they are encountered in a breadth-first traversal. [16]
7. (a) Compute the number of rows of 6 Americans, 7 Mexicans, and 10 Canadians
in which an American invariably stands between a Mexican and a Canadian
and in which a Mexican and a Canadian never stand side by side.
1 of 2
Code No: RR210501 Set No. 4
(b) In how many ways can we choose 3 of the numbers from 1 to 100. So that
their sum is divisible by 3 ? [8+8]
8. Explain the Recurrence relation. What is its application in computer science ex-
plain with suitable examples. [16]
2 of 2
Return to question paper search
|
|
|
Submit Previous Years University Question Papers and make money from adsense revenue sharing program
Are you preparing for a university examination? Download model question papers
and practise before you write the exam.
|
|