Computer Engineering (Semester 3)
Total marks: 80
Total time: 3 Hours
INSTRUCTIONS
(1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Draw neat diagrams wherever necessary.
1.a. ) By using mathematical induction show that :
1 + 2 + 3 + ........ + n = n(n + 1)/2 for all natural number
values of n.
(4 marks)
00
1.b. Use :
p : I will study discrete structure
q : I will go to a movie
r : I am in a good mood.
Write the English sentence that corresponds to each of the
following :
(i) ~ r $\rightarrow$ q
(ii) ~ q $\wedge$ p
(iii) q $\rightarrow$ ? ~ p
(iv) ~ p $\rightarrow$ ~ r.
(2 marks)
00
1.c. Let R = {(1, 4), (2, 1), (2, 5), (2, 4), (4, 3), (5, 3), (3, 2)}
on the set A = {1, 2, 3, 4, 5}. Use Warshall’s algorithm to
find transitive closure of R.
(6 marks)
00
Or
2.a. 100 sportsmen were asked whether they play cricket, football
or hockey. Out of these 45 play cricket, 21 play football, 38
play hockey, 18 play cricket and hockey, 9 play cricket and
football, 4 play football and hockey and 23 play none of these.
Find the number of sportsmen who play :
(i) exactly one of the games
(ii) exactly two of the games.
(6 marks)
00
2.b. A = {1, 2, 3, 4}, B = {1, 4, 6, 8, 9}; aRb iff b = $a^{2}$. Find
the domain, range of R. Also find its relation matrix and draw
its diagraph.
(6 marks)
00
3.a. From a group of 7 men and 6 women, five persons are to
be selected to form a committee so that at least 3 men are
are there on the committee. In how may ways can it be
done?
(3 marks)
00
3.b. How many 4-letter words with or without meaning, can be
formed out of the letters of the word ‘LOGARITHMS’, if repetition
of letters is not allowed ?
(3 marks)
00
3.c. Determine whether the two graphs are isomorphic or not.
Explain.
(6 marks)
00
Or
4.a. Use Dijkstra’s algorithm to find the shortest path between
A and Z in figure :
(6 marks)
00
4.b. If a committee has eight members :
(i) How many ways can the committee members be seated
in a row ?
(ii) How many ways can the committee select a president,
vice-president and secretary ?
(6 marks)
00
5.a. Find maximum flow in the transport network using labeling
procedure. Determine the corresponding min cut :
(7 marks)
00
5.b. Define the following terms :
(i) Level and height of a tree
(ii) Cut points
(iii) Eccentricity of a vertex.
(6 marks)
00
Or
6.a. Find minimum spanning tree for the graph shown below using
Kruskal’s algorithm.
(7 marks)
00
6.b. Suppose data items A, B, C, D, E, F, G occur in the following
frequencies respectively 10, 30, 5, 15, 20, 15, 5. Construct a
Huffman code for the data. What is the minimum weighted
path length ?
(6 marks)
00
7.a. Let Zn
= {0, 1, 2, ..........., n – 1}. In Z12 what is the order
of 3, 6 and 8.
(3 marks)
00
7.b. Let (Q, *) is an Algebraic system. * is a binary operation
defined as $a^{*}+b_{0}=a+b-a b \quad \forall a, b \in$ Q. Determine
whether (Q, *) is a group.
(4 marks)
00
7.c. Define :
(i) Rings
(ii) Integral domain
(iii) Field.
(6 marks)
00
Or
8.a. Let Zn
= {0, 1, 2, ........., n – 1}. Let * be a binary operation
such that a * b = remainder of (a + b) divided by n.
Construct a table for n = 4. Is (Z4, *) a monoid, semigroup,
group and abelian group
(7 marks)
00
8.b. Define :
(i) Group code
(ii) Galois theory
(iii) Cyclic group.
(6 marks)
00