No. of Pages:2

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
FIRST SEMESTER M.IECH DEGREE EXAMINATION, DECEMBER 2018

Branch : Computer Science & Engineering

Stream(s):

|. Computer Science & Engineering

2. Information Security

Course Code & Name: 0106101 Mathematical Foundations of Computing Systems

Answer any twofull questions from each pan Limit
answers to the required points.

Max. Marks: 60 Duration: 3 hours

PART A

1. a. Discuss Branching Time Logic. (3)

b. Show by Direct Proof that "If mand ೧ are both perfect squares then product of (3) m
and nis also a perfect square.

c. Solve the recurrence relation ar - 7 ar.l+ 10 ar.2 0 for 2 2; Given ao = 0; al (3) = 41
using Generating Functions .

2. a. By Mathematical Induction, prove that for every positive integer 'n', the (3) numberAn=$+2.
+1 15 a multiple of 8.
b. Prove by contraposition that " If '೧' 15 an integer and 3n+2 is odd, then en' is (3) odd“.

c. Which are the adequate set of connectives? Discuss with an example. (3) 3. 2. What
is Linear -Time Temporal Logic? (3)

b. Show that '12 is irrational by giving a proof by contradiction .(3)

c. Solve the recurrence relation ar- 4 at-I = 2 using characteristic root method . (3)
PART 5
4. a. In a factory there are two machines, manufacturing bolts. The first machine (3)

manufactures 70% of the bolts and the second machine manufactures the remaining 30%.
From the first machine of the bolts are defective and from the second machine 5% of the bolts
are defective. A bolt is selected at random, what is the probability the bolt came from the first
machine, given that it is defective.

b. Among 18 students in a room, 7 study mathematics, 10 study science, and 10 (3) study
computer programming. Also, 3 study mathematics and science, 4 study mathematics and
computer programming, and 5 study science and computer programming. We know that
| student studies all three subjects. How many of these students study none of the three
subjects?