KEMBAR78
Graph Algorithms & NP Problems Tutorial | PDF
Scribd
Upload
59 views1 page

Graph Algorithms & NP Problems Tutorial

This document outlines the topics and questions covered in a tutorial sheet for the Design and Analysis of Algorithms course. The tutorial sheet covers graph algorithms and complexity classes like P, NP, NP-hard, and NP-complete problems. It contains 3 sections with multiple choice and multi-part problems worth varying marks testing knowledge of key graph algorithms and their complexity.

Uploaded by

megha.garg1
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
59 views1 page

Graph Algorithms & NP Problems Tutorial

This document outlines the topics and questions covered in a tutorial sheet for the Design and Analysis of Algorithms course. The tutorial sheet covers graph algorithms and complexity classes like P, NP, NP-hard, and NP-complete problems. It contains 3 sections with multiple choice and multi-part problems worth varying marks testing knowledge of key graph algorithms and their complexity.

Uploaded by

megha.garg1
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 1

B.Tech.

(Computer Science and Engineering)


Semester-V
Subject: Design and Analysis of Algorithms
Subject code BCO023A
Marks: 64

CO5: Knowledge of Graphs and their algorithms.

UNIT #5 Tutorial sheet 2


Sec-A (5x2=10marks)

1. [CO5]-Is P=NP? [2 marks]


2. [CO5]- What is a decision problem. [2 marks]
3. [CO5]- Differentiate between P and NP Problems. [2 marks]
4. [CO5]- Explain the difference between NP-hard and NP-Complete Proble [2 marks]
5. [CO5]- How to check a problem is NP. [2 marks]

Sec-B
/* Note: Each question may have one or two parts */ (3x7=21 marks)

6. [CO5]-State and Prove Cook’s Theorem [7 marks]

7. [CO5]-Prove that CNF-Satisfiablity is NP-Complete. [7 marks]

8. [CO5]-. Prove that set-partition problem is NP-Complete [7 marks]

Sec-C
/* Note: Each question may have one, two, or three parts */ [3*11=33 marks]

9. [CO5] Is 3-CNF SAT problem reducible to SAT problem.Provide example [11 marks]

10. [CO5] - Prove that travelling salesman problem is NPComplete. [11 marks]

11. [CO5]- What is Vertex Cover Decision Problem.Prove that it is NP Complete. [11 marks]

You might also like