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

Got a question or eager to learn? Discover limitless learning on WhatsApp now - Start Now!

Discrete Mathematics Question Paper

Discrete Mathematics

Course:Bachelor Of Science In Information Technology

Institution: Kca University question papers

Exam Year:2009

UNIVERSITY EXAMINATIONS: 2009/2010
FIRST YEAR EXAMINATION FOR THE DEGREE OF BACHELOR OF
SCIENCE IN INFORMATION TECHNOLOGY
BIT 1206: DISCRETE MATHEMATICS
DATE: DECEMBER 2009 TIME: 2 HOURS
INSTRUCTIONS: Answer question ONE and any other TWO questions
QUESTION ONE (30 MARKS)
a) i. Define a Boolean algebra (2 Marks)
ii. Let S ={1,2,3,4,6,8,12,24}.Define +,x, ’,on S by
x+y=lcm(x,y),x.y=gcd(x,y),x’=
x
24 .For x, y ? S ,lcm and gcd denote,respectively,the least
common multiple and the greatest common divisor. Is S together with these three operations a
Boolean algebra? (5 Marks)
b) Give the recurrence definition of the following sequence
1,3,7,15,31,63,……….. (3 Marks)
c) Solve the recurrence relation 1 2 3 5 8 4 - - - = - + n n n n t t t t for n = 3 subject to the initial
conditions 0 , 1, 2 0 1 2 t = t = t = . (6 Marks)
d) i. In how many ways a committee of 4 can be formed chosen from 10 people.
ii. How many committees of 4 or more can be chosen from 10 people (6 Marks)
2
e) i.Given that R is a relation defined by{(x, y); x divides y} is a partial ordering on the set
A={2,4,5,10,12,20,25}.Construct its Hasse diagram
ii. Is the relation in (i) above a total ordering? Justify your answer
(8 Marks)
QUESTION TWO (20 MARKS)
a) Draw diagrams to represent the complete graphs K2 and K6 and the complete bipartite graphs K2,5
and K4,4. (6 Marks)
b) Explain briefly how special types of graphs are used in LAN and interconnection networks for
parallel computations giving in each case example of such graph (6 Marks)
c) Show that in a simple graph, the sum of the vertex degrees is twice the number of edges.
(4 Marks)
d) Deduce that, in a simple graph, the number of vertices with odd degree is even. (4 Marks)
QUESTION THREE (20 MARKS)
a) Define the following terms as used in graph theory
(i) Adjacency matrix
(ii) Directed path
(iii) Subgraph
(iv) Strongly connected graph
(v) Circuit (5 Marks)
b) i) Draw a directed graph with the adjacency matrix
? ? ? ?
?
?
? ? ? ?
?
?
=
0 1 1 0
1 0 0 1
1 0 1 0
0 1 0 1
A
With vertices ordering of 1 2 3 4 v ,v ,v ,v (2 Marks)
ii) Find the indegree and outdegree of each vertex in the graph in (i) above (4 Marks)
iii) How many paths of length 4 are there from 1 3 v to v in the graph in b (i) above. (5 Marks)
iv) Obtain the path matrix (P) of the graph in b (i) above. Is the graph strongly connected?
(5 Marks)
3
QUESTION FOUR (20 MARKS)
a) Construct a truth table for the Boolean function f (x, y, z) = xy + yz (5 Marks)
b) Let S be the universal set and let S = ? (S) ,the power set of S .If we define the following
operations
X + Y = X ? Y , X.Y = X ?Y , X = X C on S. Show that (S,?,?,F,S , ) is a Boolean algebra
(5 Marks)
c) Show that C(2n,2) = 2C(n,2) + n2 (5 Marks)
d) show that n
n
k k
n
2
0
= ?
??
?
? ??
? S=
(5 Marks)
QUESTION FIVE (20 MARKS)
a) Solve the recurrence relation 1 2 3 3 3 - - - = - + n n n n a a a a for n = 3 subject to the initial
Conditions 2 , 1, 1 0 1 2 a = a = a = . (6 Marks)
b) Given that A={2,7,14,28,56,84}.A relation R on A is defined as {(x, y)? R; x divides y}
(i) Construct Hasse diagram for R (4 Marks)
(ii) find the maximal and minimal elements (2 Marks)
(iii) is there greatest and least elements? (2 Marks)
(iv) find all upper bounds and lower bounds of {14,28} (2 Marks)
(v) Find least upper bounds and greatest lower bound of{14,28} (2 Marks)
(vi) Is the poset a lattice? Give reason for your answer (2 Marks)

Discrete Mathematics Question Paper

More Question Papers

Popular Exams