Module 5: Analysis & Design of Algorithms (BCS401); Dept.
of AI & ML, KIT, Tiptur
Limitations of Algorithm Power
But the power of algorithms is not unlimited, and its limits are the subject of this chapter.
Some problems cannot be solved by any algorithm. Other problems can be solved
algorithmically but not in polynomial time.
And even when a problem can be solved in polynomial time by some algorithms, there are
usually lower bounds on their efficiency.
Methods for obtaining lower bounds, which are estimates on a minimum amount of work
needed to solve a problem.
Module 5: Analysis & Design of Algorithms (BCS401); Dept. of AI & ML, KIT, Tiptur
Decision Trees
Many important algorithms, especially those for sorting and searching, work by comparing
items of their inputs. We can study the performance of such algorithms with a device called a
decision tree.
As an example, Figure 11.1 presents a decision tree of an algorithm for finding a minimum of
three numbers.
Each internal node of a binary decision tree represents a key comparison indicated in the
node, e.g., k < k1. The node’s left subtree contains the information about subsequent
comparisons made if k < k1, and its right subtree does the same for the case of k >k1.
Each leaf represents a possible outcome of the algorithm’s run on some input of size n.
Module 5: Analysis & Design of Algorithms (BCS401); Dept. of AI & ML, KIT, Tiptur
Note that the number of leaves can be greater than the number of outcomes because, for some
algorithms, the same outcome can be arrived at through a different chain of comparisons.
An important point is that the number of leaves must be at least as large as the number of
possible outcomes.
The algorithm’s work on a particular input of size n can be traced by a path from the root to a
leaf in its decision tree, and the number of comparisons made by the algorithm on such a run
is equal to the length of this path.
Hence, the number of comparisons in the worst case is equal to the height of the algorithm’s
decision tree.
Decision Trees for Sorting
Most sorting algorithms are comparison based, i.e., they work by comparing elements in a list
to be sorted. By studying properties of decision trees for such algorithms, we can derive
important lower bounds on their time efficiencies.
We can interpret an outcome of a sorting algorithm as finding a permutation of the element
indices of an input list that puts the list’s elements in ascending order.
Consider, as an example, a three-element list a, b, c of orderable items such as real numbers
or strings. For the outcome a < c<b obtained by sorting this list (see Figure below), the
permutation in question is 1, 3, 2. In general, the number of possible outcomes for sorting an
arbitrary n-element list is equal to n!.
Module 5: Analysis & Design of Algorithms (BCS401); Dept. of AI & ML, KIT, Tiptur
The height of a binary decision tree for any comparison-based sorting algorithm and hence
the worst-case number of comparisons made by such an algorithm cannot be less than log2
n!:
Module 5: Analysis & Design of Algorithms (BCS401); Dept. of AI & ML, KIT, Tiptur
For example, for the three-element insertion sort whose decision tree is given in Figure
below, this number is (2 + 3 + 3 + 2 + 3 + 3)/6 = 2*2/3.
Under the standard assumption that all n! outcomes of sorting are equally likely, the
following lower bound on the average number of comparisons Cavg made by any comparison-
based algorithm in sorting an n-element list has been proved:
Decision Trees for Searching a Sorted Array
Module 5: Analysis & Design of Algorithms (BCS401); Dept. of AI & ML, KIT, Tiptur
Module 5: Analysis & Design of Algorithms (BCS401); Dept. of AI & ML, KIT, Tiptur
P, NP, and NP-Complete Problems
Problem Types: Optimization and Decision
Optimization problem: find a solution that maximizes or minimizes some objective
function
Decision problem: answer yes/no to a question
o Many problems have decision and optimization versions.
o E.g.: traveling salesman problem
optimization: find Hamiltonian cycle of minimum length
decision: find Hamiltonian cycle of length less than or equal to m
Decision problems are more convenient for formal investigation of their complexity.
Class P
P: the class of decision problems that are solvable in O(p(n)) time, where p(n) is a polynomial
of problem’s input size n
Examples:
searching
element uniqueness
graph connectivity
graph acyclicity
primality testing
Module 5: Analysis & Design of Algorithms (BCS401); Dept. of AI & ML, KIT, Tiptur
Class NP
NP (nondeterministic polynomial): class of decision problems whose proposed solutions can
be verified in polynomial time = solvable by a nondeterministic polynomial algorithm
A nondeterministic polynomial algorithm is an abstract two-stage procedure that:
generates a random string purported to solve the problem
checks whether this solution is correct in polynomial time
By definition, it solves the problem if it’s capable of generating and verifying a solution on
one of its tries
Module 5: Analysis & Design of Algorithms (BCS401); Dept. of AI & ML, KIT, Tiptur
Module 5: Analysis & Design of Algorithms (BCS401); Dept. of AI & ML, KIT, Tiptur
Backtracking
The principal idea is to construct solutions one component at a time and evaluate such
partially constructed candidates as follows. If a partially constructed solution can be
developed further without violating the problem’s constraints, it is done by taking the first
remaining legitimate option for the next component. If there is no legitimate option for the
next component, no alternatives for any remaining component need to be considered. In this
case, the algorithm backtracks to replace the last component of the partially constructed
solution with its next option.
It is convenient to implement this kind of processing by constructing a tree of choices being
made, called the state-space tree. Its root represents an initial state before the search for a
solution begins. The nodes of the first level in the tree represent the choices made for the first
component of a solution, the nodes of the second level represent the choices for the second
component, and so on. A node in a state-space tree is said to be promising if it corresponds to
a partially constructed solution that may still lead to a complete solution; otherwise, it is
called nonpromising.
n-Queens Problem
The problem is to place n queens on an n × n chessboard so that no two queens attack
each other by being in the same row or in the same column or on the same diagonal.
For n = 1, the problem has a trivial solution, and
It is easy to see that there is no solution for n = 2 and n = 3.
So let us consider the four-queen problem (n=4) and solve it by the backtracking
technique.
Since each of the four queens has to be placed in its own row, all we need to do is to
assign a column for each queen on the board presented in Figure.
Module 5: Analysis & Design of Algorithms (BCS401); Dept. of AI & ML, KIT, Tiptur
Module 5: Analysis & Design of Algorithms (BCS401); Dept. of AI & ML, KIT, Tiptur
Subset-Sum Problem
Consider the subset-sum problem: find a subset of a given set A = {a1, . . . , an} of n
positive integers whose sum is equal to a given positive integer d.
For example, for A = {1, 2, 5, 6, 8} and d = 9, there are two solutions:
{1, 2, 6} and {1, 8}.
Of course, some instances of this problem may have no solutions.
It is convenient to sort the set’s elements in increasing order. So, we will assume that
a1< a2 < . . . < an.
The state-space tree can be constructed as a binary tree like that in Figure for the
instance A = {3, 5, 6, 7} and d = 15.
The root of the tree represents the starting point, with no decisions about the given
elements made as yet.
Its left and right children represent, respectively, inclusion and exclusion of a1 in a set
being sought.
Similarly, going to the left from a node of the first level corresponds to inclusion of
a2 while going to the right corresponds to its exclusion, and so on.
Thus, a path from the root to a node on the ith level of the tree indicates which of the
first I numbers have been included in the subsets represented by that node.
Module 5: Analysis & Design of Algorithms (BCS401); Dept. of AI & ML, KIT, Tiptur
Branch-and-Bound
The central idea of backtracking, is to cut off a branch of the problem’s state-space
tree as soon as we can deduce that it cannot lead to a solution.
This idea can be strengthened further if we deal with an optimization problem.
An optimization problem seeks to minimize or maximize some objective function (a
tour length, the value of items selected, the cost of an assignment, and the like),
usually subject to some constraints.
Note that in the standard terminology of optimization problems, a feasible solution is
a point in the problem’s search space that satisfies all the problem’s constraints (e.g.,
a Hamiltonian circuit in the travelling salesman problem or a subset of items whose
total weight does not exceed the knapsack’s capacity in the knapsack problem).
Whereas an optimal solution is a feasible solution with the best value of the objective
function (e.g., the shortest Hamiltonian circuit or the most valuable subset of items
that fit the knapsack).
Compared to backtracking, branch-and-bound requires two additional items:
For every node of a state-space tree, a bound on the best value of the objective
function on any solution that can be obtained by adding further components to the
partially constructed solution represented by the node. The value of the best solution
seen so far
If this information is available, we can compare a node’s bound value with the value
of the best solution seen so far.
Module 5: Analysis & Design of Algorithms (BCS401); Dept. of AI & ML, KIT, Tiptur
Knapsack Problem
Given n items of known weights wi and values vi , i = 1, 2, . . . , n, and a knapsack of
capacity W, find the most valuable subset of the items that fit in the knapsack.
It is convenient to order the items of a given instance in descending order by their
value-to-weight ratios.
Then the first item gives the best payoff per weight unit and the last one gives the
worst payoff per weight unit, with ties resolved arbitrarily:
A simple way to compute the upper bound ub is to add to v, the total value of the
items already selected, the product of the remaining capacity of the knapsack W − w
and the best per unit payoff among the remaining items, which is vi+1/wi+1:
Module 5: Analysis & Design of Algorithms (BCS401); Dept. of AI & ML, KIT, Tiptur
Module 5: Analysis & Design of Algorithms (BCS401); Dept. of AI & ML, KIT, Tiptur
Approximation Algorithms for NP-Hard Problems
A different approach to handling difficult problems of combinatorial optimization, such as
the traveling salesman problem and the knapsack problem.
There are no known polynomial-time algorithms for these problems, and there are serious
theoretical reasons to believe that such algorithms do not exist.
What then are our options for handling such problems, many of which are of significant
practical importance?
Approximation Algorithms for the Knapsack Problem
The knapsack problem, well-known NP-hard problem:
Given n items of known weights w1, . . . , wn and
values v1, . . . , vn and
a knapsack of weight capacity W,
find the most valuable subset of the items that fits into the knapsack.
Greedy Algorithms for the Knapsack Problem
We can think of several greedy approaches to this problem.
One is to select the items in decreasing order of their weights; however, heavier items
may not be the most valuable in the set.
Alternatively, if we pick up the items in decreasing order of their value, there is no
guarantee that the knapsack’s capacity will be used efficiently.
Can we find a greedy strategy that takes into account both the weights and values?
Yes, we can, by computing the value-to-weight ratios vi/wi, i = 1, 2, . . . , n, and
selecting the items in decreasing order of these ratios.
Here is the algorithm based on this greedy heuristic.
Module 5: Analysis & Design of Algorithms (BCS401); Dept. of AI & ML, KIT, Tiptur
The greedy algorithm will select the first item of weight 4,
skip the next item of weight 7,
select the next item of weight 5, and
skip the last item of weight 3.
Optimal solution is
Profit=40 + 25 = 65
Module 5: Analysis & Design of Algorithms (BCS401); Dept. of AI & ML, KIT, Tiptur
For example, for the four-item instance used to illustrate the greedy algorithm for the discrete
version,
the algorithm will take the first item of weight 4 and
then 6/7 of the next item on the sorted list to fill the knapsack to its full capacity.
Optimal solution is
Profit=40 + 36 = 76