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: 30 Jul 2008 Posted By: Sonam Member Level: Gold
|
2007 The Institution of Engineers,India A.M.I.E.T.E Electronics & Tele Communication Engineering Code: AC10 Subject: DISCRETE STRUCTURES - December University Question paper
Code: AC10 Subject: DISCRETE STRUCTURES
Time: 3 Hours Max. Marks: 100
NOTE: There are 9 Questions in all.
• Question 1 is compulsory and carries 20 marks. Answer to Q. 1. must be written in the space provided for it in the answer book supplied and nowhere else.
• Out of the remaining EIGHT Questions answer any FIVE Questions. Each question carries 16 marks.
• Any required data not explicitly given, may be suitably assumed and stated.
Q.1 Choose the correct or best alternative in the following: (2x10)
a. Let P(S) denotes the powerset of set S. Which of the following is always true?
(A) (B)
(C) (D)
b. The number of functions from an m element set to an n element set is:
(A) mn (B) m + n
(C) nm (D) m * n
c. A binary Tree T has n leaf nodes. The number of nodes of degree 2 in T is:
(A) log n (B) n
(C) n–1 (D) n+1
d. Push down machine represents:
(A) Type 0 grammer (B) Type 1 grammer
(C) Type-2 grammer (D) Type-3 grammer
e. In how many ways can a party of 7 persons arrange themselves around a circular table?
(A) 6! (B) 7!
(C) 5! (D) 7
f. Which of the following statement is true:
(A) Every graph is not its own subgraph
(B) The terminal vertex of a graph are of degree two.
(C) A tree with n vertices has n edges.
(D) A single vertex in graph G is a subgraph of G.
g. Which of the following proposition is a tautology?
(A) (p v q)?p (B) p v (q?p)
(C) p v (p?q) (D) p?(p?q)
h. What is the converse of the following assertion?
I stay only if you go.
(A) I stay if you go. (B) If you do not go then I do not stay
(C) If I stay then you go. (D) If you do not stay then you go.
i. The length of Hamiltonian Path in a connected graph of n vertices is
(A) n–1 (B) n
(C) n+1 (D) n/2
j. A graph with one vertex and no edges is:
(A) multigraph (B) digraph
(C) isolated graph (D) trivial graph
Answer any FIVE Questions out of EIGHT Questions.
Each question carries 16 marks.
Q.2 a. Shirts numbered consecutively from 1 to 20 are worn by 20 members of a bowling league. When any three of these members are chosen to be a team, the league proposes to use the sum of their shirt numbers as the code number for the team. Show that if any eight of the 20 are selected, then from these eight one may form at least two different teams having the same code number. (8)
b. In a group of athletic teams in a certain institute, 21 are in the basket ball team, 26 in the hockey team, 29 in the foot ball team. If 14 play hockey and basketball, 12 play foot ball and basket ball, 15 play hockey and foot ball, 8 play all the three games.
(i) How many players are there in all?
(ii) How many play only foot ball? (4+4)
Q.3 a. Let A = {a,b,c,d,e} and R={(a,a), (a,b), (b,c), (c,e), (c,d), (d,e)}
Compute (i) R2 and (ii) R? (8)
b. Simplify the Boolean function:
F(w,x,y,z) = ? (0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 14) (8)
Q.4 a. Use Kruskal’s algorithm to find a minimal spanning tree for the following graph. (10)
b. How do you find the second minimum spanning tree of a graph? Find the second minimum spanning tree of the above graph. (6)
Q.5 a. Prove that for every pair of elements x and y in A (using algebraic method).
(i) (x+y)' = x'.y'
(ii) (x.y)' = x'+y' (10)
b. Prove that (p ? q) ? r = p ? (q ? r) (6)
Q.6 a. Find the number of ways in which 5 prizes can be distributed among 5 students such that
(i) Each student may get a prize
(ii) There is no restriction to the number of prizes a student gets. (8)
b. Prove that the relation "congruence modulo m" is an equivalence relation in the set of integers. (8)
Q.7 a. Show that is divisible by 3. (8)
b. Find the state table for the NFA with the state diagram given below. Find the language recognized by it. (8)
Q.8 a. Find the number of ways in which we can put n distinct objects into two identical boxes so that no box remains empty. (8)
b. Let L, be distributive Lattice, for any a,b,c ? L, then show that
a ? b = a ? c and a ? b = a ? c imply b = c (8)
Q.9 a. Which of the following sets are equal?
S1 = {1, 2, 2, 3}, S2 = {x | x2 – 2x + 1 = 0},
S3 = {1, 2, 3}, S4 = {x | x3 – 6x2 + 11x – 6 = 0}, (8)
b. A graph G has 21 Edges, 3 vertices of degree 4 and other vertices
are of degree 3. Find the number of vertices in G. (8)
Attachments:
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.
|
Advertise Here
|