Sardar Patel University 2008 B.E Computer Science CP201-Introduction to Theoretical (Internal Test) - Question Paper

[2].
3) Define ‘hasse diagram’ and ‘lattice’ with example. [1]

**********
******Best of Luck******
***********

Solution

ADIT/BVM/GCET
A.Y. 2007-08, Semester II
INTERNAL exam
CP201-Introduction to Theoretical Computer Science

Date: 11/03/2008 Time: 12:00 P.M to 1:00 P.M Max Marks: 20

Note: Write ans to the ques. point to point.
Q.1 Attempt following:
[A] 1) Show that
12 + 32 +52 + …+(2n-1)2 = n (2n-1) (2n+1) / three
[2]
Ans. Basic of the induction:
For n=1
L.H.S = one
R.H.S = 3/3 = 1
Induction hypothesis:

presume that for n= k it is true,
12 + 32 +52 + …+(2k-1)2 = k (2k-1) (2k+1) / 3

Now n = k +1

L.H.S = 12 + 32 +52 + …+(2k-1)2 + ( 2k + 1)2
= k (2k-1) (2k+1) / three + ( 2k + 1)2
= (2k + 1) [ 2k2 + 2k + 3k + three ]/3
= (2k + 1) ( k +1 ) ( 2k + 3) /3

Marking Strategy:
1. If above steps are shown correctly then two marks.

2) Among 100 students, 32 study mathematics, 20 study physics, 45 study biology, 15 study mathematics and biology, seven study mathematics and physics, 10 study physics and biology, and 30 do not study any of the 3 subjects.
(c) Find the number of students studying all 3 subjects.
(d) Find the number of students studying exactly 1 of the 3 subjects. [2]
Ans. We are provided subsequent data:
| M | = 32, | P | = 20, | B | = 45
| M ? B | = 15, | M ? P | = 7, | P ? B | = 10
~|M U P U B | = 30

a) Number of students are studying all the 3 subjects:
|M U P U B | = one - ~|M U P U B | = 100 – 30 = 70

|M U P U B | = | M | + | P | + | B | - | M ? B | - |M ? P | -| P ? B | + | M ? P ? B |
70 = 32 + 20 + 45 – 15 – seven – 10 + | M ? P ? B |
| M ? P ? B | = five students are studying all the 3 subjects

b) Number of students who studying exactly 1 of 3 subjects:

= | M | + | P | + | B |
= 25 + 15 + 8
= 48
Marking Strategy:
1. For every of the accurate ans one mark.

3) Construct the truth table for the subsequent statements:
(c) (a ? a) ? (a ? a)
(d) a ?? (e V a) [1]
Ans.
a a a ? a a ? a (a ? a) ? (a ? a)
T F T F F
F T T T T


a e a e e V a a ?? (e V a)
T T F F F F
T F F T T T
F T T F T F

Earning:   Approval pending.