02/07/2020 Design and analysis of algorithms - - Unit 26 - Week 8 Quiz
(https://swayam.gov.in) (https://swayam.gov.in/nc_details/NPTEL)
reviewer4@nptel.iitm.ac.in
NPTEL (https://swayam.gov.in/explorer?ncCode=NPTEL) » Design and analysis of algorithms (course)
Announcements (announcements) About the Course (https://swayam.gov.in/nd1_noc20_cs27/preview)
Ask a Question (forum) Progress (student/home) Mentor (student/mentor)
Unit 26 - Week 8 Quiz
Course
outline Week 8 Quiz
How does an The due date for submitting this assignment has passed. Due on 2020-03-25, 23:59 IST.
NPTEL online As per our records you have not submitted this assignment.
course work?
All questions carry equal weightage. You may submit as many times as you like within the deadline.
Week 1 : Your final submission will be graded.
Introduction
1) When we model a graph problem using LP, mapping each path to a variable is not a good 2 points
strategy because:
Week 1 : Analysis
of algorithms We have to be careful to avoid cycles.
A graph has exponentially many paths.
Week 1 Quiz
Edges may be directed.
Week 2 : Paths can be hard to compute.
Searching and No, the answer is incorrect.
sorting Score: 0
Feedback:
Week 2 Quiz Graphs have exponentially many paths, so the LP model will have exponentially many variables.
Accepted Answers:
Week 2 A graph has exponentially many paths.
Programming
2) Which of the following is a linear constraint? 2 points
Assignment
17x + 3xz ≤ 4
Week 3 : Graphs
3x ≥ 14y + 2z + 13
7x ≤ 3xy + 14z - 12
Week 3 Quiz
5y + 3x2 ≥ 33
Week 3 No, the answer is incorrect.
Programming Score: 0
Assignment Feedback:
In a non-linear constraint, we have two or more variables (same or different) multiplied together.
Accepted Answers:
https://onlinecourses.nptel.ac.in/noc20_cs27/unit?unit=125&assessment=126 1/3
02/07/2020 Design and analysis of algorithms - - Unit 26 - Week 8 Quiz
3x ≥ 14y + 2z + 13
Week 4 :
Weighted graphs 3) Suppose we compute the maximum s-t flow F in a network. Then, which of the following is 2 points
true of s-t cuts?
Week 4 Quiz
F gives a lower bound for the capacity of the minimum s-t cut but not the exact capacity.
Week 4 From F, we can identify all minimum s-t cuts in polynomial time.
Programming From F, we can identify a minimum s-t cut in polynomial time.
Assignment
From F, we know the capacity of the minimum s-t cut, but identifying such a cut can take
exponential time.
Week 5: Data
Structures: No, the answer is incorrect.
Union-Find and Score: 0
Heaps Feedback:
From F, use BFS to identify saturated edges that form a min-cut. There may be other min-cuts.
Week 5 : Divide Accepted Answers:
From F, we can identify a minimum s-t cut in polynomial time.
and Conqure
4) We wish to show that problem B is NP-complete. Which of the following facts is sufficient to 2 points
Week 5 Quiz establish this.
Week 6: Data There is a polynomial time reduction from B to SAT.
Structures: There is a polynomial time reduction from SAT to B
Search Trees
There is a polynomial time reduction from B to SAT, and B has a checking algorithm.
There is a polynomial time reduction from SAT to B, and B has a checking algorithm.
Week 6: Greedy
Algorithms No, the answer is incorrect.
Score: 0
Week 6 Quiz Feedback:
We need a reduction from an NP-complete problem to B and evidence that B belongs to NP.
Accepted Answers:
Week 6
There is a polynomial time reduction from SAT to B, and B has a checking algorithm.
Programming
Assignment 5) We have constructed a polynomial time reduction from problem A to problem B. Which of the 2 points
following is a valid inference?
Week 7: Dynamic
Programming If the best algorithm for A takes exponential time, there is no polynomial time algorithm for B.
If we have a polynomial time algorithm for A, we must also have a polynomial time algorithm for B.
Week 7 Quiz If we don’t know whether there is a polynomial time algorithm for B, there cannot be a polynomial
time algorithm for A.
Week 7
If the best algorithm for B takes exponential time, there is no polynomial time algorithm for A.
Programming
Assignment No, the answer is incorrect.
Score: 0
Week 8: Linear Feedback:
If we have a polynomial time solution for B, the reduction gives us a polynomial time solution for A.
Programming
and Network Accepted Answers:
Flows If the best algorithm for A takes exponential time, there is no polynomial time algorithm for B.
Week 8:
Intractability
Week 8 Quiz
Quiz : Week 8
Quiz
(assessment?
name=126)
https://onlinecourses.nptel.ac.in/noc20_cs27/unit?unit=125&assessment=126 2/3
02/07/2020 Design and analysis of algorithms - - Unit 26 - Week 8 Quiz
Text Transcripts
Books
Download Videos
https://onlinecourses.nptel.ac.in/noc20_cs27/unit?unit=125&assessment=126 3/3
