Reg No.:

Max. Marks: 100

G1164 Pages: 2

Name:

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
SEVENTH SEMESTER B.TECH DEGREE EXAMINATION(S), MAY 2019

Course Code: CS469
Course Name: COMPUTATIONAL COMPLEXITY

Duration: 3 Hours

PARTA
Answer all questions, each carries 4 marks. Marks

1 Give the formal definition of Turing machine (4)
2 List out any three asymptotic notations. (4)
9 Define Universal Turing Machine. (4)
4 Define the classes NTIME[t] and NP. (4)
5 State and prove Cook-Levin Theorem. (4)
6 Define the classes DSPACE and PSPACE. (4)
7 Define the complexity class BPP with example. (4)
8 Define probabilistic Turing machine (4)
9 Define the TRAVELLING SALES MAN Problem. (4)
10 Let P be an optimization problem. Then define P using maximization and (4)

minimization problems.

PART ‏تا‎
‎Answer any two full questions, each carries 9 marks.

11 a) Prove that for every multi tape Turing Machine there exist an equivalent single (6)

tape Turing Machine.

(b) Let M be multi Tape Turing machine with O(n) computing steps and there exist (3)

an equivalent single tape Turing Machine D. Then calculate the maximum

number of computing steps for D on an input x with length n such that

M(x)=D(x).
12 (a) State Rice’s Theorem for computing models. (4)

(b) Whether there exists a Turing Machine M that can decide the property “Accept 6)

a binary string with exactly five bits” on another Turing Machine N. Justify

your answer.
13 8) Differentiate the features of decision problem with optimization problems. (4)
b) Design an algorithm to solve the 2-colourability problem in polynomial time. (5)

Page lof 2