No. of Pages: 3

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
FIRST SEMESTER M.TECH DEGREE EXAMINATION. DECEMBER 201 7
Branches: Computer Science & Engineering & Information Technology

Streams *

| . Computer Science & Engineering
2. Information Security
3. Network Engineering

01 CS 6101: Mathematical Foundations ofComputing Systems

Answer any twofull questions from each part

Limit answers to the required points.

Max. Marks: 60 |)uration: 3 hours
PART A

.a. For a © 2, if a2 -2a +7 is even, then a 15 odd. Prove the statement by (5) contradiction and
contrapositive proof techniques.

0. சோத complete induction show that if nis an integer greater than 1, thenncan (4) be
written as the product of primes.
2. a. Prove that Q3 is irrational. (5)
0. Using mathematical induction prove that 1-3+23+. . +111 =(1+2+.n)2 forn€ Ze (4)
3. a. Write short notes on linear time temporal logic. (4)
Using generating function, solve the recurrence relation an-7an_|.10 an-2=0, (5) with
initial conditionao=a1=3
PART B

4. a. Every sequence of (n2+1) distinct real numbers contain a subsequence of length (n+l) that
is either strictly increasing or strictly decreasing. Prove using (5) pigeon hole principle.

b. From a box of 3 black and 4 white marbles,

(i) If two marbles are drawn successively, find the probability that both are black if
the first marble is not replaced before the second drawing.

(ii) If two marbles are drawn successively, find the probability that both are black if
the first marble is replaced before the second drawing.

(iii) If four marbles are drawn at random, find the probability that there are equal
number of marbles of both colors.

(iv) 1 three marbles are drawn successively without replacement, find the (4)