MODULE – 5
Part-I
Short Answer Type Questions
1) What are the features/characteristics of an efficient algorithm?
Ans) Efficiency in algorithms refers to how well an algorithm utilizes computational resources
such as time and space to solve a problem.
1. Time Complexity: An efficient algorithm should have a minimal time complexity,
which means it should complete its execution within a reasonable amount of time.
The time complexity is often expressed using Big O notation, which provides an
upper bound on the growth rate of the algorithm as the input size increases.
2. Space Complexity: Similarly, an efficient algorithm should use a minimal amount of
memory or space to solve a problem. It should avoid excessive memory usage and
optimize the storage requirements for data structures and variables.
3. Scalability: An efficient algorithm should be scalable, meaning it can handle larger
input sizes without a significant increase in execution time or memory usage. It
should have a growth rate that is proportional to the input size, preferably linear or
sub-linear.
4. Correctness: An efficient algorithm should produce the correct output for all valid
inputs. It should accurately solve the problem it is designed for, considering all
possible edge cases and scenarios.
5. Clarity and Simplicity: An efficient algorithm should be easy to understand,
implement, and maintain. It should have clear and concise code with well-defined
steps. A simple algorithm is often more efficient than a complex one, as it reduces
the chance of introducing unnecessary computations or bugs.
2) Define disjoint set data structure with example.
Ans) Two sets are called disjoint sets if they don’t have any element in common, the intersection of
sets is a null set. A data structure that stores non overlapping or disjoint subset of elements is called
disjoint set data structure. Let's understand the disjoint sets through an example.
s1 = {1, 2, 3, 4}
s2 = {5, 6, 7, 8}
We have two subsets named s1 and s2. The s1 subset contains the elements 1, 2, 3, 4, while s2
contains the elements 5, 6, 7, 8. Since there is no common element between these two sets, we
will not get anything if we consider the intersection between these two sets. This is also
known as a disjoint set where no elements are common.
3) State and explain the operations that can be performed on disjoint set data structure.
Ans) The main operations in a disjoint set data structure are:
1. MakeSet(x): Creates a new subset with a single element x.
2. Find(x): Returns the representative or parent element of the subset that x belongs to. The
representative element is typically chosen as the root of the subset's tree structure.
3. Union(x, y): Merges the subsets containing elements x and y into a single subset.
Let's consider a set of elements: {A, B, C, D, E, F}
Initially, each element is in its own subset:
{A}, {B}, {C}, {D}, {E}, {F}
Now, let's perform some operations:
1. Union(A, B): Merges subsets containing A and B.
Updated sets: {A, B}, {C}, {D}, {E}, {F}
2. Union(C, D): Merges subsets containing A and B.
Updated sets: {A, B}, {C,D}, {E}, {F}
3. Find(E): Returns the representative element of the subset containing E.
Find(E) -> E
4. Find(D): Returns the representative element of the subset containing D.
Find(D) -> C
The disjoint set data structure allows us to efficiently perform operations like merging subsets and
finding the representative element of a given element.
4) What are tractable and intractable Problems.
Ans) Tractable problems, also known as solvable or efficiently solvable problems, are those for which
there exists an algorithm that can solve them within a reasonable amount of time. These algorithms
have polynomial time complexity, meaning their running time grows at a rate that is polynomial in
the size of the input. Tractable problems can typically be solved in practice, even for large input sizes.
On the other hand, intractable problems are those for which there is
no known algorithm that can solve them efficiently for all possible inputs. These problems have
superpolynomial time complexity, where the running time grows faster than any polynomial function
of the input size. Intractable problems are generally difficult to solve in practice, particularly as the
input size increases.
5) Define Cook’s theorem.
Ans) Cook's theorem, also known as Cook-Levin theorem, the theorem establishes the
concept of NP-completeness and demonstrates the existence of problems that are believed
to be intractable.
Cook's theorem states that the Boolean satisfiability problem (SAT) is NP-
complete. The SAT problem is the task of determining whether there exists an assignment of
truth values (true or false) to variables in a given Boolean formula such that the formula
evaluates to true.
The significance of Cook's theorem is that it establishes a foundational result in computational
complexity theory. It demonstrates that if an efficient algorithm can be found for solving the
SAT problem, it would imply an efficient algorithm for solving all problems in NP, and
therefore, P = NP.
6) State deterministic algorithm and non-deterministic algorithm.
Ans) A deterministic algorithm is a type of algorithm that, given the same input, will always produce
the same output and follow the same sequence of steps to arrive at the solution. In other words, it is
predictable and does not involve any randomness or non-determinism during its execution. The
behavior of a deterministic algorithm is entirely determined by its input and the logic specified in the
algorithm itself.
On the other hand, a non-deterministic algorithm is a type of algorithm that
may exhibit non-deterministic behavior during its execution. Non-deterministic algorithms can have
multiple possible paths or choices to follow at certain stages, and they can explore all possible paths
in parallel. These algorithms are based on the concept of non-determinism, where the algorithm can
guess or choose different options simultaneously, exploring different branches of computation.
7) Define decision problem and optimization problem.
Ans) Decision Problem:
A decision problem is a type of computational problem that requires a yes/no answer based
on a given input. It is a problem that can be formulated as a question, and the goal is to
determine whether the answer to the question is "yes" or "no." Decision problems are often
used in theoretical computer science to analyze the computational complexity of solving
specific problems.
Examples of decision problems:
• Is a given number prime?
• Does a graph have a Hamiltonian cycle?
Optimization Problem:
An optimization problem is a type of computational problem that involves finding the best
solution from a set of possible solutions which focus on a binary yes/no answer, optimization
problems seek to find the best possible solution, which may involve maximizing profits,
minimizing costs, optimizing efficiency, or achieving an optimal arrangement.
Examples of optimization problems:
• Finding the shortest path between two points in a graph.
• Maximizing the profit of a production process given limited resources.
8) What is node cover decision problem.
Ans) The Node Cover decision problem is a computational problem that involves graphs and seeks to
determine if there exists a node cover of a certain size or below. A node cover in a graph is a set of
nodes such that every edge in the graph is incident to at least one node in the set. In other words, it is
a set of nodes that "covers" all the edges in the graph.
Part-II
Focused-Short answer type Questions
1) Define circuit satisfiability. Prove that 3 CNF is np complete.
Ans) Circuit Satisfiability, also known as the Boolean Circuit Satisfiability problem or the SAT
problem, is a decision problem in computer science. It involves determining if there exists an input
assignment to the inputs of a Boolean circuit that makes the circuit output a true value.
To prove: -
1. Concept of 3CNF SAT
2. SAT≤ρ 3CNF SAT
3. 3CNF≤ρ SAT
4. 3CNF ϵ NPC
1. CONCEPT: - In 3CNF SAT, you have at least 3 clauses, and in clauses, you will have
almost 3 literals or constants.
2. SAT ≤ρ 3CNF SAT:- In which firstly you need to convert a Boolean function created in
SAT into 3CNF either in POS or SOP form within the polynomial time
F=X+YZ
= (X+Y) (X+Z)
= (X+Y+ZZ') (X+YY'+Z)
= (X+Y+Z) (X+Y+Z') (X+Y+Z) (X+Y'+Z)
= (X+Y+Z) (X+Y+Z') (X+Y'+Z)
3. 3CNF ≤p SAT: - From the Boolean Function having three literals we can reduce the
whole function into a shorter one.
F= (X+Y+Z) (X+Y+Z') (X+Y'+Z)
= (X+Y+Z) (X+Y+Z') (X+Y+Z) (X+Y'+Z)
= (X+Y+ZZ') (X+YY'+Z)
= (X+Y) (X+Z)
= X+YZ
4. 3CNF ϵ NPC: - As you know very well, you can get the 3CNF through SAT and SAT
through CIRCUIT SAT that comes from NP.
Part-III
Long answer type Questions
1) Define NP completeness. State chromatic number decision problem and clique
decision problem.
Ans) NP completeness is a concept in computational complexity theory that classifies
computational problems based on their computational difficulty. A problem is said to be
NP-complete if it is in the complexity class NP (nondeterministic polynomial time) and all
other problems in NP can be reduced to it in polynomial time.
The Chromatic Number decision problem is a computational problem that involves
graphs and seeks to determine the minimum number of colors required to color the
vertices of a graph such that no two adjacent vertices share the same color. It is a
decision problem related to graph coloring.
The Clique decision problem is a computational problem that involves graphs and seeks
to determine if a graph contains a clique of a certain size or above. A clique in a graph is
a subset of vertices where every vertex is connected to every other vertex in the subset.
2) Define class P, NP and NP- HARD. Show the relationship between np, p and np complete.
Ans) P (Polynomial Time): The class P consists of decision problems that can be solved by a
deterministic Turing machine in polynomial time. In other words, problems in P can be solved
efficiently using an algorithm that runs in polynomial time, where the running time is bounded
by a polynomial function of the input size. A problem in P is considered to be tractable and
efficiently solvable.
NP (Nondeterministic Polynomial Time): The class NP consists of decision problems for which a
solution can be verified in polynomial time. In other words, if there is a proposed solution to an
NP problem, it can be checked by a deterministic Turing machine in polynomial time to
determine whether it is correct or not. However, finding the solution itself may not be as
straightforward and efficient. NP stands for "nondeterministic polynomial time" because the
verification of a solution can be seen as a nondeterministic process. It is important to note that
NP does not stand for "non-polynomial" or "not possible."
NP-hard (Nondeterministic Polynomial-time hard): The class NP-hard consists of decision
problems that are at least as hard as the hardest problems in NP. In other words, an NP-hard
problem is one for which if there exists a polynomial-time algorithm to solve it, then there would
be a polynomial-time algorithm to solve all problems in NP. NP-hard problems are considered to
be among the most difficult problems in computational complexity theory. An NP-hard problem
may or may not be in NP itself.
The relationship between these classes can be visualized as follows:
P
/\
/ \
/ \
NP- Complete NP
P is a subset of NP: Problems that can be solved efficiently in polynomial time (P) are also in the
class NP since a polynomial-time algorithm can also be seen as a polynomial-time verifier.
NP-complete problems are in NP: NP-complete problems are by definition in NP since they are a
subset of NP. Any problem in NP-complete can be verified in polynomial time, and thus, they are
in NP.
NP-complete problems are the hardest problems in NP: NP-complete problems are the most
difficult problems in NP because any problem in NP can be reduced to an NP-complete problem
in polynomial time. If an efficient algorithm is discovered for any NP-complete problem, it would
imply an efficient algorithm for all problems in NP, making P = NP.