Module V
Topological Sort
• A topological sort of a dag G(V, E) is a linear ordering of all its vertices
such that if G contains an edge u, then u appears before v in the
ordering.
• Applicable to Directed Acyclic Graph
• Many applications use directed acyclic graphs to indicate precedences
among events
• If the graph contains a cycle, then no linear ordering is possible.
• We can view a topological sort of a graph as an ordering of its
vertices along a horizontal line so that all directed edges go from left
to right.
• Each directed edge u, v means that garment u must be put on before
garment .
• The discovery and finishing times from a depth-first search are shown
next to each vertex.
String Matching – Naïve algorithm
• We assume that the text is an array T[1..n] of length n and that the
pattern is an array P[1…m]
• pattern P occurs with shift s in text T
Knuth-Morris-Pratt algorithm
The prefix function for a pattern
• The prefix function for a pattern encapsulates knowledge about how
the pattern matches against shifts of itself.
• We can take advantage of this information to avoid testing useless
shifts in the naive pattern-matching algorithm
• We preprocess the pattern and build LPS array for it. The size of this
array is same as pattern length.
• LPS is the Longest Proper Prefix which is also a Suffix. A proper prefix
is a prefix that doesn’t include whole string. For example, prefixes of
“abc” are “”, “a”, “ab” and “abc” but proper prefixes are “”, “a” and
“ab” only. Suffixes of the string are “”, “c”, “bc”, and “abc”.
• Each value, lps[i] is the length of longest proper prefix
of pat[0..i] which is also a suffix of pat[0..i].
For the pattern “AAAA”, lps[] is [0, 1, 2, 3]
For the pattern “ABCDE”, lps[] is [0, 0, 0, 0, 0]
For the pattern “AABAACAABAA”, lps[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
For the pattern “AAACAAAAAC”, lps[] is [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]
For the pattern “AAABAAA”, lps[] is [0, 1, 2, 0, 1, 2, 3]
Polynomial-time algorithms – Class P
• The class P consists of those problems that are solvable in polynomial
time.
• More specifically, they are problems that can be solved in time O(n^k)
for some constant k, where n is the size of the input to the problem.
Class NP
• The class NP consists of those problems that are “verifiable” in
polynomial time.
• If we were somehow given a “certificate” of a solution, then we could
verify that the certificate is correct in time polynomial in the size of
the input to the problem.
• For example, in the Hamiltonian cycle problem, given a directed graph
G(V,E) a certificate would be a sequence v1,v2…v|v| of vertices.
• Any problem in P is also in NP, since if a problem is in P then we can
solve it in polynomial time without even being supplied a certificate.
Decision problems vs. optimization problems
• Many problems of interest are optimization problems, in which each
feasible (i.e.,“legal”) solution has an associated value, and we wish to
find a feasible solution with the best value.
• For example, in a problem that we call SHORTEST-PATH we are given
an undirected graph G and vertices u and , and we wish to find a path
from u to that uses the fewest edges.
• In other words, SHORTEST-PATH is the single-pair shortest-path
problem in an unweighted, undirected graph.
• NP completeness applies directly not to optimization problems,
however, but to decision problems, in which the answer is simply
“yes” or “no”
• Although NP-complete problems are confined to the realm of
decision problems, we can take advantage of a convenient
relationship between optimization problems and decision problems.
• We usually can cast a given optimization problem as a related
decision problem by imposing a bound on the value to be optimized
• For example, a decision problem related to SHORTEST-PATH is PATH:
given a directed graph G, vertices u and , and an integer k, does a
path exist from u to consisting of at most k edges
Reduction
• NP-completeness is about showing how hard a problem is rather than how
easy it is, we use polynomial-time reductions in the opposite way to show
that a problem is NP-complete.
• Let us take the idea a step further, and show how we could use polynomial-
time reductions to show that no polynomial-time algorithm can exist for a
particular problem B.
• Suppose we have a decision problem A for which we already know that no
polynomial-time algorithm can exist.
• Suppose further that we have a polynomial-time reduction transforming
instances of A to instances of B.
• Now we can use a simple proof by contradiction to show that no
polynomial time algorithm can exist for B.
• Suppose that B has a polynomial-time algorithm.
• Then, using the reduction method we would have a way to solve
problem A in polynomial time, which contradicts our assumption that
there is no polynomial-time algorithm for A.
NP-completeness and reducibility
a problem is in the class NPC—and we refer to it as being NP
complete—if it is in NP and is as “hard” as any problem in NP.
Approximation
• To produce an algorithm of low polynomial complexity to solve an NP-
hard optimization problem, then it is necessary to relax the meaning
of "solve."
• There are two relaxations of the meaning of "solve."
• In the first we remove the requirement that the algorithm that solves
the optimization problem P must always generate an optimal solution
• This requirement is replaced by the requirement that the algorithm
for P must always generate a feasible solution with value close to the
value of an optimal solution
• A feasible solution with value close to the value of an optimal solution
is called an approximate solution.
• An approximation algorithm for P is an algorithm that generates
approximate solutions for P.
• In the second relaxation we look for an algorithm for P that
almost always generates optimal solution
• Algorithms with this property are called probabilistically
good algorithms
Planar Graph Coloring
• There are very few NP-hard optimization problems for which
polynomial time absolute approximation algorithms are known.
• One problem is that of determining the minimum number of colors
needed to color a planar graph G = (V,E)
• It is known that every planar graph is four colorable.
• One can easily determine whether a graph is zero, one, or two
colorable
• It is zero colorable iff V = 0.
• It is one colorable iff E = 0.
• It is two colorable iff it is bipartite
• Determining whether a planar graph is three colorable is NP-hard.
• However, all planar graphs are four colorable
• An absolute approximation algorithm is easy to obtain.
• Algorithm finds an exact answer when the graph can be colored using at
most two colors
• Since we can determine whether a graph is bipartite in time 0(|V| + |E|),
the complexity of the algorithm is 0(|V| + |E|),
Vertex Cover
• Even though we don’t know how to find an optimal vertex cover in a
graph G in polynomial time, we can efficiently find a vertex cover that
is near-optimal