Chapter 5

Advanced design and analysis techniques

 Chapter About…..
• Dynamic programming
• Greedy algorithms
• Amortized analysis
 What is Dynamic Programming?
• Dynamic Programming is a technique for algorithm design.
• It is a tabular method in which it uses divide-and-conquer to
solve problems.
• dynamic programming is applicable when the subproblems
are not independent.
• So to solve a given problem, we need to solve different parts
of the problem.
 Advantage
• A dynamic-programming algorithm solves every
subsubproblem just once and then saves its answer
in a table, thereby avoiding the work of
recomputing the answer every time the
subsubproblem is encountered.
• Dynamic programming is typically applied to
optimization problems. In such problems there
can be many possible solutions. Each solution has
a value, and we wish to find a solution with the
optimal (minimum or maximum) value.
 DP algorithm can be broken into a
sequence of four steps.
1. Characterize the structure of an optimal
solution.
2. Recursively define the value of an optimal
solution.
3. Compute the value of an optimal solution in a
bottom-up fashion.
4. Construct an optimal solution from computed
information
 Algorithms
• Matrix-chain multiplication
• Elements of dynamic programming
 Optimal substructure
 Overlapping subproblems
 Memoization
• Longest common subsequence
 Elements of dynamic programming
• Optimal substructure
if an optimal solution to the problem contains
within it optimal solutions to subproblems.
Whenever a problem exhibits optimal
substructure, it is a good clue that dynamic
programming might apply.
 Overlapping subproblems

• Dynamic-programming algorithms typically

take advantage of overlapping subproblems
by solving each subproblem once and then
storing the solution in a table where it can be
looked up when needed, using constant time
per lookup.
Example
 Memoization
• offers the efficiency of the usual dynamic-
programming approach while maintaining a top-
down strategy.
• A memoized recursive algorithm maintains an
entry in a table for the solution to each
subproblem. Each table entry initially contains a
special value to indicate that the entry has yet to
be filled in.
• When the subproblem is first encountered during
the execution of the recursive algorithm, its
solution is computed and then stored in the
table.
• Each subsequent time that the subproblem is
encountered, the value stored in the table is
simply looked up and returned.
 Matrix-chain multiplication
• Dynamic programming is an algorithm that solves
the problem of matrix-chain multiplication. We
are given a sequence (chain) A1, A2, . . ., An of n
matrices to be multiplied, and we wish to
.
compute the product A1 A2 ……. An .
.
• We can evaluate the expression using the
standard algorithm for multiplying pairs of
matrices as a subroutine once we have
parenthesized it to resolve all ambiguities in how
the matrices are multiplied together.
• A product of matrices is fully parenthesized if it is
either a single matrix or the product of two fully
parenthesized matrix products, surrounded by
parentheses
 For example,
• if the chain of matrices is A1, A2, A3, A4 , the
product A1A2A3A4 can be fully parenthesized in
five distinct ways:
(A1(A2(A3A4))) ,
• (A1((A2A3)A4)) ,
• ((A1A2)(A3A4)) ,
• ((A1(A2A3))A4) ,
• (((A1A2)A3)A4) .
 matrix-chain multiplication problem
• given a chain A1, A2, . . . , An of n matrices,
where for i = 1, 2, . . . , n , matrix Ai has
dimension pi - 1 X pi, fully parenthesize the
product A1 A2...An in a way that minimizes the
number of scalar multiplications.
 Steps to be followed
• structure of an optimal parenthesization
• A recursive solution
• Computing the optimal costs
 Algorithm
MATRIX-CHAIN-ORDER(p)
1 n  length[p] - 1
2 for i  1 to n
3 do m[i, i]  0
4 for l  2 to n
5 do for i  1 to n - l + 1
6 do j  i + l-1
7 m[i, j] ∞
8 for k  i to j - 1
9 do q  m[i, k] + m[k + 1, j] +pi - 1pkpj
10 if q < m[i, j]
11 then m[i, j] q
12 s[i, j]  k
13 return m and s
 The m and s tables computed by MATRIX-CHAIN-ORDER for n =
6 and the following matrix dimensions

matrix dimension
-----------------
A1 30 X 35
A2 35 X 15
A3 15 X 5
A4 5 X 10
A5 10 X 20
A6 20 X 25
 Longest common subsequence
• A subsequence of a given sequence is just the
given sequence with some elements (possibly
none) left out
• X = (x1, x2, . . . , xm ), another sequence Z =( z1, z2, .
. . , zk )is a subsequence of X if there exists a
strictly increasing sequence (i1, i2, . . . , ik )of
indices of X such that for all j = 1, 2, . . . , k, we
have xij = zj.
• For example, Z = <B, C, D, B >is a subsequence of
X =< A, B, C, B, D, A, B> with corresponding index
sequence <2, 3, 5, 7 >
 Example
• Given two sequences X and Y, we say that a
sequence Z is a common subsequence of X
and Y if Z is a subsequence of both X and Y.
For example, if X = <A, B, C, B, D, A, B> and Y =
<B, D, C, A, B, A , >
 Theorem
• Let X = <x1, x2, . . . , xm >and Y = <y1, y2, . . . , yn
>be sequences, and let Z = <z1, z2, . . . , zk >be
any LCS of X and Y.
1. If xm = yn, then zk = xm = yn and Zk-l is an LCS of
Xm-l and Yn-l.
2. If xm ≠yn, then zk ≠xm implies that Z is an LCS of
Xm-1 and Y.
3. If xm ≠yn, then zk ≠yn implies that Z is an LCS of
X and Yn-l.
A recursive solution to subproblems
 Computing the length of an LCS
• LCS-LENGTH on the sequences X = <A, B, C, B, D, A, B>
and Y = <B, D, C, A, B, A> .
• The square in row i and column j contains the value of
c[i, j] and the appropriate arrow for the value of b[i, j].
• The entry 4 in c[7, 6]--the lower right-hand corner of
the table--is the length of an LCS B, C, B, A of X and Y.
• For i, j > 0, entry c[i, j] depends only on whether xi = yj
and the values in entries c[i -1, j], c[i, j - 1], and c[i - 1, j
- 1], which are computed before c[i, j].
• To reconstruct the elements of an LCS, follow the b[i, j]
arrows from the lower right-hand corner; the path is
shaded. Each " on the path corresponds to an entry
(highlighted) for which xi = yj is a member of an LCS.
 Algorithm
LCS-LENGTH(X,Y)
1 m  length[X]
2 n  length[Y]
3 for i  1 to m
4 do c[i,0]  0
5 for j  0 to n
6 do c[0, j]  0
7 for i  1 to m
8 do for j  1 to n
9 do if xi = yj
10 then c[i, j] c[i - 1, j -1] + 1
11 b[i, j]  " ↖"
12 else if c[i - 1, j] ≥c[i, j - 1]
13 then c[i, j]  c[i - 1, j]
14 b[i, j]  " ↑“
15 else c[i, j]  c[i, j -1]
16 b[i, j]  "  "
17 return c and b
Constructing an LCS
 Greedy Algorithm
• A greedy algorithm always makes the choice
that looks best at the moment. That is, it
makes a locally optimal choice in the hope
that this choice will lead to a globally optimal
solution.
 Applications
• Nontrivial problem,
• The activity-selection problem,
• Data-compression (Huffman) codes.
• problem of scheduling unit-time tasks with
deadlines and penalties.
• The greedy method is quite powerful and works
well for a wide range of problems.
• minimum-spanning-tree algorithms
• Dijkstra's algorithm for shortest paths form a
single source
• Minimum spanning trees
 activity-selection problem
• Suppose we have a set S = { 1, 2, . . . , n} of n proposed
activities that wish to use a resource, such as a lecture
hall, which can be used by only one activity at a time.
• Each activity i has a start time si
• finish time âi, where si ≤ âi. If selected, activity i takes
place during the half-open time interval [si,âi).
• Activities i and j are compatible if the intervals [si, âi)
and [sj,âj) do not overlap (i.e., i and j are compatible if
si ≥âj or sj ≥âi).
• The activity-selection problem is to select a maximum-
size set of mutually compatible activities.
 Algorithm
GREEDY-ACTIVITY-SELECTOR(s, f)
1 n  length[s]
2 A  {1}
3j 1
4 for i  2 to n
5 do if si ≥ âj
6 then A  A U {i}
7 j i
8 return A
Example
 0-1 knapsack problem
• A thief robbing a store finds n items; the ith item
is worth vi dollars and weighs wi pounds, where vi
and wi are integers.
• He wants to take as valuable a load as possible,
but he can carry at most W pounds in his
knapsack for some integer W.
• What items should he take?
• (This is called the 0-1 knapsack problem because
each item must either be taken or left behind; the
thief cannot take a fractional amount of an item
or take an item more than once.)
 fractional knapsack problem
• the setup is the same, but the thief can take
fractions of items, rather than having to make
a binary (0-1) choice for each item.
• You can think of an item in the 0-1 knapsack
problem as being like a gold ingot, while an
item in the fractional knapsack problem is
more like gold dust.
 Solution

(a)The thief must select a subset of the three items shown whose weight must
not exceed 50 pounds.
(b)The optimal subset includes items 2 and 3. Any solution with item 1 is
suboptimal, even though item 1 has the greatest value per pound.
(c) For the fractional knapsack problem, taking the items in order of greatest
value per pound yields an optimal solution.
 AMORTIZED ANALYSIS
• In an amortized analysis, the time required to
perform a sequence of data-structure
operations is averaged over all the operations
performed.
• Amortized analysis can be used to show that
the average cost of an operation is small, if one
averages over a sequence of operations, even
though a single operation might be expensive.
• Amortized analysis differs from average-case
analysis in that probability is not involved; an
amortized analysis guarantees the average
performance of each operation in the worst
case.
 Importance of AA
• we want to analyze the complexity of
performing a sequence of operations on a
particular data structure. In some cases,
knowing the complexity of each operation in
the sequence is important, so we can simply
analyze the worst-case complexity of each
operation.
• In other cases, only the time complexity for
processing the entire sequence is important.
 Definition of Worst case sequence
complexity
• "worst-case sequence complexity" of a
sequence of m operations as the MAXIMUM
total time over all sequences of m operations

T(m) = worst-case cost of doing a sequence of m

operations
 Definition of amortized sequence
complexity
• amortized sequence complexity of a sequence of m
operations is defined as follows:

amortized worst-case sequence complexity

Sequence = ---------------------------------------------
m
Amortized analyses make more sense than a plain
worst-case time analysis in many situation
Three Most Common Techniques Used
In Amortized Analysis

• Aggregate Method
• Accounting Method
• Potential Method
 Aggregate Method

• In the aggregate method of amortized

analysis, we show that for all n, a sequence of
n operations takes worst-case time T(n) in
total. In the worst case, the average cost, or
amortized cost, per operation
• therefore T(n) / n.
 The accounting method
• In the accounting method of amortized
analysis, we assign differing charges to
different operations, with some operations
charged more or less than they actually cost.
The amount we charge an operation is called
its amortized cost.
• When an operation's amortized cost exceeds
its actual cost, the difference is assigned to
specific objects in the data structure as credit.
• Credit can be used later on to help pay for
operations whose amortized cost is less than
their actual cost
 The potential method
• Instead of representing prepaid work as credit
stored with specific objects in the data
structure, the potential method of amortized
analysis represents the prepaid work as
"potential energy,"or just "potential," that can
be released to pay for future operations.
• The potential is associated with the data
structure as a whole rather than with specific
objects within the data structure.
 potential function

A potential function maps each data structure D

to a real number(Di), which is the potential
associated with data structure Di.
The amortized cost of the ith operation with
respect to potential function