Scribd
Upload
53 views2 pages

DAA - Theory Assignment 2

This document contains 15 multiple choice questions from the "Design and Analysis of Algorithms" course at Sinhgad Institute of Technology related to complexity theory. The questions cover topics like best/average/worst case analysis of algorithms, P/NP/NP-hard/NP-complete problems, 3-SAT problem, vertex cover problem, deterministic and non-deterministic algorithms, big-O notation, and the differences between NP-complete and NP-hard problems. The purpose of the document is to assess students' understanding of foundational algorithm analysis concepts and complexity classes.

Uploaded by

djalok190109
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
53 views2 pages

DAA - Theory Assignment 2

This document contains 15 multiple choice questions from the "Design and Analysis of Algorithms" course at Sinhgad Institute of Technology related to complexity theory. The questions cover topics like best/average/worst case analysis of algorithms, P/NP/NP-hard/NP-complete problems, 3-SAT problem, vertex cover problem, deterministic and non-deterministic algorithms, big-O notation, and the differences between NP-complete and NP-hard problems. The purpose of the document is to assess students' understanding of foundational algorithm analysis concepts and complexity classes.

Uploaded by

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

Sinhgad Technical Education Society’s

SINHGAD INSTITUTE OF TECHNOLOGY, LONAVALA


(Affiliated to Savitribai Phule Pune University and Approved by AICTE, New Delhi)
Accredited by NAAC with Grade “A”
Department of Computer Engineering

Design and Analysis of Algorithms

UNIT - II: Analysis of Algorithms and Complexity Theory

Theory Questions

Sr. No. Questions Marks


1. What is Best, Average and Worst case Analysis of Algorithms? Analyse the 8
following algorithm Best, Average and Worst case.

void sort (int a. int n) {


int i, j;
for (i = 0; i < n; i++) {
j = i-1;
key = a[i];
while (j >=0 && a[j] > key)
{
a[j+1] = a[j];
j = j-1;
}
a[j+1] = key;
}
}
2. Explain P, NP, NP-Hard and NP-Complete problems with examples. 7
3. Explain 3-SAT problem using an example. Why is SAT so important in 7
theoretical computer science?
4. What is NP-complete class problem? How would you prove vertex cover 8
problem is NP-complete class problem?
5. What is Best, Average and Worst case Analysis of Algorithms? Analyse the 7
following algorithm Best, Average and Worst case

int Linear-search(int a, int n, int item) {


int i;
for (i = 0; i < n; i++) {
if (a[i] = = item) {
return a[i]
}
}
return – 1
}
6. State vertex cover problem and prove that vertex cover problem is NP 8
Complete.
7. What are deterministic and non-deterministic algorithms? Explain with 8
example.
8. Write short note on : 8
i. P class and NP class
ii. Big ‘oh’ and theta

Dept Tel. : +91 2114-673490, 491 Office : 02114-673355, 356 Email : [email protected] Website : sit.sinhgad.edu
Sinhgad Technical Education Society’s
SINHGAD INSTITUTE OF TECHNOLOGY, LONAVALA
(Affiliated to Savitribai Phule Pune University and Approved by AICTE, New Delhi)
Accredited by NAAC with Grade “A”
Department of Computer Engineering

9. Explain NP-hard Hamilton cycle problem. 8

10. Define the terms: best case, worst case, and average case time complexity. 5
Provide examples for each.
11. What is Big O notation? How is it used to provide an upper bound on an 6
algorithm's time complexity?
12. Differentiate between Ω (Omega) and Θ (Theta) notations. How do they 6
provide lower and tight bounds on time complexity, respectively?
13. Define o (little-o) and ω (little-omega) notations. How do they express upper 5
and lower bounds that are not asymptotically tight?
14. Compare and contrast polynomial and non-polynomial time complexity. 5
Provide examples of algorithms in each category.
15. Explain the difference between NP-complete and NP-hard problems. Can an 5
NP-hard problem be easier than an NP-complete problem?

Course In charge:
Ms. Rupali S. Shishupal

Dept Tel. : +91 2114-673490, 491 Office : 02114-673355, 356 Email : [email protected] Website : sit.sinhgad.edu

You might also like