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. 1] Question paper

Course: B.Tech

University: Jawaharlal Nehru Technological University

Code No: RR210501 Set No. 1
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) Show that the relation of congruence modulo m has m distinct equivalence
classes [8+8]
(b) Let C be a collection of sets which are closed under intersection and union.
Verify whether (C, \, [) is a lattice.
3. (a) If f : X!Y and g : Y!X the function g is equal to f-1 only if g • f = Ix and
f •g = Iy .Prove the result . [8+8]
(b) Let f : R ! R and g : R ! R where R is the set of real numbers. Find f •
g and g • f where f(x) = x2 - 2, g(x) = x + 4. State whether these functions
are injective, subjective or objective.
4. (a) Define bigraph and their properties. [4+4+8]
(b) Find the diameter of Bipartite graph Km,n
(c) A graph is Bipartite prove that all the cycles of the graph are even cycles.
5. (a) State and explain the Four - Colour problem for planar graphs. [6+10]
(b) Prove that the regions of a plane graph can be 4 - coloured if G has a Hamil-
tonian cycle.
6. (a) Show how to represent a linked list as an almost complete binary tree in which
each list element is represented by one tree node. [8+8]
(b) Describe the concept of trees and also explain how they are represented? Also
list their uses in problem solving.
7. A shop sells 20 different flavors of ice cream. In how many ways can a customer
choose 4 ice cream cones ( one dip of ice cream per cone ) ?
(a) if they are all of different flavors ? [4]
(b) are not necessarily of different flavors ? [4]
(c) contain only 2 (or ) 3 flavors ? [4]
(d) contain 3 different flavors ? [4]
1 of 2
Code No: RR210501 Set No. 1
8. Solve the recurrence relation an-7an-1+26an-2 - 24an-3=0 for n 2. [16]

2 of 2

Return to question paper search

Next Question Paper: Code No: RR212304 II B.Tech I Semester Supplimentary Examinations, November 2007 BIO-CHEMISTRY [ Set No. 4]

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