FURTHER DESIGN TECHINIQUES

 Space and Time Trade-Offs

 Greedy Approach
 Backtracking
 Branch-and-Bound
Space and Time Trade-Offs
 “Things which matter most must never be at the mercy of things
which matter less. —Johann Wolfgang von Goethe (1749–1832)“
 Space and time trade-offs in algorithm design are a well-
known issue for both theoreticians and practitioners of
computing.
 As an algorithm design technique, trading space for time is much
more prevalent than trading time for space.
 useful comments about the interplay between time and space in
algorithm design need to be made.
 First, the two resources—time and space—do not have to compete
with each other in all design situations.
 Second, one cannot discuss space-time trade-offs without
mentioning the important area of data compression. Note, however,
that in data compression, size reduction is the goal rather than a
technique for solving another problem.
Approaches
 input enhancement (also called preprocessing and preconditioning)
 the idea is to preprocess the problem’s input, in whole or in part, and store the
additional information obtained to accelerate solving the problem afterward.
 algorithms based on it:
 counting methods for sorting (Section 7.1)
 Boyer-Moore algorithm for string matching and its simplified version
suggested by Horspool (Section 7.2)
 prestructuring.
 simply uses extra space to facilitate faster and/or more flexible access to the
data.
 highlights two facets of this variation of the space-for-time trade-off:
 some processing is done before a problem in question is actually solved
 but, unlike the input-enhancement variety, it deals with access structuring.
 algorithms based on it
 hashing (Section 7.3)
 indexing with B-trees (Section 7.4)
 dynamic programming.
 based on recording solutions to overlapping subproblems of a given problem in
a table from which a solution to the problem in question is then obtained
Input-enhancement Technique -
Sorting by Counting
 Count, for each element of a list to be sorted,
 the total number of elements smaller than this element
and record the results in a table.
 These numbers will indicate the positions of the
elements in the sorted list:
 e.g., if the count is 10 for some element, it should be in
the 11th position (with index 10, if we start counting with
0) in the sorted array.
 Thus, we will be able to sort the list by simply copying
its elements to their appropriate positions in a new,
sorted list. This algorithm is called comparison-
counting sort (Figure 7.1).
EXAMPLE
Time efficiency of this algorithm
Greedy Technique
 Greed, for lack of a better word, is good! Greed is right!
Greed works! —Michael Douglas, US actor in the role
of Gordon Gecko, in the film Wall Street, 1987.
 Greedy algorithm is an algorithmic paradigm based on
heuristic that follows local optimal choice at each step
with the hope of finding global optimal solution.
 In many problems, it does not produce an optimal
solution though it gives an approximate (near optimal)
solution in a reasonable time.
 It build a solution part by part, choosing the next part
in such a way, that it gives an immediate benefit.
 It never reconsiders the choices taken previously. It is
mainly used to solve optimization problems.
Counting Coins Example
 This problem is to count to a desired value by choosing
the least possible coins and the greedy approach forces
the algorithm to pick the largest possible coin. If we
are provided coins of € 1, 2, 5 and 10 and we are asked
to count € 18 then the greedy procedure will be −
 1 − Select one € 10 coin, the remaining count is 8
 2 − Then select one € 5 coin, the remaining count
is 3
 3 − Then select one € 2 coin, the remaining count
is 1
 3 − And finally, the selection of one € 1 coins solves
the problem
 Though, it seems to be working fine, for this count we
need to pick only 4 coins. But if we slightly change the
problem then the same approach may not be able to
produce the same optimum result.
 For the currency system, where we have coins of 1, 7, 10
value, counting coins for value 18 will be absolutely
optimum but for count like 15, it may use more coins
than necessary.
 For example, the greedy approach will use 10 + 1 + 1 + 1
+ 1 + 1, total 6 coins. Where as the same problem could
be solved by using only 3 coins (7 + 7 + 1)
 Hence, we may conclude that the greedy approach
picks an immediate optimized solution and may fail
where global optimization is a major concern.
The change-making problem

 Give change for a specific amount n with the least number of coins of the
denominations d1>d2 > . . .>dm used in that locale. (Here, we assume that
the denominations are ordered in decreasing order.) For example, the
widely used coin denominations in the United States are
 d1 = 25 (quarter), d2 = 10 (dime), d3 = 5 (nickel), and d4 = 1 (penny).
 How would you give change with coins of these denominations of, say, 48
cents?
 If you came up with the answer 1 quarter, 2 dimes, and 3 pennies, you
followed— consciously or not—a logical strategy of making a sequence of
best choices among the currently available alternatives.
 Indeed, in the first step, you could have given one coin of any of the four
denominations. “Greedy” thinking leads to giving one quarter because it
reduces the remaining amount the most, namely, to 23 cents. In the second
step, you had the same coins at your disposal, but you could not give a
quarter, because it would have violated the problem’s constraints. So your
best selection in this step was one dime, reducing the remaining amount to
13 cents. Giving one more dime left you with 3 cents to be given with three
pennies.
 Is this solution to the instance of the change-making
problem optimal? Yes, it is.
 In fact, one can prove that the greedy algorithm yields
an optimal solution for every positive integer amount
with these coin denominations.
 At the same time, it is easy to give an example of coin
denominations that do not yield an optimal
 solution for some amounts—e.g., d1 = 25, d2 = 10, d3 = 1
and n = 30.
 The approach applied to the change-making problem is called
greedy.
 Computer scientists consider it a general design
technique despite the fact that it is applicable to optimization
problems only.
 The greedy approach suggests constructing a solution through
a sequence of steps, each expanding a partially constructed
solution obtained so far, until a complete solution to the
problem is reached.
 On each step—and this is the central point of this
technique—the choice made must be:
 feasible, i.e., it has to satisfy the problem’s constraints
 locally optimal, i.e., it has to be the best local choice among all
feasible choices available on that step
 irrevocable, i.e., once made, it cannot be changed on
subsequent steps of the algorithm
 These requirements explain the technique’s name: on
each step, it suggests a “greedy” grab of the best
alternative available in the hope that a sequence of locally
optimal choices will yield a (globally) optimal solution to
the entire problem.
 What is usually more difficult is to prove that a greedy
algorithm yields an optimal solution (when it does).
 One of the common ways to do this is using
mathematical induction, we show that a partially
constructed solution obtained by the greedy algorithm
on each iteration can be extended to an optimal solution
to the problem.
 The second way to prove optimality of a greedy algorithm
is to show that on each step it does at least as well as any
other algorithm could in advancing toward the problem’s
goal.
 Application Areas
 Most networking algorithms use the greedy approach. Here
is a list of few of them −
 Travelling Salesman Problem
 Prim's Minimal Spanning Tree Algorithm
 Kruskal's Minimal Spanning Tree Algorithm
 Dijkstra's Minimal Spanning Tree Algorithm
 Graph - Map Coloring
 Graph - Vertex Cover
 Knapsack Problem
 Job Scheduling Problem
 There are lots of similar problems that uses the greedy
approach to find an optimum
 solution.
Prim’s Algorithm
 The following problem arises naturally in many
practical situations:
 Given n points, connect them in the cheapest possible
way so that there will be a path between every pair of
points.
 It has direct applications to the design of all kinds of
networks— including communication, computer,
transportation, and electrical—by providing the
cheapest way to achieve connectivity.
 We can represent the points given by vertices of a
graph, possible connections by the graph’s edges, and
the connection costs by the edge weights.
 Then the question can be posed as the minimum
spanning tree problem, defined formally as follows.
 DEFINITION: A spanning tree of an undirected
connected graph is its connected acyclic subgraph
(i.e., a tree) that contains all the vertices of the graph.
 If such a graph has weights assigned to its edges, a
minimum spanning tree is its spanning tree of the
smallest weight, where the weight of a tree is
defined as the sum of the weights on all its edges.
 The minimum spanning tree problem is the
problem of finding a minimum spanning tree for a
given weighted connected graph.
Prim’s algorithm
 Prim’s algorithm constructs a minimum spanning tree
through a sequence of expanding subtrees.
 The initial subtree in such a sequence consists of a single
vertex selected arbitrarily from the set V of the graph’s
vertices. On each iteration, the algorithm expands the current
tree in the greedy manner by simply attaching to it the
nearest vertex not in that tree. (By the nearest vertex, we
mean a vertex not in the tree connected to a vertex in the tree
by an edge of the smallest weight. Ties can be broken
arbitrarily.)
 The algorithm stops after all the graph’s vertices have been
included in the tree being constructed.
 Since the algorithm expands a tree by exactly one vertex on
each of its iterations, the total number of such iterations is n
− 1, where n is the number of vertices in the graph. The tree
generated by the algorithm is obtained as the set of edges
used for the tree expansions.
 Here is pseudocode of this algorithm.
The nature of Prim’s algorithm
 The nature of Prim’s algorithm makes it necessary to provide each vertex not in
the current tree with the information about the shortest edge connecting the
vertex to a tree vertex. We can provide such information by attaching two labels
to a vertex: the name of the nearest tree vertex and the length (the weight) of
the corresponding edge. Vertices that are not adjacent to any of the tree vertices
can be given the ∞ label indicating their “infinite” distance to the tree
vertices and a null label for the name of the nearest tree vertex. (Alternatively,
we can split the vertices that are not in the tree into two sets, the “fringe” and
the “unseen.” The fringe contains only the vertices that are not in the tree but
are adjacent to at least one tree vertex. These are the candidates from which the
next tree vertex is selected. The unseen vertices are all the other vertices of the
graph, called “unseen” because they are yet to be affected by the
algorithm.)With such labels, finding the next vertex to be added to the current
tree T = {V T,, ET} becomes a simple task of finding a vertex with the smallest
distance label in the set V − VT .
 Ties can be broken arbitrarily.
After we have identified a vertex u ∗ to be added to
the tree, we need to perform two operations:

The Figure that follows demonstrates the

application of Prim’s algorithm to a specific graph.
Kruskal’s Algorithm
 It looks at a minimum spanning tree of a weighted
connected graph G = V, E as an acyclic subgraph with
|V| − 1 edges for which the sum of the edge weights is
the smallest.
 (It is can be shown easily that such a subgraph must be
a tree.)
 Consequently, the algorithm constructs a minimum
spanning tree as an expanding sequence of subgraphs
that are always acyclic but are not necessarily
connected on the intermediate stages of the algorithm.
 The algorithm
begins by sorting
the graph’s edges in
nondecreasing
order of their
weights.
 Then, starting with
the empty
subgraph, it scans
this sorted list,
adding the next
edge on the list to
the current
subgraph if such
an inclusion does
not create a cycle
and simply
skipping the edge
otherwise.
 Applying Prim’s and
Kruskal’s algorithms to the
same small graph by hand
may create the impression
that the latter is simpler than
the former. This impression
is wrong because, on each of Figure?: New edge connecting two vertices may
its iterations, Kruskal’s (a) or may not (b) create a cycle.
algorithm has to check •In view of these observations, it is convenient to
whether the addition of the
next edge to the edges use a slightly different interpretation of Kruskal’s
already selected would create algorithm.
a cycle. •We can consider the algorithm’s operations as a
 A new cycle is created if and progression through a series of forests containing
only if the new edge all the vertices of a given graph and some of its
connects two vertices already edges. The initial forest consists of |V | trivial
connected by a path, i.e., if trees, each comprising a single vertex of the
and only if the two vertices graph.
belong to the same •The final forest consists of a single tree, which is
connected component a minimum spanning tree of the graph.
(Figure ?).
•On each iteration, the algorithm takes the next
 Note also that each edge (u, v) from the sorted list of the graph’s
connected component of a
subgraph generated by edges, finds the trees containing the vertices u
Kruskal’s algorithm is a tree and v, and, if these trees are not the same, unites
because it has no cycles. them in a larger tree by adding the edge (u, v).
Definition
 In graph theory, tree is an undirected graph in which
any two vertices are connected by exactly one path.
 In other words, any acyclic connected graph is a tree. A
forest is a disjoint union of trees. ... A rooted tree itself
has been defined by some authors as a directed graph.
Dijkstra’s Algorithm
 The best-known algorithm for the single-source shortest-
paths problem.
 Applicable to undirected and directed graphs with
nonnegative weights only.
 Finds the shortest paths to a graph’s vertices in order of
their distance from a given source.
 First, it finds the shortest path from the source to a vertex
nearest to it, then to a second nearest, and so on.
 In general, before its ith iteration commences, the
algorithm has already identified the shortest paths to i − 1
other vertices nearest to the source.
 These vertices, the source, and the edges of the shortest paths
leading to them from the source form a subtree Ti of the given
graph (Figure ??).

FIGURE??: Idea of Dijkstra’s algorithm. The subtree of the shortest

paths already
found is shown in bold. The next nearest to the source v0 vertex, u ∗ , is
selected by comparing the lengths of the subtree’s paths increased by the
distances to vertices adjacent to the subtree’s vertices.
 Since all the edge weights are nonnegative, the next vertex
nearest to the source can be found among the vertices
adjacent to the vertices of Ti .
 The set of vertices adjacent to the vertices in Ti can be
referred to as “fringe vertices”; they are the candidates from
which Dijkstra’s algorithm selects the next vertex nearest to
the source.
 (Actually, all the other vertices can be treated as fringe
vertices connected to tree vertices by edges of infinitely
large weights.)
 To identify the ith nearest vertex, the algorithm computes,
for every fringe vertex u, the sum of the distance to the
nearest tree vertex v (given by the weight of the edge (v, u))
and the length dv of the shortest path from the source to v
(previously determined by the algorithm) and then selects
the vertex with the smallest such sum.
 The fact that it suffices to compare the lengths of such
special paths is the central insight of Dijkstra’s algorithm.
 To facilitate the algorithm’s operations, we label each vertex
with two labels.
 The numeric label d indicates the length of the shortest
path from the source to this vertex found by the algorithm
so far; when a vertex is added to the tree, d indicates the
length of the shortest path from the source to that vertex.
 The other label indicates the name of the next-to-last
vertex on such a path, i.e., the parent of the vertex in the
tree being constructed. (It can be left unspecified for the
source s and vertices that are adjacent to none of the
current tree vertices.) With such
 labelling, finding the next nearest vertex u ∗ becomes a
simple task of finding a fringe vertex with the smallest d
value. Ties can be broken arbitrarily. After we have
identified a vertex u ∗ to be added to the tree, we need to
perform two operations:
 Figure ??? demonstrates the application of Dijkstra’s
algorithm to a specific graph.
 The shortest paths (identified by following
nonnumeric labels backward from a destination vertex
in the left column to the source) and their lengths
(given by numeric labels of the tree vertices) are as
follows:
 from a to b : a − b of length 3
 from a to d : a − b − d of length 5
 from a to c : a − b − c of length 7
 from a to e : a − b − d − e of length 9

FIGURE ??? Application of Dijkstra’s algorithm. The

next closest vertex is shown in bold.
Backtracking
 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.
 Suppose you have to make a series of decisions, among
various choices, where
 You don’t have enough information to know what to
choose
 Each decision leads to a new set of choices
 Some sequence of choices (possibly more than one) may
be a solution to your problem
 Backtracking is a methodical way of trying out various
sequences of decisions, until you find one that “works”
40
Backtracking (animation)
dead end
?
dead end
dead end

?
start ? ?
dead end

dead end

success!

41
 Backtracking: Hamiltonian Circuit
Problem
 The Hamiltonian path problem and the Hamiltonian
cycle problem are problems of determining whether
a Hamiltonian path (a path in an undirected or directed
graph that visits each vertex exactly once) or
a Hamiltonian cycle exists in a given graph (whether
directed or undirected)
 Without loss of generality, we can assume that if a
Hamiltonian circuit exists, it starts at vertex a.
 Accordingly, we make vertex a the root of the state-space
tree (Figure ?????).
 The first component of our future solution, if it exists, is a
first intermediate vertex of a Hamiltonian circuit to be
constructed.
 Using the alphabet order to break the three-way tie
among the vertices adjacent to a, we select vertex b.
 From b, the algorithm proceeds to c, then to d, then to
e, and finally to f, which proves to be a dead end.
 So the algorithm backtracks from f to e, then to d, and
then to c, which provides the first alternative for the
algorithm to pursue.
 Going from c to e eventually proves useless, and the
algorithm has to backtrack from e to c and then to b.
 From there, it goes to the vertices f , e, c, and d, from
which it can legitimately return to a, yielding the
Hamiltonian circuit a, b, f , e, c, d, a. If we wanted to
find another Hamiltonian circuit, we could continue
this process by backtracking from the leaf of the
solution found.
FIGURE ????? (a) Graph. (b) State-space tree for finding a Hamiltonian circuit. The
numbers above the nodes of the tree indicate the order in which the
nodes are generated.
Branch-and-Bound
 Recall that the central idea of backtracking, discussed in
the previous section, 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.
 Compared to backtracking, branch-and-bound requires
two additional items:
 a way to provide, for every node of a state-space tree, a bound
on the best value of the objective function1 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
Assignment Problem with
Branch-and-Bound