1. Define Dynamic Programming and its Principle.
Dynamic Programming (DP) is a method used to solve complex problems by dividing them into
smaller overlapping subproblems. It stores the results of these subproblems to avoid redundant
calculations. The principle involves using optimal substructure and overlapping subproblems to
achieve efficiency.
2. Define the Sum of Subsets problem in view of Backtracking.
The Sum of Subsets problem aims to find all subsets of a given set whose sum equals a target
value. Backtracking systematically explores all subset possibilities and eliminates those that exceed
the target sum. It helps reduce the search space and improves the efficiency of finding valid
subsets.
3. What is the main difference between Backtracking and Branch and Bound?
Backtracking is mainly used for constraint satisfaction problems like N-Queens or Sudoku. Branch
and Bound is used for optimization problems such as the Knapsack or Traveling Salesman
Problem. Backtracking prunes based on constraints, while Branch and Bound prunes using bounds
or costs.
4. State Cook’s Theorem.
Cook’s Theorem, proved by Stephen Cook in 1971, states that the Boolean satisfiability problem
(SAT) is NP-Complete. It was the first problem shown to be NP-Complete, establishing the
foundation for NP-Completeness theory. The theorem implies that if SAT can be solved in
polynomial time, every NP problem can also be solved in polynomial time.
5. Analyze the time complexity of Clique Decision Problem.
The Clique Decision Problem checks whether a graph contains a clique of size k. It involves testing
all possible subsets of vertices to see if they form a clique. Its time complexity is exponential,
typically O(2■), since it must check every subset combination.
6. Analyze the time complexity of Bellman-Ford Algorithm for finding shortest paths in a graph.
The Bellman-Ford Algorithm computes shortest paths from a single source to all vertices in a graph,
even with negative weights. It relaxes all edges (V-1) times, where V is the number of vertices and
E is the number of edges. Hence, its time complexity is O(V × E), making it less efficient than
Dijkstra for non-negative weights.
7. What is Graph Coloring in view of Backtracking?
Graph Coloring is the process of assigning colors to vertices so that no two adjacent vertices share
the same color. Backtracking assigns colors one by one, backtracking when an invalid color
assignment is made. It is commonly used in scheduling and map-coloring problems.
8. What is the Edit Distance (String Editing) problem, and which operations are involved?
The Edit Distance problem determines the minimum number of operations required to convert one
string into another. The allowed operations are Insertion, Deletion, and Substitution. It is solved
using dynamic programming and is used in spell checkers and DNA sequence analysis.
9. State Cook’s Theorem.
Cook’s Theorem establishes that SAT (Satisfiability) is NP-Complete. Every problem in NP can be
reduced to SAT using a polynomial-time reduction. It is a fundamental result that connects all
NP-Complete problems under a common framework.
10. What is the Chromatic Number Decision Problem (CNDP) in graph theory?
The Chromatic Number Decision Problem asks if a graph can be colored with k or fewer colors. It
helps determine the minimum number of colors required so that no two adjacent vertices share the
same color. CNDP is an NP-Complete problem in computational complexity.
11. What is Memorization in Dynamic Programming?
Memorization is a top-down approach used in dynamic programming. It stores the results of
subproblems in a lookup table to prevent recalculations. This technique improves time efficiency
and is often implemented using recursion with caching.
12. What are dead nodes in a state space tree?
Dead nodes represent parts of the state space tree that cannot lead to a feasible or optimal
solution. They occur when constraints are violated or bounds are not met. Such nodes are pruned
to reduce unnecessary computation and improve efficiency.
13. What is Chronological Backtracking?
Chronological Backtracking is a systematic method where, upon reaching a dead end, the algorithm
backtracks to the most recent decision point. It explores alternative choices in chronological order
of decision-making. This approach ensures completeness while avoiding repetition.
14. State NP-Complete.
A problem is NP-Complete if it belongs to NP and every other NP problem can be polynomially
reduced to it. These problems are the hardest in NP, meaning a polynomial-time solution to one
implies polynomial-time solutions to all. Examples include SAT, Clique, and Traveling Salesman
problems.
15. What is meant by Decision Problem?
A Decision Problem is a problem that can be answered with a simple 'yes' or 'no'. It focuses on
determining the existence or non-existence of a solution rather than finding the actual solution. For
example: 'Is there a path of length ≤ k between two nodes in a graph?'
