Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Tests  >  Test: Dynamic Programming, P & NP Concepts- 2 - Computer Science Engineering (CSE) MCQ

Test: Dynamic Programming, P & NP Concepts- 2 - Computer Science Engineering (CSE) MCQ


Test Description

5 Questions MCQ Test - Test: Dynamic Programming, P & NP Concepts- 2

Test: Dynamic Programming, P & NP Concepts- 2 for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Test: Dynamic Programming, P & NP Concepts- 2 questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Dynamic Programming, P & NP Concepts- 2 MCQs are made for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Dynamic Programming, P & NP Concepts- 2 below.
Solutions of Test: Dynamic Programming, P & NP Concepts- 2 questions in English are available as part of our course for Computer Science Engineering (CSE) & Test: Dynamic Programming, P & NP Concepts- 2 solutions in Hindi for Computer Science Engineering (CSE) course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Dynamic Programming, P & NP Concepts- 2 | 5 questions in 15 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
Test: Dynamic Programming, P & NP Concepts- 2 - Question 1

 What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?

Detailed Solution for Test: Dynamic Programming, P & NP Concepts- 2 - Question 1

In a complete graph total no of edges is

Time complexity of Bellman-Ford algo for a graph having n vertices and m edges = O(nm) for a complete graph time complexity

Test: Dynamic Programming, P & NP Concepts- 2 - Question 2

 The Ackermann’s function

Detailed Solution for Test: Dynamic Programming, P & NP Concepts- 2 - Question 2

Ackermann’s function has exponential time complexity,

1 Crore+ students have signed up on EduRev. Have you? Download the App
Test: Dynamic Programming, P & NP Concepts- 2 - Question 3

 Which of the following statements are TRUE?
1. The problem of determining whether there exists a cycle in an undirected graph is in P.
2. The problem of determining whether there , exists a cycle in an undirected graph is in NP.
3. If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A

Detailed Solution for Test: Dynamic Programming, P & NP Concepts- 2 - Question 3

1. By depth first search we can find whether there exits a cycle in an undirected graph in O(n2) times so it is P problem.
2. As so this problem will also be considered as NP problem.
3. This is the definition of NP-complete so it is trivially true.

Test: Dynamic Programming, P & NP Concepts- 2 - Question 4

 Consider two decision problems Q1, Q2 such that Q1 reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to Q2. Then which one of the following is consistent with the above statement?

Detailed Solution for Test: Dynamic Programming, P & NP Concepts- 2 - Question 4

Given Q1 ≤ 3-SAT and 3-SAT ≤ Q2 3-SAT is NP- complete.
∴ It is NP as well as NP-hard.
  is NP-problem   3-SAT ≤ Qand 3-SAT is NP-hard ⇒ Q2 is NP- hard problem.
So the strongest statements is Q1 is in NP and Q2 is NP-hard.

Test: Dynamic Programming, P & NP Concepts- 2 - Question 5

Language L1 is polynomial time reducible to language L2. Language L3 is polynomial time reducible to L2, which in turn is polynomial time reducible to language L4. Which of the following is/are True?

I. If L4 ∈ P , L2 ∈ P
II If L, ∈ P or L3e P, then L2∈ P
III. L, ∈ P, if and only if L3∈ P
IV. If L4 ∈ P, then L1 ∈ P and L3 ∈ P

Detailed Solution for Test: Dynamic Programming, P & NP Concepts- 2 - Question 5

if L1 ∈ P we cannot say anything about L2 from 
Since we cannot say anything about L2 therefore we cannot say anything about L3 either from 
So Statement III is false.
IV. If L4∈ P, then L1 ∈ P and L3 ∈ P is true.
If L4 ∈ P then fromwe can get that L2∈ P.
and from  we can now get that  L3 ∈ P 
also from we can get that L1 ∈ P
So Statement IV is true.

Information about Test: Dynamic Programming, P & NP Concepts- 2 Page
In this test you can find the Exam questions for Test: Dynamic Programming, P & NP Concepts- 2 solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Dynamic Programming, P & NP Concepts- 2, EduRev gives you an ample number of Online tests for practice

Top Courses for Computer Science Engineering (CSE)

Download as PDF

Top Courses for Computer Science Engineering (CSE)