Are you Searching Kannur University Question papers? Here you can get COMPUTATIONAL COMPLEXITY Question paper.
VII Semester B.Tech. (Reg./Sup./Imp. - Including Part Time) Degree
Examination, November 2011
(2007 Admn.)
2K6CS 705 (F) : COMPUTATIONAL COMPLEXITY
Time:3 Hours Max. Marks: 100
Instruction : Answer all questions.
I. a) Write notes on Karp-completeness based on Karp theorem. [Marks 5]
h) Write notes on space complexity. [Marks 5]
c) Write notes on randomized reduction. [Marks 5]
d) Write notes on Valiants theorem. [Marks 5]
e) Write notes on interactive proofs with suitable examples. [Marks 5]
f) Explain multi-party communication complexity. [Marks 5]
g) Write notes on quantum computation with suitable examples. [Marks 5]
h) Write notes on random walks. [Marks 5]
II. a) Explain the NP problems and show that travelling salesman problem is an NP
complete problem. [Marks 15]
OR
b) Explain in detail the NP complete problems. Prove that the satisfiability problems are NP complete. [Marks 15]
III. a) Explain about major aspects of the failure probability of randomized algorithms. [Marks 8]
b) Explain in detail the concept of counting complexity. [Marks 7]
OB
c) Explain PTMs in detail with suitable examples. [Marks 15]
IV. a) Explain in detail the randomized decision trees with suitable examples. Write
notes on randomized algorithms. [Marks 15]
OR
b) Write notes on differences between interactive proofs and mathematical proofs
by giving suitable examples. [Marks 15]
V. a) Explain polynomial time sampling with example. [Marks 10]
b) Write notes on derandomization. [Marks 5]
OR
c) Explain in detail the PCP and the hardness of approximation with the help of
suitable examples. [Marks 15]
VII Semester B.Tech. (Reg./Sup./Imp. - Including Part Time) Degree
Examination, November 2011
(2007 Admn.)
2K6CS 705 (F) : COMPUTATIONAL COMPLEXITY
Time:3 Hours Max. Marks: 100
Instruction : Answer all questions.
I. a) Write notes on Karp-completeness based on Karp theorem. [Marks 5]
h) Write notes on space complexity. [Marks 5]
c) Write notes on randomized reduction. [Marks 5]
d) Write notes on Valiants theorem. [Marks 5]
e) Write notes on interactive proofs with suitable examples. [Marks 5]
f) Explain multi-party communication complexity. [Marks 5]
g) Write notes on quantum computation with suitable examples. [Marks 5]
h) Write notes on random walks. [Marks 5]
II. a) Explain the NP problems and show that travelling salesman problem is an NP
complete problem. [Marks 15]
OR
b) Explain in detail the NP complete problems. Prove that the satisfiability problems are NP complete. [Marks 15]
III. a) Explain about major aspects of the failure probability of randomized algorithms. [Marks 8]
b) Explain in detail the concept of counting complexity. [Marks 7]
OB
c) Explain PTMs in detail with suitable examples. [Marks 15]
IV. a) Explain in detail the randomized decision trees with suitable examples. Write
notes on randomized algorithms. [Marks 15]
OR
b) Write notes on differences between interactive proofs and mathematical proofs
by giving suitable examples. [Marks 15]
V. a) Explain polynomial time sampling with example. [Marks 10]
b) Write notes on derandomization. [Marks 5]
OR
c) Explain in detail the PCP and the hardness of approximation with the help of
suitable examples. [Marks 15]
0 comments:
Pen down your valuable important comments below