Description

This mock test of Dynamic Programming, P & NP Concept ( Advance Level) - 1 for Computer Science Engineering (CSE) helps you for every Computer Science Engineering (CSE) entrance exam.
This contains 5 Multiple Choice Questions for Computer Science Engineering (CSE) Dynamic Programming, P & NP Concept ( Advance Level) - 1 (mcq) to study with solutions a complete question bank.
The solved questions answers in this Dynamic Programming, P & NP Concept ( Advance Level) - 1 quiz give you a good mix of easy questions and tough questions. Computer Science Engineering (CSE)
students definitely take this Dynamic Programming, P & NP Concept ( Advance Level) - 1 exercise for a better result in the exam. You can find other Dynamic Programming, P & NP Concept ( Advance Level) - 1 extra questions,
long questions & short questions for Computer Science Engineering (CSE) on EduRev as well by searching above.

QUESTION: 1

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

Solution:

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

QUESTION: 2

The Ackermann’s function

Solution:

Ackermann’s function has exponential time complexity,

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

Solution:

1. By depth first search we can find whether there exits a cycle in an undirected graph in O(n^{2}) 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.

QUESTION: 4

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

Solution:

Given Q_{1} ≤ 3-SAT and 3-SAT ≤ Q_{2} 3-SAT is NP- complete.

∴ It is NP as well as NP-hard.

is NP-problem 3-SAT ≤ Q_{2 }and 3-SAT is NP-hard ⇒ Q_{2} is NP- hard problem.

So the strongest statements is Q_{1} is in NP and Q_{2} is NP-hard.

QUESTION: 5

Language L_{1} is polynomial time reducible to language L_{2}. Language L_{3} is polynomial time reducible to L_{2}, which in turn is polynomial time reducible to language L_{4}. Which of the following is/are True?

I. If L_{4} ∈ P , L_{2} ∈ P

II If L, ∈ P or L_{3}e P, then L_{2}∈ P

III. L, ∈ P, if and only if L_{3}∈ P

IV. If L_{4} ∈ P, then L_{1} ∈ P and L_{3} ∈ P

Solution:

if L_{1} ∈ P we cannot say anything about L_{2} from

Since we cannot say anything about L_{2} therefore we cannot say anything about L_{3} either from

So Statement III is false.

IV. If L_{4}∈ P, then L_{1} ∈ P and L_{3} ∈ P is true.

If L_{4} ∈ P then fromwe can get that L_{2}∈ P.

and from we can now get that L_{3} ∈ P

also from we can get that L_{1} ∈ P

So Statement IV is true.

### Dynamic Programming

Video | 52:19 min

### Knapsack Problem - Dynamic Programming

Doc | 36 Pages

### Notes - Dynamic Programming

Doc | 3 Pages

### Alignment by Dynamic Programming

Doc | 4 Pages

- Dynamic Programming, P & NP Concept ( Advance Level) - 1
Test | 5 questions | 15 min

- Dynamic Programming, P & NP Concepts (Basic Level)
Test | 10 questions | 30 min

- Programming In C++, C And Java (Advance Level) - 1
Test | 15 questions | 45 min

- Dynamic Programming And Divide-And-Conquer MCQ - 1
Test | 20 questions | 60 min

- Test: Timer Programming
Test | 10 questions | 10 min