Get premium membership and access revision papers, questions with answers as well as video lessons.

Discrete Mathematics Question Paper

Discrete Mathematics

Course:Bachelor Of Science In Information Technology

Institution: Kca University question papers

Exam Year:2010

UNIVERSITY EXAMINATIONS: 2009/2010
FIRST YEAR EXAMINATION FOR THE DEGREE OF BACHELOR OF
SCIENCE IN INFORMATION TECHNOLOGY
BIT 1206: DISCRETE MATHEMATICS
DATE: APRIL 2010 TIME: 2 HOURS
INSTRUCTIONS: Answer question ONE and any other TWO questions
QUESTION ONE
a) Define the following terms
i. partial ordering
ii. A graph
iii. Boolean algebra
iv. Permutation
v. Combination
(5 Marks)
b) Let B = {1,2,3,5,6,10,15,30}.Define +,×, , on B by
x + y = lcm(x, y) , x + y = gcd(x, y) ,
x
x = 30 .For x, y? B,lcm and gcd denote,respectively,the
least common multiple and the greatest common divisor. is (B,+,×, ,1,30) a Boolean algebra?
(6 Marks)
c) Solve the recurrence relation 5 3 3 1 2 3 = - + - = - - - a a a a for n n n n n subject to the
Initial Conditions 0, 1, 2 0 1 2 a = a = a = . (7 Marks)
d) Use Boolean laws to show that if x + y = 1 and xy = 0 then y = x (5 Marks)
2
e) Draw a Hasse diagram of the partial order R on A = {1,2,4,8,16,32,64} given by
R = {(a,b): a / b} (7 Marks)
QUESTION TWO (20 MARKS)
a) Define the following terms as used in graph theory
i. Sub graph
ii. Simple path
iii.Cycle
iv. Reachability
v. Strongly connected
(5 Marks)
b) Show that the maximum number of edges in a graph with n -vertices is 2 nC (4 Marks)
c) i. Draw a directed graph with the adjacency matrix
With vertices ordering of 1 2 3 4 v ,v ,v ,v . (2 Marks)
ii. How many paths of length 3 are there from 2 v to 4 v in the graph in c (i) a above. (4 Marks)
iii. Obtain the path matrix (P) of the graph in c (i) above (4 Marks)
iv. Is G strongly connected? Justify your answer (1 Mark)
QUESTION THREE (20 MARKS)
a) Use the binomial theorem to prove that ( 1) ( , ) 0
0
= - S=
n
k
k C n k (4 Marks)
b) Construct the truth table for the following Boolean expression
f (x, y, z) = (x + y)(x + z) (5 Marks)
c) Let S be the universal set and let G = ? (S) ,the power set of S .Define the following
operations
3
X + Y = X ?Y , XY = X nY , X = X C on G.Show that (G,?,n, ,F,S) is a Boolean
algebra (5Marks)
d) Solve the following recurrence relation 6 9 4 1 2 + + = n n- n- a a a given that
0 , 1 0 1 a = a = (6 Marks)
QUESTION FOUR (20 MARKS)
a) Define a lattice as used in posets (2 Marks)
b) Draw a Hasse diagram for the following set under the divisibility relation
{2,4,6,9,12,18,27,36,48,60,72} (8 Marks)
i. Find the maximal and minimal elements (2 Marks)
ii. Find the greatest and least elements, if they exist (2 Marks)
iii. Find the all upper bound and all lower bound of the set B = {2.9} (2 Marks)
iv. Find the least upper bound and greatest lower bound of B = {2,9}, if they exist
(2Marks)
v. Is this poset a lattice? Give reason for your answer (2 Marks)
QUESTION FIVE (20 MARKS)
a) State and define the components of a recursively defined set (3 Marks)
b) i). Draw graphs to represent the complete graphs 4 K and 6 K and the complete
Bipartite graph 3,5 K and 5,5 K (4 Marks)
ii). Briefly explain how special type of graphs are used in data communication and
Parallel processing in computer science. (4 Marks)
b) How many ways can three integers be selected from the integers 1, 2, 3, 4, 5, 6…, 30
So that their sum is even. (4 Marks)
c) i. State the Binomial theorem (2 Marks)
ii. Use Binomial theorem to find the coefficient of x12 y13 in the expansion of (6x - 8y)25
(3 Marks)

Discrete Mathematics Question Paper

More Question Papers

Popular Exams