Computer Science 3719, Winter '08
Course Diary
Copyright 2008 by H.T. Wareham
All rights reserved
Week 1,
Week 2,
Week 3,
(MidTerm Exam Notes),
Week 4,
Week 5,
Week 6,
(Final Exam Notes #1),
(Final Exam Notes #2),
(end of diary)
Thursday, February 7 (Lecture #1)
[Class Notes]
 Algorithm Design Techniques
 Over the next few lectures, we'll look in depth at various
design algorithm design techniques for various problems on
discrete structures.
 In many cases, we will be looking for a substructure of a
given structure that is optimal relative to some function
(combinatorial optimization problems). It would be
worth talking a bit more about these before we go on.
 Combinatorial optimization problems
 Each solution associated with an instance of a
combinatorial optimization problem has
a cost, and we want the solutions of optimal
(min/max) cost over the whole solution space.
 Any time you have a problem of the form "Find
the best X" where X is some discrete structure,
chances are you're dealing with a combinatorial
optimization problem.
 Distinguish several types of solutions:
 Candidate solutions = all possible solutions to
the instance, e,g., all possible
edgesequences of a given graph that start with
vertex u and end with vertex v.
 Viable solutions = all potentially optimal
candidate solutions, e.g., all
edgesequences of a given graph that are paths
between vertices u and v.
 Optimal solutions = those viable solutions that
have optimal value relative to the cost
function over the set of viable solutions,
e.g., all paths in a given graph between
vertices u and v that have the
smallest number of edges over the space of
all such paths.
 Each such problem instance has a combinatorial,
i.e., exponential in instance size, candidate
(and often
viable) solution space  the job of an algorithm
is to find the optimal solutions in this space
(of which there will always be at least one).
 Example: The 0/1 Knapsack problem
0/1 Knapsack
Input: A set U of items, an itemsize
function s(), an itemvalue function v(), and
a positive integer B.
Output: A subset U' of U such that the
sum of the sizes of the items in U' is less
than or equal to B and the sum of the values of
the items in U' is the largest possible.
space.
 Candidate solutions = subsets of U.
 Viable solutions = subsets of U whose summed size
is <= B.
 Optimal solutions = subsets of U whose summed size
is <=B and whose summed value is maximum over the
space of viable solutions.
 Each subset U' can be modeled as a binary vector
of length U (v_i = 1 (0) => item i is (not) in
U'); hence, there are 2^{U}
candidate solutions for any instance of 0/1 Knapsack.
 Sometimes, you can't generate viable solutions 
you have to generate all candidate solutions and
check viability along the way.
 Example: The Longest Common Subsequence problem
Longest common subsequence (LCS)
Input: Two strings s, s' over an alphabet
Sigma.
Output: All strings s'' over Sigma such that s'' is
a subsequence of both s and s' and the length of
s'' is of is maximized over the solution space.
 Candidate solutions = all possible strings over
alphabet Sigma of length <= min(s,s').
 Viable solutions = all subsequences of the shorter
given string.
 Optimal solutions = all subsequences of the shorter
given string that are also subsequences of the
longer given string and have the maximum length over
the space of viable solutions.
 Each subsequence s'' can be modeled as a binary
vector of length min(s,s') (v_i = 1 (0) =>
symbol i is (not) included in the subsequence);
hence, there are
O(2^{min(s,s')}) viable solutions for any
instance of LCS (note that this worst case only
occurs if each symbol in s and s' only occurs once).
 Sometimes, you can generate viable solutions
up front  this depends in part on your ingenuity.
 Example: The Minimum Spanning Tree problem
Minimum spanning tree (MST)
Input: An edgeweighted graph G = (V, E, w).
Output: All spanning trees T of G, i.e., trees
that connect all vertices in G, such that the sum
of the weights of the edges in T is minimized
over the solution space.
 Candidate solutions = all (V  1)sized subsets of
the edges of G.
 Viable solutions = all (V  1)sized subsets of the
edges of G that are spanning trees of G.
 Optimal solutions = all spanning trees of G that have
minimum summed edgeweight over the space of
viable solutions.
 By Cayley's Theorem, a graph G = (V, E) has
O(V^{V  2}) spanning trees (the worst case
here is when G is a complete graph); hence, there
are O(V^{V  2}) viable solutions for any
instance of MST.
 Sometimes even the set of viable solutions is
dauntingly large ...
 Can solve combinatorial optimization problems by
looking at all (candidate/viable) solution and
saving those of the optimal cost (which we can
determine on the fly by saving those solutions
with the best cost we've seen so far at any point
in the enumeration of all solutions).
 This is inherently inefficient given the exponential
sizes of the (candidate/viable) solution spaces
involved. Can we do better?
 We most certainly can. Consider MST; though the
set of viable solutions for each instance of
MST is potentially exponentially large, we can
solve all instances of MST in
loworder polynomial time! (i.e.,
combinatorics is not destiny)
 How good we can do algorithmwise depends on
how much of the (candidate/viable) solution
space our algorithm can ignore. Over the next
few lectures, we'll examine four techniques
for doing this whose applicability depend on
some fairly simple properties of problem
solutionspaces.
 Combinatorial SolutionSpace Trees (Sections 9.19.7, B&B)
 The most basic approach to solving combinatorial
optimization problems.
 In some cases, is the only known way to solve the
problem.
 Is also one of the few dependable ways to generate
all solutions for an instance of a combinatorial
optimization problem.
 As a first step, simplify generation of solutions
for a problem instance by using a combinatorial
solutionspace tree (CST).
In such a tree, internal nodes are partial
solutions and the full solutions labeling the
leaves comprise the solution space.
 Example: A CST for an instance of 0/1 Knapsack
in which U = 3.
 Can traverse such a tree and examine all of its
leaves using depthfirst search (DFS) or
breadthfirst search (BFS). Only those leaves
corresponding to viable solutions are important.
 Example: Viability conditions for
0/1 Knapsack, LCS, and MST.
 Do items in partial solution fit in
knapsack? (0/1 Knapsack)
 Is partial solution string a subsequence of
both given sequences? (LCS)
 Do edges in partial solution form a forest?
(MST)
 As a second step, decrease space requirements by
operating on an implicit CST, i.e., generate tree
nodes as necessary during traversal.
 Example: Algorithm for DFSbased traversal
of implicit CST (minimization version).
DFSI(i, sol)
if (i == n + 1)
if (viable (sol))
return(cost(sol))
else
return(INFINITY)
else
return(min(DFSI(i + 1, sol),
DFSI(i + 1, sol U item[i])))
 Initial call: DFSI(1, empty set)
 Note that n is the number of items in the
set in the instance; hence "i == n + 1" means
that you have reached a leaf in the CST.
 Example: Algorithm for BFSbased traversal
of implicit CST (minimization version).
BFSI()
Q = {(1, empty set)}
best = INFINITY
while not empty(Q)
(i, sol) = pop(Q)
if (i == n + 1)
if (viable(sol))
best = min(best, cost(sol))
else
push(Q,(i + 1, sol))
push(Q,(i + 1, sol U item[i]))
return(best)
 Modifications:
 To make the above work for maximization
problems, change min to max and INFINITY
to INFINITY.
 To obtain optimal solutions, the simplest way
is to run a second treetraversal that
takes the optimal cost produced previously
as a parameter and stores / prints all
viable solutions with that cost.
 This is all well and good; however, we are still
looking at every node in the tree, and as this
tree is of exponential size, our algorithm runs
in exponential time. Can we do better? Unfortunately,
we cannot in the worst case; however, we can sometimes
do much better in practice. This will be the topic
of our next lecture.
Tuesday, February 12 (Lecture #2)
[Section 15.315.4; Class Notes]
 Algorithm Design Techniques (Cont'd)
 Combinatorial SolutionSpace Trees (Sections 9.19.7, B&B)
(Cont'd)
 As a third step, where possible, use information
about partial solution viability and potential
optimality to terminate search of unfeasible
subtrees of the CST (dynamic pruning).
 Traditionally, DFS + dynamic pruning is known as
backtracking and BFS + dynamic pruning
is known as branch and bound.
 Backtracking typically used; however, if search
tree does not have finite depth, branch and
bound is preferable.
 Dynamic pruning works in CST because all
"full" candidate solutions that incorporate
a particular particular partial solution are
leaves in the subtree rooted at the node
corresponding to that partial solution; hence,
nonviability of a partial solution implies the
nonviability of all solutions in the subtree
rooted at the node corresponding to that
partial solution!
 Example: Potential optimality
conditions for 0/1 Knapsack, LCS, and MST.
 Does sum of values of items in partial
solution plus sum of values of all remaining
items that could be added exceed the
value of the best solution seen so far?
(0/1 Knapsack)
 Does the length of the partial solution
string plus the length of the string of
all remaining characters that could be
added exceed the length of the best
solution string seen so far? (LCS)
 Is the sum of the weights of the edges in
the partial solution less than the
cost of the best solution found so far?
(MST)
 Example: Algorithm for DFSbased traversal
of implicit CST + dynamic pruning (minimization version).
DFSIP(i, sol, best)
if (not viable(sol)) or (best < cost(sol))
return(INFINITY)
else if (i == n + 1)
best = min(best, cost(sol))
return(cost(sol))
else
return(min(DFSIP(i + 1, sol, best),
DFSIP(i + 1, sol U item[i], best)))
 Initial call: DFSIP(1, empty set, BEST) where
BEST is an object encoding the integer
INFINITY.
 Note that variable BEST is passed by reference,
e.g., it is a pointer to an integer; if it is
passed by value, the value of BEST is not
saved from any of the leafevaluations.
 Example: Algorithm for BFSbased traversal
of implicit CST + dynamic pruning (minimization version).
BFSIP()
Q = {(1, empty set)}
best = INFINITY
while not empty(Q)
(i, sol) = pop(Q)
if (viable(sol) and (cost(sol) < best)
if (i == n + 1)
best = min(best, cost(sol))
else
push(Q,(i + 1, sol))
push(Q,(i + 1, sol U item[i]))
return(best)
 Example: A Java implementation of a
DFSbased CST algorithm for solving the
Vertex Cover problem
[Problem Description,
VCST.java]
 Such tricks can drastically reduce actual running
time for CST traversal; however, all of these
algorithms are still asymptotically exponential time
in the worst case (you still might have to visit all
the nodes in the tree).
 The CST approach to solving combinatorial optimization
problems assumes nothing about the structure of
the solution space for an instance. If we did have
such knowledge, can we do better? That is the topic
of our next lecture.
There are other types of computation trees besides
CST. There are, for example, the trees associated
with recursive computations, in which nodes represent
individual recursive algorithm calls on subproblems of
smaller size. Such a recursivecall tree is also
called a recursive decomposition.
Characteristics of recursive decomposition:
 Can decompose instance of problem into smaller
instance of the same problem, i.e.,
subproblems.
 At any point in the computation, may be several
choices for decomposition.
Problems that are solvable by recursive decomposition
have the optimal substructure property,
i.e, an optimal solution for an instance of
the problem can be constructed using optimal
solutions for instances of that problem that are
of smaller size (subproblems)..
Our remaining algorithm design techniques will be
applicable if a problem's recursive decomposition
satisfies additional properties.
DivideandConquer (D&C)
 Applies if a problem has recursive decomposition in
which each subproblem occurs only once, i.e.,
the subproblems do not repeat / overlap.
 Will typically only be efficient if the depth of
recursion is logarithmically bounded, thus ensuring
that the total number of recursive calls is
polynomially bounded.
 Example: Merge sort
 Example: Binary search
 Example: Fast exponentian (a^n)
 Example: Strassen's matrix multiplication
algorithm (Section 28.2)
This is all fine and good; however, can we do anything if
we have a problem with a recursive decomposition in which
each subproblem occurs more than once? It turns out that
we can, and this will be the topic of our next lecture.
Dynamic Programming
 Applies if a problem has a recursive decomposition
in which the number of distinct subproblems is
bounded and can thus be organized in an
ndimensional table.
 Example:: Computing Fibonacci numbers
 Recursivecalls tree: 2^{n/2}  1 <= Tree Size
<= 2^{n}  1
 The problem here is that subproblems are
being repeated; perhaps the recursive algorithm
can keep track of what subproblems have been
solved by storing those values in a table and
look these up as necessary? An algorithm that
does this is called a memoized
algorithm.
 Memoized (recursive) algorithm:
InitFibT(n,FibT)
Allocate nelement table and assign to FibT
FibT[1] = FibT[2] = 1
for (i = 3; i <= n; i++)
FibT[i] = INFINITY
FibM(n, FibT)
if (FibT[n] == INFINITY)
FibT[n] = FibM(n  1, FibT) +
FibM(n  2, FibT)
return(FibT[n])
This table idea was pretty neat. In fact, do we
really need the recursion anymore? Let's just
fill out the table!
Dynamic programming (iterative) algorithm:
FibI(n)
if ((n == 1)  (n== 2))
return(1)
else
Allocate nelement table FibT
FibT[1] = FibT[2] = 1
for (i = 3; i <= n; i++)
FibT[i] = FibT[i  1] + FibT[i  2]
return(FibT[n])
If we are lucky, there are a polynomial number of
distinct subproblems. If we
are really lucky, we can use the recurrence to solve
these subproblems in a "bottom up" rather than a
"top down fashion", solving the smallest subproblems
first and solving progressively larger subproblems
until we solve the original problem instance.
Dynamic programming (DP) => tabledriven, bottomup
recursive decomposition algorithms!
The Dynamic Programming Cookbook:
 Step 1: Find a recurrence / recursive decomposition
for the problem of interest.
 This also (in the case of complex recurrences)
involves proving that this recurrence is
correct.
 This step is difficult, and very much an art 
one learns this by practice, and drawing on
a standard list of example recurrences.
 Step 2: Lay out the distinct subproblems in a table.
 Step 3: Fill in the basecase values in the table.
 Step 4: Run the recurrence "in reverse" / in a
bottomup fashion, using smaller solved subproblems
to solve larger subproblems, until the table is
filled in.
 At the end of this fillin process, the
cost of the optimal solution is now
in one of the table entries, e.g.,
FibT[n].
 Step 5: Use traceback from the optimalcost table
entry to reconstruct one or more optimal solutions
for the problem.
As noted in Step 1 above, the design of DP algorithms
is made easier by having a standard set of example
algorithms to draw on for inspiration. In the next
several lectures, we will present several such examples.
Thursday, February 14 (Lecture #3)
[Section 15.4]
 Algorithm Design Techniques (Cont'd)
 Dynamic Programming (Cont'd)
 Example: DP algorithm for Longest Common
Subsequence (LCS)
 Recursive decomposition: three cases.
 Recurrence (recursive + base cases)
 D(i,j) = length of longest common
subsequence of first i characters of
s and first j characters of s'.
 Example run: s = cbab and s' = abacab
 Matrix fillin (including backpointers)
for deriving length of longest common
subsequence.
 Rectangular (m + 1) x (n + 1) matrix
(where m and n are the lengths of
s and s', respectively);
fillin proceeds from cell (1,1)
rowwise, columnwise, or
antidiagonalwise.
 Fillin of an individual cell
involves consulting filledin
cells in the 3cell "overhang" to
left and behind of that cell.
 Traceback for deriving longest common
subsequences.
 DP algorithm (table fillin + traceback)
 Time complexity of matrix fillin: (# cells) x (#choices per cell) x
(max # subproblems per choice) = (mn) x (1) x
O(1) = 2mn = O(mn)
 Space complexity: # cells = (((m + 1) x (n + 1)) = O(mn)
 Deriving an arbitrary longest common subsequence
given a filledin matrix takes O(m + n) time;
however, enumerating all longest common
subsequences may require exponential time!
Tuesday, February 19
 Midterm break; no lecture
Tuesday, February 19
 Midterm Exam Notes
I've finished making up the upcoming midterm exam. This exam
will be closedbook and has a total of 60 marks (note that I
have tried to make the number of marks for a question roughly
equivalent to the number of minutes it should take you to do
it). The current layout is as follows:
 Recurrences (10 marks)
 Asymptotic worstcase time complexity (22 marks)
 Algorithm design techniques (28 marks)
Things that will not be covered are solution of recurrences
and detailed derivation of "raw" worstcase time complexity
functions; however,
all else is fair game. The questions on the first assignment
are guides to what I have in mind; you should also find the
questions on previous CS 3711 exams of some help:
 Midterm exam (Winter 2003) (7 pages:
PDF)
 Answers to midterm exam (Winter 2003) (8 pages:
PDF)
 Midterm exam (Winter 2004) (7 pages:
PDF)
 Answers to midterm exam (Winter 2004) (8 pages:
PDF)
 Midterm exam (Winter 2005) (7 pages:
PDF)
 Answers to midterm exam (Winter 2005) (7 pages:
PDF)
I hope the above helps, and I wish you all the best of luck
with this exam.
Thursday, February 21 (Lecture #4)
[Section 15.2; Class Notes]
 Algorithm Design Techniques (Cont'd)
 Dynamic Programming (Cont'd)
 Example: DP algorithm for Matrix Chain
Parenthesization (MCP)
 Review of 2matrix multiplication: O(n^3) time
(n = max matrix dimension)
 3matrix multiplication: Parenthesization of
matrix "chain" for 2matrix multiplication
can drastically affect the number of
individual element multiplications.
 Recurrence (recursive + base cases)
 m(i,j) = minimum number of element
multiplications required to multiply
matrices i through j in the given chain.
 Note that this is the first recurrence
we've seen that involves multiple
subproblem decomposition choices.
 DP algorithm
 Matrix fillin (including backpointers)
for deriving minimum number of
multiplications relative to optimal
matrix chain parenthesization.
subsequence.
 Raggedbottom pyramid / B1 bomber
shape matrix; fillin proceeds
from left to right in ascending
rows.
 Fillin of an individual cell
involves consulting filledin
cells in the "boomerang" hanging
off that cell.
 Backpointer matrix cells have value
k at which matrix sequence
i .. j split into matrix
subsequences i .. k and
(k + 1) .. j.
 Traceback for deriving optimal matrix chain
parenthesization.
 Time complexity of matrix fillin: (# cells) x (#choices per cell) x
(max # subproblems per choice) = (n(n  1)/2) x O(n) x
O(1) = O(n^3).
 Space complexity: # cells = (n(n  1)/2) = O(n^2)
 Example run: matrix chain is A_1 A_2 A_3 A_4,
where A_1 = 10 x 5, A_2 = 5 x 20, A_3 =
20 x 5, and A4 = 5 x 20. Thus, n = 4 and
dimension list p = (10,5,20,5,20)
Tuesday, February 26 (Lecture #5)
[Sections 15.3 and 16.1; Class Notes]
 Algorithm Design Techniques (Cont'd)
 Dynamic programming and divideandconquer algorithms
have enabled us to make many apparently difficult
problems solvable in loworder polynomial time. Can we
do still better? In certain cases, it seems that we can.

Consider binary search; it is a particularly interesting
example of
a D&C algorithm in which there is, at each point in the
computation, at most 1 choice and 1 subproblem to be
solved. In this case, the recursive computation collapses
to a path of recursive calls from the "root" problem to a
"leaf" subproblem.
 The subproblem structure for binary search is
unusually
simple, in that a choice can be made before
the subproblem is solved, i.e., the choice can be
made in a topdown, locally optimal (greedy) manner.
Compare this with divideandconquer and dynamic
programming algorithms, which solve subproblems in
a bottomup manner and make choices only after all
necessary subproblems have been solved.
Thursday, February 28
Tuesday, March 4 (Lecture #6)
[Section 16.1; Class Notes]
 Algorithm Design Techniques (Cont'd)
 Greedy Algorithms
 Example: The Activity Selection problem
 Problem statement
 DP algorithm
 Can we do better? In particular, do we have
to evaluate all subproblempairs induced by
a choice ak from S(i,j), or can
we get away with a single akchoice and
subproblem?
 It turns out that we can  pick the
activity am from S(i,j) with
the earliest finishing time  we are then
left with the subproblem S(m,j)!
(Theorem 16.1).
 This gets even better  note that instead of
solving all S(i,j) in the bottomup
manner
described above, we start with S(0,n+1)
and solve directly in a topdown manner!
 Greedy algorithm (iterative)
Thursday, March 6(Lecture #7)
[Sections 23.123.2; Class Notes]
 Algorithm Design Techniques (Cont'd)
 Greedy Algorithms (Cont'd)
 Example: The Minimum Spanning Tree problem
(Cont'd)
 DP algorithm.
 Based on problems of the form P[i] =
the cost of the minimum spanning forest
for edgeweighted graph G that has i edges
(note that what we ultimately want is
P[V  1]).
 We can imagine a recurrence for P[i] in
which we add all possible edges to
solutionforests for P[i  1] that connect
two formerly distinct components in the forest
and select those edges that result in
minimumcost forests on n edges. To do this,
we need to associate the solution
spanningforests
explicitly with P[i], i.e., we cannot
reconstruct them after matrix fillin by
traversing backpointers.
 The resulting recurrence has a double
minimization over solution spanningforests for
P[i  1] and edges that can be added to
these forests, respectively.
 Can we do better? In particular, do we have to
evaluate all of the subproblems induced by all edge
choices at each point, or can we get away with a
single edgechoice and subproblem?
 Consider the following very useful property of
minimum spanning forests: Given such a
forest for a graph G, each minimumweight edge
linking separate components in the forest must
be in some minimum spanning tree for G
(Theorem 23.1; see also Corollary 23.2).
Such an edge is said to be safe.
 What this means is that all we have to do is
choose a safe edge and evaluate the resulting
subproblem! This gets rid of the inner
minimization over edges in the recurrence;
moreover, as the
choice of a safe edge always leads to some
minimum spanning tree, we can also get rid of
the outer minimization over spanningforests.
 Generic MST algorithm (page 563):
GENERICMST(G = (V,E,w))
F = (V, {})
for (i = 1; i <= V  1; i++)
Find a safe e in E
F = (V, E' u {e})
return F
 Under appropriate selections of safe edges,
this generic algorithm underlies both
of the classic minimum spanning tree algorithms
considered below.
 Kruskal's algorithm
 Start with trivial forest of G that just includes the
vertices in V; add edges greedily, minimumweight
first, growing a minimum spanning forest that eventually
coalesces into a minimum spanning tree for G.
 Algorithm:
MSTKRUSKAL(G, w)
A = {}
for each vertex v in V do
MAKESET(v)
sort the edges in E in nondecreasing order by weight
for each edge in (u,v) taken in nondecreasing order by weight do
if FINDSET(u) <> FINDSET(v) then
A = A u {(u,v)}
UNION(u,v)
return(A)
 Note that this a direct implementation of
the generic MST algorithm above.
 Running time =
V(T(MAKESET)) + 2E(T(FINDSET)) + E(T(UNION)) + SORT(E)
= V(T(MAKESET)) + 2E(T(FINDSET)) + E(T(UNION)) + E log E
= V(T(MAKESET)) + 2E(T(FINDSET)) + E(T(UNION)) + E log V
 Prim's algorithm
 Start with a single vertex in G; add edges greedily,
minimumweight first, growing minimum spanning tree
for successively larger subsets of V until you
have a minimum spanning tree for G.
 Algorithm:
MSTPRIM(G,w,r)
for each u in V do
key[u] = INFTY
pi[u] = nil
key[r] = 0
Q = BUILD(V)
while Q is not empty do
u = EXTRACTMIN(Q)
for each v in adj[u] do
if v in Q and w(u,v) < key[v] then
pi[v] = u
key[v] = w(u,v)
 Note that in this algorithm (unlike
Kruskal's), the spanning forest has
exactly one nontrivial component with
edges at any point during processing.
 Running time =
T(BUILD) + V(T(EXTRACTMIN)) +
E(T(DECREASEKEY))
 Note that Kruskal's and Prim's algorithms are, in a
broad sense, converses of each other  by adding
minimumweight edges,
Kruskal's algorithm coalesces a (initially trivial)
spanning forest for the given graph G into a spanning tree
for G and Prim's algorithm extends spanning tree for
successively larger subgraphs of G until it has a spanning
tree for G.
 There is usually a quicker way of deriving a greedy
algorithm than developing and subsequently "pruning"
a dynamic programming algorithm (see Section 16.2);
however, the examples given here are useful as they
show the intimate relationship between dynamic
programming and greedy algorithms.
The relationship between CST, DP, DivideandConquer, and
Greedy algorithms:
Optimal
Substructure
AND
Independent
Subproblems?
/ \
/ YES \ NO
/ \
Greedy CST
Choice?
/ \
/ NO \ YES
/ \
Repeated Greedy
Subproblems?
/ \
/ YES \ NO
/ \
DP D&C
The differences that make related versions of a
problem amenable to
greedy algorithms instead of just dynamic
programming algorithms can be very subtle, and
do not appear to be (at this point in time,
anyway) either systematic or comprehensible.
Example: Versions of the Knapsack problem
that allow greedy and dynamic programming
algorithms.
Exploiting Data Structures
 The techniques we've seen so far use properties
of solution spaces to organize efficient searches
of these spaces; in many cases, we have lowered
time complexities from exponential to loworder
polynomial.
 Lower bound on time complexity of any algorithm for
a problem is typically linear (must at least read
all the input). To get as close as possible to this
bound, need to choose data structures that provide
best time complexities for operations required by
an algorithm.
 Example: Exploiting data structures to
solve the Minimum Spanning Tree problem
 Kruskal's algorithm
 Running time
= V(T(MAKESET)) + 2E(T(FINDSET)) + E(T(UNION)) + O(E log E)
= V(T(MAKESET)) + 2E(T(FINDSET)) + E(T(UNION)) + O(E log V^2)
= V(T(MAKESET)) + 2E(T(FINDSET)) + E(T(UNION)) + O(E log V)
 Running time relative to various data
structures for disjoint sets (see
here for more details about cited data structures):
Data Structure 
Time Complexity (Worst Case) 
MAKESET 
FINDSET 
UNION 
Kruskal's Algorithm 
List (naive) 
O(1) 
O(n) 
O(1) 
O(EV) 
List (repptr) 
O(1) 
O(1) 
O(n) 
O(EV) 
Forest (naive) 
O(1) 
O(n) 
O(1) 
O(EV) 
Forest (repptr) 
O(1) 
O(1) 
O(n) 
O(EV) 
Forest (UR + PC) 
O(1) 
O(1) 
O(1) 
O(E log V) 
 Prim's algorithm
 Running time =
T(BUILD) + VT(EXTRACTMIN)) +
E(T(DECREASEKEY))
 Running time relative to various data
structures for priority queues (see
here for more details about cited data structures):
Data Structure 
Time Complexity (Worst Case) 
BUILD 
EXTRACT MIN 
DECREASE KEY 
Prim's Algorithm 
Array (Unsorted) 
O(n) 
O(n) 
O(n) 
O(EV) 
Linked list (Unsorted) 
O(n) 
O(n) 
O(n) 
O(EV) 
Array (Sorted) 
O(n log n) 
O(n) 
O(n) 
O(EV) 
Linked list (Sorted) 
O(n log n) 
O(1) 
O(n) 
O(EV) 
Search tree 
O(n) 
O(n) 
O(n) 
O(EV) 
Balanced search tree 
O(n) 
O(log n) 
O(log n) 
O(E log V) 
Binary heap 
O(n) 
O(log n) 
O(log n) 
O(E log V) 
 There are several lessons implicit in the tables
above:
 To obtain the best overall set of running
times for a set of operations relative to
an abstract data type, a complex underlying
data structure may be required.
 When one is dealing with an algorithm that
only invokes a subset of the operations
relative to an abstract data type, the best
overall data structure implementing that
data type may not be appropriate  rather,
one looks for a data structure that gives the
best running times for the required subset of
operations.
An efficient algorithm is a collaboration
between an appropriate algorithm design technique
and one or more data structures whose operationsets
are optimally efficient for the subset of operations
required by the algorithm. Hence,
need good knowledge of both algorithm design
techniques and data structures to create efficient
algorithms.
An algorithm designer also needs a good knowledge of
the bestknown algorithms for standard problems.
After all, who wants to reinvent the wheel?
Such knowledge tends to be domainspecific. Let's
concentrate on the domain of graphs and standard
graph algorithms, starting with our next lecture.
Tuesday, March 11 (Lecture #8)
[Sections 22.2, 24.1, and 24.3; Class Notes]
 Algorithm Design Techniques (Cont'd)
 Example: Shortest Paths in Graphs
 Has many applications, especially if you also have
edgeweights, e.g., distances, costs.
 Two types of problems:
 Singlesource shortest paths
 Allpairs shortest paths
 Can further break down algorithms on edgeweighted
graphs based on whether
or not they detect negativeweight cycles. Such
cycles are problematic because they render
shortestpaths estimates meaningless, e.g.,
can make length of path arbitrarily short by
appropriate number of traversals around the cycle.
 Properties of shortest paths:
 Triangle inequality: d(s,v) <= d(s,u) + w(u,v)
 Shortest path has at most V  1 edges,
i.e., can eliminate negative, zero,
and positiveweight cycles from shortest paths.
 Shortest paths satisfy the optimal substructure
property, i.e., given a shortest path
from s to v and a vertex u on this path, the
subpaths s>u and u>v are also shortest paths;
this means that there are many nice algorithmic
possibilities, i.e., DP, D&C, Greedy.
We will exploit each of these properties to develop
different types of shortestpath algorithms over the
next two lectures.
 SingleSource Shortest Paths
 Can do this in unweighted graphs using general
breadthfirst search (BFS).
 Intuition behind BFS:
Exploration of shells of vertices at successively
larger distances from a selected point.
 Basic BFS algorithm:
BFS(G, s)
for each vertex u in G  {s} do
color[u] = white
color[s] = gray
Q = {}
ENQUEUE(Q, s)
while Q is not empty do
u = DEQUEUE(Q)
for each v in adj[u] do
if color[v] = white then
color[v] = gray
ENQUEUE(Q,v)
color[u] = black
 Interpretation of colors:
 black = fully explored (node + children)
 gray = partially explored (node only)
 white = unexplored
 Visualize as ink spreading from a central point
outwards along edges until it has reached all
vertices in a graph.
 Analysis of running time
 Running time = VO(1) + QO(1) + EO(1) + T_tot(nextadj))
= V + VO(1) + E + T_tot(nextadj))
= O(V + E + T_tot(nextadj))
 Adjacency list: O(V + E + E) = O(V + E) time
 Adjacency matrix: O(V + E + V^2) = O(V^2) time
 Though E <= V(V  1)/2 = O(V^2),
often keep Eterm in expressions to
show running time relative to sparse
graphs.
 Did not analyze algorithm in terms of
rigorouslyderived T(n) function 
worked less formally and directly in terms
of bigOh behavior of individual algorithm
components.
 Did not analyze algorithm by nested control
structure  had to reason about behavior
of algorithm as a whole to derive certain
quantities, e.g., total length of
queue over execution of algorithm.
 Full BFS algorithm (page 532):
BFS(G, s)
for each vertex u in G  {s} do
color[u] = white
** d[u] = INFTY
** pi[u] = NIL
color[s] = gray
** d[s] = 0
** pi[s] = nil
Q = {}
ENQUEUE(Q, s)
while Q is not empty do
u = DEQUEUE(Q)
for each v in adj[u] do
if color[v] = white then
color[v] = gray
** d[v] = d[u] + 1
** pi[v] = u
ENQUEUE(Q,v)
color[u] = black
 What are the pi and d arrays for?
 BFS defines a search tree based on all
vertices of G that is rooted at the start
vertex s; the piarray defines the
nodeparent relations in this tree.
 This search tree is structured such that
the length of the path from s to u in this
tree is the length of the shortest path
(in terms of # edges) between s and u
in G; the darray contains these
shortestpath length values.
 Intuition behind proof of correctness for
dvalues: If there were a
shorter path from s to v via some
vertex u, during exploration of children
of u, v would have previously been
colored gray!
 Note that Prim's algorithm for computing
minimum spanning trees is somewhat like BFS;
both are expanding a frontier outwards from
an initial vertex in the graph,
but while BFS expands this frontier uniformly
by distance from the start point, the expansion
by Prim is relative the the smallestweight
edge extending into the frontier.
 Can solve on edgeweighted graphs by applying
edgeexpansion and BFS; however, this yields an
exponential time algorithm. Can we do better?
 Singlesource (and indeed allsource) shortestpath
algorithms on weighted graphs use the Relax operation.
 Algorithm (pages 585586):
InitializeSingleSource(G, s)
for each vertex v in adj[v] do
d[v] = INFTY
pi[v] = nil
d[s] = 0
Relax(u, v, w)
if (d[v] > d[u] + w(u,v)) then
d[v] = d[u] + w(u,v)
pi[v] = u
 The relax operation is trivial; however,
sequences of relaxations can be quite powerful.
 Many of the algorithms we will consider for the
next 1 1/2
lectures will essentially differ only in the
the order in which edges are relaxed and the
number of times each edge is relaxed.
 Dijkstra's algorithm
 This algorithm essentially applies relaxations in
a systematic matter to grow a set of vertices with
known shortestpath distances outwards from the
source vertex to encompass the whole graph. In
particular, relaxations are applied to vertices
(or rather, the adjacencies of those vertices)
as they are added to this set and can be seen as
extending out from the frontier of this region into
the remainder of the graph.
 Algorithm:
Dijkstra(G, w, s)
InitializeSingleSource(G, s)
S = {}
Q = V[G]
while Q is not empty do
u = EXTRACTMIN(Q)
S = S u {u}
for each vertex v in adj[u] do
Relax(u, v, w)
 Analysis of running time
 Running time
= T(INITIALIZE) + VT(EXTRACTMIN) + ET(RELAX)
= T(INITIALIZE) + VT(EXTRACTMIN) + ET(DECREASEKEY)
 Runs in O(E log V) time relative to a
binary heap.
 Doesn't Dijkstra's algorithm look an awful lot
like Prim's algorithm for minimum
spanning trees? It should!
Try writing the code for the initialization and
relaxation procedures into Dijkstra's
algorithm, eliminating the Slines (which are
not being used), and then comparing with Prim's
algorithm  oddly enough, you'll see that
relaxation is a generalization of the keyvalue
adjustment done by Prim on lines 9 and 11,
e.g.,
DijkstraRewrite(G, w, s)
for each u in V do
d[u] = INFTY
pi[u] = nil
d[s] = 0
Q = V
while Q not empty do
u = EXTRACTMIN(Q)
for each v in adj[u] do
if d[u] + w(u,v) < d[v] then
d[v] = d[u] + w(u, v)
pi[v] = u
Dijkstra's algorithm cannot detect negative
cycles, and will produce
erroneous results if one or more such cycles
are present. Worse, this algorithm may fail
in the presence of negativeweight edges,
independent of whether these edges are part of
a negativeweight cycle.
Dijkstra's
algorithm is fast, but at the price of
restricted applicability. Can we do better?
The BellmanFord algorithm
 This algorithm essentially adopts the philosophy that
if you invoke relaxation often enough, all will be
well. Oddly enough, it turns out that if you relax
each edge in the graph V  1 times, the dvalues
associated with all vertices are guaranteed to settle
to the actual shortestdistance values. This
works because each round of relaxations
relaxes one edge further along a shortest path
and each shortest path has at most
V  1 edges.
 Algorithm:
BellmanFord(G, w, s)
InitializeSingleSource(G,s)
for i = 1 to V  1 do
for each edge (u,v) in E do
Relax(u, v, w)
for each edge (u,v) in E do
if d[v] > d[u] + w(u,v) then
return FALSE
return(TRUE)
Running time = O(VE)
This algorithm does (V  1)E relaxations, as compared to
the E relaxations done by Dijkstra's algorithm,
and hence runs much slower. However, it has the
advantage of being able to detect negativeweight
cycles.
 The intuition behind this is almost the same as
for the BellmanFord algorithm in general as
given above  in addition to propagating correct
shortest distances along a path, the
invoked relaxations propagate
the negative summed weights around negativeweight
cycles and dump these negative weights onto
regular paths, where the resulting screwup in the
relation between dvalues of adjacent vertices can
be detected by a simple scan of all edges
(lines 57 of the algorithm)
 Shouldn't Dijkstra's algorithm be able to detect
negativeweight cycles by the same argument? I
suspect not, as Dijkstra's algorithm probably does
not invoke enough relaxations
to guarantee that the influences
of negativeweight cycles will necessarily be
dumped onto all (or even any) paths 
however, I could be wrong in this.
Note that the running times given for both Dijkstra's
algorithm and the BellmanFord algorithm assume
that the input graph is represented as an adjacency
list  if the graph is instead represented as an
adjacency matrix, the running time of both
algorithms becomes O(V^3).
Thursday, March 13 (Lecture #9)
[Sections 25.125.2; Class Notes]
 Algorithm Design Techniques (Cont'd)
 Example: Shortest Paths in Graphs
 The FloydWarshall algorithm
 Running time = O(V^3)
Note that both of these algorithms are technically
operating on a 3D matrix of size O(V^3); however,
as we only need
to save adjacent 2D "slices" of this matrix,
we actually use O(V^2) space.
Note that the running times given for the three
algorithms above assume that the input graph is
represented as an adjacency matrix  if the graph
is instead represented as an adjacency list, the
running times of each algorithm increase by a
a multiplicative factor of V!
Thursday, April 3
 Final Exam Notes #1
Though Dr. Wang and myself haven't yet made up your final exam,
at the request of some of you, I am posting some of my
previous exams with answers so you can get an idea of the types
of questions I ask:
When I have a better idea what I will be putting on your exam,
I will post further notes.
Monday, April 14
 Final Exam Notes #2
Dr. Wang and myself have finished making up the final exam.
This exam
will be closedbook and has a total of 120 marks (note that we
have tried to make the number of marks for a question roughly
equivalent to the number of minutes it should take you to do
it). The current layout is as follows:
 Time complexity (24 marks)
 Algorithm design techniques / Graph algorithms
(26 marks)
 Algorithm design (35 marks)
 Proving polynomialtime intractability (35 marks)
All is fair game; this includes any algorithm we discussed in
class, e.g., the various shortest path algorithms. The
questions on the assignments are guides to what I have in mind;
you should also find the questions on my previous CS 3711 exams
(posted in Final Exam Notes #1 above) of some help.
We hope the above helps, and we wish you all the best of luck
with this exam and all of your other final exams.
References
Unless otherwise stated, all references above are to Cormen
et al. (2001).
 Brassard, G. and Bratley, P. (1996) Fundamentals of
Algorithmics. PrenticeHall; Englewood Cliffs, NJ.
[Abbreviated above as B&B]
Created: February 5, 2008
Last Modified: April 14, 2008