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.
Advertisements
|
Download Model question papers & previous years question papers
|
Posted By: S.Yamininagarajan Member Level: Diamond Posted Date: 01 Jun 2008
|
2005 Indira Gandhi National Open University (IGNOU) Discrete Mathematics Question paper
|
|
|
Test Papers / Previous Question Papers of IGNOU CS07 Discrete Mathematics December 2005
ADCA / MCA (II Yr)
Term-End Examination
December, 2005
CS07 (S): Discrete Mathematics
Time: 3 hours
Maximum Marks: 75
Note : Question No. 1 is compulsory. Answer any three questions from the rest.
1. (a) Write the following formula in principal conjunctive normal form (Q => ?P) ^ (P v R). (4)
(b) Consider the following graph :
-----DIAGRAM-----
(i) ldentify a cut vertex in the graph. lf you remove the vertex, how many connected components will be there in the resulting graph ? (2)
(ii) Why is the graph non-Eulerian ? How can you make this graph Eulerian by removing an edge and adding a new edge ? (2)
(c) Define a relation R on the set of natural numbers as follows:
aRb if l a-b l < 3.
(i) Is R reflexive ?
(ii) ls R symmetric ?
(iii) ls R transitive ?
Give reasons for your answers. (3)
(d) Draw the Hasse diagram of the poset ({{1 , 2 , 3 , 4}, {1 , 2}, {1,3}, {1 , 2 , 3}, {1}}, €)
Check whether the poset is a lattice or not. (4)
(e) Let P : The electricity meter is faulty.
Q : The electricity charges are high
R : The consumers will complain about the bills.
Write the following staiements using logical symbols
(i) If the electricity meter is faulty and the electricity charges are high, the consumers will complain about the bills.
(ii) lf the consumer do not complain about the bills, either the electricity meters are not faulty or the electricity charges are not high. (4)
(f) Consider the following complete weighted graph :
-----DIAGRAM-----
Starting from the cycle v1 v2 v3 v4 v5 v1 apply the two-optimal algorithm to get a Hamiltonian cycle of weight less than 10. (4)
(g) Consider the binary operation * defined on the set of integers by a * b = a + b - ab. Check whether
(i) * is commutative
(ii) * is associative
(iii) * has an identity element (4)
(h) State the two distributive laws for lattices. Verify the laws for the elemenls 3,5 and 9 of the lattice (D(45), g.c.d, l.c.m) (3)
2. (a) Check, using truth tables, whether the following statemens are consistent:
"If the dog bark at Ram, Ram is a stranger."
"lf the dog doesn't bark at strangers, the dog does not bark at Ram."
"lf Ram is not a stranger, the dog barks at Ram." (7)
(b) Find a Minimum Spanning Tree graph using Kruskal's algorithm. (5)
-----DIAGRAM-----
(c) Let A = {1, 2, 3, 4}, B = {3, 4, 5, 6, 8}, C = {6, 8, 10. 12, 16, 18}. Let f : A -> B be defined by f(x) = x + 2, and g : B -> C be defined by g(x) = 2x. Find gof. Check whether gof is injective and surjective. (3)
3. (a) Construct a finite state machine that takes as input '0' and '1', and gives '1' as output if and only if it gets two '1's followed by a '0' as input. (7)
(b) Fill in the missing terms in the following table : (4)
P Q P ^ Q P => Q
1 1
0 1
0 1
1 0
(c) Let U = {a, b, c, d, e, f}, A = {a, b, c, d, e}, B = {a, d, e}.
(i) State the DeMorgan's laws and check them for A and B.
(ii) If C = {x l x is a letter in the word 'red'}, is B = C ? Give reasons for your answer. (4)
4. (a) check that B = {1, 2, 3}, {1, 2}, {3} , Ø } is a Boolean subalgebra of (P({1,2,3}), n, U. What are the atoms and anti-atoms in B ? (4)
(b) 300 computer users were asked if they have upgraded their computer after they bought them. 120 people said they have increased the RAM, 80 people said they have added a CD-writer, 60 people said they have added another hard disk, 20 people said they have increased the RAM and added a CD-writer, 15 said they have added RAM and an additional hard disk, 10 said they have added a CD-writer and added an additional hard disk, 5 have carried out all the three upgradations.
(i) How many people increased the RAM alone ?
(ii) How many people haven't upgraded anything ?
(iii) How many have added a hard disk, but not a CDwriter ? (7)
(c) Use the breadth first search algorithm to find the length of the shortest path from v1 to each of the other vertices in the following graph. Also, find the length of the shortest path from v1 to v8. (4)
-----DIAGRAM-----
5. (a) Let C(x, y) mean that student x has registered for the course y, where the universe of discourse for x is the set of all MCA students of IGNOU and the universe of discourse for y is the set of all courses offered in the MCA programme. Rewrite each of the following statements in words :
(i) (C(Fahim, CS-07) ? ?C(Fahim, CS-60))
(ii) ?x (C(x, CS-60) ? C(x, CS-07))
(iii) ?y C(Shalini, y)
(iv) ?x (C(x, CS-60) v C(x, CS-07)) (4)
(b) Find the binary tree representation of (x + 6y).xy. (4)
(c) Use the Karnaugh map to simplify the following expression:
x1xbar2x3xbar4 + x1xbar2xbar3xbar4 + x1x2xbar3x4 + x1x2x3xbar4 (7)
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.
|
|