Algorithm Design 549

Professor: Dr. Clark F. Olson (he/him), cfolson@[Link] [UW1 - 271B, (425) 352 -
5288]
EXTRA STUDY MATERIALS
Seattle Campus Resources
Youtube Videos

Run Times
Sorting Algorithms
1.​ Quicksort:
○​ Worst-case time O(n^2)
○​ Average-case time O(n log n)
○​ In-place, but not stable; usually fastest in “the real world”
2.​ Mergesort:
○​ Worst-case time O(n log n)
○​ Average-case time O(n log n)
○​ not in-place, but stable
3.​ Heapsort:
○​ Worst-case time O(n log n)
○​ Average-case time O(n log n)
○​ in-place, but not stable.

Shortest Paths
1.​ Dijkstra’s Algorithm:
○​ Running time: O(E log V + V log V)
○​ Precondition: All edge-weights non-negative.
○​ Stores distance from source to v in [Link] for every vertex v.
○​ Can also find path from source to v for a particular v in O(E) extra
time.
2.​ BFS-Shortest Path:
○​ Running time: O(V+E)
○​ Precondition: All edge weights are identical (or unweighted).
○​ Stores distance from source to v in [Link] for every vertex v.
○​ Can also find path from source to v for a particular v in O(E) extra
time.

1
Minimum Spanning Trees
1.​ Kruskal’s Algorithm:
○​ Running time: O(E log E)
○​ Returns list of edges in MST or a graph object containing just the
spanning tree.
2.​ Prim’s Algorithm:
○​ Running time: O(E + V log V)
○​ Returns list of edges in MST or a graph object containing just the
spanning tree.

Graph Search
1.​ [B/D]FS modification to find connected components.
○​ Running Time O(V+E)
○​ Precondition: undirected graph.
○​ Stores a component number in each vertex (given two vertices,
the numbers are the same if-and-only-if they are in the same
component)
2.​ [B/D]FS modification to find weakly connected components.
○​ Running Time O(V+E)
○​ Precondition: directed graph.
○​ Stores a component number in each vertex (given two vertices,
the numbers are the same if-and-only-if they are in the same
weakly connected component)
3.​ DFS modification to find strongly connected components.
○​ Running time: O(V+E)
○​ Precondition: directed graph.
○​ Stores a SCC number in each vertex (given two vertices, the
numbers are the same if-and-only if they are in the same strongly
connected component)
4.​ DFS modification to find meta-graph (a.k.a. “condensation graph”) of G.
○​ Running time: O(V+E) (of the original graph
○​ Precondition: directed graph.
○​ Given vertex u of G, can get access in constant time to
corresponding component vertex of condensation graph.
○​ Given component vertex of condensation graph, can get (in
constant time) a list of the vertices of G in that component.
5.​ DFS modification to find topological sort.
○​ Running time O(V+E)
○​ Precondition: directed acyclic graph.

2
 ○​ Stores the index in the ordering in each vertex (e.g. if u is the 3rd
vertex in the list, u has 3 stored inside) or returns a list of vertices
in order.

Data Structures
Dictionaries
1.​ AVL tree
Operation Worst-ca Average-Cas
se e
Insert O(log n) O(log n)
Find O(log n) O(log n)
Delete O(log n) O(log n)
2.​ ​
Hash Table
Operatio Worst-case Average-Cas
n e
Insert O(n) O(1)
Find O(n) O(1)
Delete O(n) O(1)
○​ If you can guarantee a constant number of collisions (for
example, because you know the keys in advance), all worst-case
times become O(1).

Lists
1.​ ArrayList
Operation Worst-case Average-Case
Insert at O(n) O(n)
front
Insert at end O(1) (amortized) O(1)
Delete O(n) O(n)
Find O(log n) if sorted, O(n) O(log n) if sorted, O(n)
otherwise otherwise
○​ In some use-cases, some of these operations can be sped up (for
example, if you use lazy deletion, in a sorted array, deletion can
be sped up)
2.​ Linked List

3
Operation Worst-case Average-Cas
e
Insert at O(1) O(1)
front
Insert at end O(1) O(1)
Delete O(n) O(n)
Find O(n) O(n)
Queue
Operation Running time (worst- and
average-case)
Enqueue O(1)
Peek O(1)
Dequeue O(1)
●​ Running times are amortized for array-based implementations.

Stack
Operation Running time (worst- and
average-case)
Push O(1)
Peek O(1)
Pop O(1)
●​ Running times are amortized for array-based implementations.

Priority Queue
Operation Running time (worst- and
average-case)
Insert O(log n)
Remove-Min O(log n)
Peek-Min O(1)
Decrease Priority O(log n)
Build-Heap (create heap with n O(n)
elements)

4
Book Work
Stable Matching - Gale Shapley
Chapter 1:
Two parties: Hospitals H and the students S.
Goal: A one to one matching of hospitals to students
Conditions:
●​ H prefers every one of its accepted applicants to S
OR
●​ S prefers the current situation over studying at hospital H
Perfect matching: Every student has a hospital and every hospital has one student
Stable matching: If it is perfect and there is no instability in the matches so that h prefers s to its
current match and s prefers h to its current match.

Questions:
●​ Is there a stable matching for every set of preference lists?
●​ Can we efficiently construct a stable matching if there is one?
○​ Yes, we use the gale-shapley algorithm

Algorithm:
While there is a hospital h who is free and has not proposed to every student
​ Choose such a hospital h
​ Let s be the highest-ranked student in h’s preference list to whom they have not
proposed
​ if(s is free)
​ ​ Make match (h,s)
​ Else
​ ​ If s prefers h’ to h (make this O(1) time by making a rank array of hospitals for
each student wherein the index corresponds to the proposers and the value is their rank.
​ ​ ​ h remains free
​ ​ Else
​ ​ ​ Make match (h,s)
​ ​ ​ h’ becomes free and is added to the queue of proposers

Midterm
Q1: Run the algorithm and circle the final matches
2
Q2: Worst case run time of Gale-Shapley? Answer: O(𝑛 )
2
If, instead of heap/stack for all next proposers we used a priority queue? Answer: O(𝑛 𝑙𝑜𝑔𝑛)

5
Q3: How do we process the proposals in O(1) time? : rank array of hospitals for each student
wherein the index corresponds to the proposers and the value is their rank.

Interval Scheduling
Interval scheduling and bipartite matching can both be encoded as special cases of the
independent set problem.
Run time: O(nlogn)

Chapter 1:
This is a greedy algorithm

Chapter 4:
First we sort the items by their finish times.
Starting at the first interval, which we always include.
Then we greedily pick the next finishing non overlapping interval.

THIS DOES NOT WORK FOR WEIGHTED INTERVAL SCHEDULING.

Because it does not take into account the weights of the intervals. Perhaps this method would
ignore a weighted interval that overlaps with the first finishing interval but would overall give a
higher value when finished.

Related Problem: Scheduling All intervals

AKA Interval Partitioning Problem

6
We will always need k resources as a rearrangement of the requests into k rows of
nonoverlapping intervals. We can also say that the depth of a set of intervals is the maximum
number that passes over a particular point. For the problem above the depth is 3.

First we sort by their start times

Let 𝐼1, 𝐼2, … 𝐼𝑛 denote the intervals in this order
For j = 1,2,3,..n
​ For each interval 𝐼𝑖 that precedes 𝐼𝑗 in sorted order and overlaps it
​ ​ Exclude the label of 𝐼𝑖 from consideration for 𝐼𝑗
EndFor
If there is any label from {1,2,...d} that has not been excluded then
​ Assign a nonexcluded label to 𝐼𝑗
Else
​ Leave 𝐼𝑗 unlabeled
End if
End for.

Related Problem: Scheduling to Minimize Lateness

Earliest deadline first.
Sort the jobs in increasing order of their deadlines and take on jobs that don't overlap.

Related Problem: Optimal Caching

Problem arises with memory hierarchy.
“Caching is storing copies of frequently used data in a temporary, faster storage”
The goal of this process is to do the least amount of “swaps” of data, or taking things out of the
cache storage to replace with something different. AKA a cache miss.
The farthest-in-future algorithm optimizes this.
When 𝑑𝑖 needs to be brought into the cache,
​ Evict the item that is needed the farthest into the future
IRL this is changed to least-recently used because we often don’t know the order of what
information we will need when.

Weighted Interval Scheduling

Chapter 1:
Dynamic Programming

7
Chapter 6:

Recursive algorithm
The optimal solution is the maximum value of intervals able to be scheduled

The idea behind the algorithm is that if interval n is an element of the optimal solution, then any
interval that overlaps with n is not an element of the optimal solution.
p(j), for an interval j, to be the largest index i<j such that intervals i and j are disjoint; i is the left
most interval that ends before j begins.
So the optimal solution is the value of n interval plus the optimal solution of {1,2….p(n)}
If n is not an element of the optimal solution we need the optimal solution of {1,2…n-1} all
intervals before n.
OPT(j) = max(𝑣𝑗 + OPT(p(j)), OPT(j-1))
n is an element of the optimal solution if and only if the first of the options is at least as good as
the second, and so on
𝑣𝑗+OPT(p(j)) ≥OPT(j-1)
Without optimization, the running time is exponential.
To optimize we memoize the recursion
Memoization: Saving values that have already been computed.

Bipartite Matching
Interval scheduling and bipartite matching can both be encoded as special cases of the
independent set problem.

Chapter 1:
Graph G = (V, E) is bipartite if node set V can be partitioned into sets X and Y in such a way that
every edge E has one end in X and the other in Y.
Perfect matching: If every node in G is able to be represented in the bipartite matching M.
Stable matching is a way of creating a bipartite graph.
But by the nature of arbitrary bipartite graphs is that not necessarily an edge E from every h ∈
H to every s ∈ S.
Also used to solve network flow problems.

8
Algorithm:
Augmentation: Inductively build up larger and larger matches, selectively back tracking along
the way.

Shortest Path : Dijkstra’s algorithm

Chapter 4:
Greedy Algorithm
AKA Minimum Cost Spanning trees

Dijkstra’s algorithm:
Let S be the set of explored nodes
​ For each u∈ S, we store a distance d(u)
Initially S = {s} and d(s) =0
While S≠V
​ Select a node v≠S with at least one edge from S for which d’(v)=𝑚𝑖𝑛𝑒=(𝑢,𝑣):𝑢∈𝑆d(u)+𝐿𝑒 is
as small as possible
​ Add v to S and define d(v) = d’(v)
endWhile

In plain English:

1.​ Set initial distances for all vertices: 0 for the source vertex, and infinity for all the
others.
2.​ Choose the unvisited vertex with the shortest distance from the start to be the
current vertex. So the algorithm will always start with the source as the current
vertex.

9
 3.​ For each of the current vertex's unvisited neighbor vertices, calculate the
distance from the source and update the distance if the new, calculated, distance
is lower.
4.​ We are now done with the current vertex, so we mark it as visited. A visited
vertex is not checked again.
5.​ Go back to step 2 to choose a new current vertex, and keep repeating these
steps until all vertices are visited.
6.​ In the end we are left with the shortest path from the source vertex to every other
vertex in the graph.

Doing it this way creates a running time of O(mn)

But there is a way to make it faster.
Priority queue of the minima values d’(v)=𝑚𝑖𝑛𝑒=(𝑢,𝑣):𝑢∈𝑆d(u)+𝐿𝑒 for each node.
To select the node v to add to the set S we need the ExtractMin operation.
To update a value of a node already on S, we need the changeKey operation.
This makes it run O(mlogn)

Extension: Minimum Spanning Tree

Greedy Algorithm
Three greedy algorithms to solve this problem

Kruskal’s algorithm
Start at any edge, successively insert edge from E in order of increasing cost. Insert an edge as
long as e does not create a cycle.

Prim’s Algorithm
Start at root node s and build the tree outward by adding the node that can be reached as
cheaply as possible.

Reverse-Delete or Backwards Kruskal’s Algorithm

Start with a full graph and delete edges in order of decreasing cost as long as deleting the edge
will not disconnect the graph we already have.

Clustering

Chapter 4:
Creating a cluster of objects k, aka a k-clustering, from a set of objects U with maximum space
between the clusters.

10
Single-link clustering: When you add an edge between two distinct clusters to combine them
into one cluster.
To do this we simply use Kruskal’s algorithm but stopping before it adds k-1 edges.

Huffman Codes and Data Compression

Think of Morse code and how it can be represented using a binary tree.

Prefix codes: One “letter” or node is a prefix to another node.

The question is how to build an optimal tree of prefix codes for a set of data?

Huffman Algorithm
To construct a prefix code for an alphabet S, with given frequencies:
​ If S has two letters then,
​ ​ Encode one letter using 0 and the other using 1.
​ Else
​ ​ Let y* and z* be the two lowest frequency letters
​ ​ Form a new alphabet S’ by deleting y* and z* and
​ ​ ​ Replacing them with a new letter w of frequency 𝑓𝑦*+ 𝑓𝑧*
​ ​ Recursively construct a prefix code for/ S’ with tree T’
​ ​ Define a prefix code for S as follows:
​ ​ ​ Start with T’
​ ​ ​ Take the leaf labeled w and add two children below it labeled y* and z*.
​ End if
This algorithm creates the Huffman Code for that alphabet or data set.

2
Running time: O(𝑘 ) without optimization using heaps
Running time optimization using heaps: O(klogk)

11
Minimum Cost Arborescenses
This is the minimum spanning tree for a directed graph.
For each node v≠r
​ Let 𝑦𝑣 be the minimum cost of an edge entering node v
​ Modify the costs of all edges e entering v to 𝑐'𝑒 = 𝑐𝑒 - 𝑦𝑣
Choose one 0-cost edge entering each v≠r, obtaining a set F*
If F* forms an arborescence, then return it
Else, there is a directed cycle C⊆F*
​ Contract C to a single supernode, yielding a graph G’=(V’, E’)
​ Recursively find an optimal arborescence (V’, F’) in G’ with costs {𝑐'𝑒}
​ Extend (V’, F’) to an arborescence (V,F) in G by adding all but one edge of C

Shortest Path In Weighted Graph

Decentralized Dijkstra’s algorithm because we can have negative cost edges.
This algorithm is called the Bellman-Ford Algorithm.
It states first that : If graph G has no negative cycles, then there is a shortest path from s to t
that is simple (i.e. does not repeat nodes) and hence has at most n-1 edges.
This leads to:
OPT(i,v) = min(OPT(i-1,v), min(OPT(i-1,w)+𝑐𝑣𝑤))

3
Running time: O(𝑛 )
Optimized: O(mn)

Optimize by only looking at each edge leaving a node.

Independent Set
No efficient algorithm is known for finding the largest independent set. It is NP-complete.
You can efficiently find if a graph is an independent set.

Chapter 1:
Graph G = (V,E) with subset S ⊆ V is an independent set if no two nodes in S are connected
by an edge.
Interval scheduling and bipartite matching can both be encoded as special cases of the
independent set problem.

12
Competitive Facility Location
Finding a large solution is hard, but checking a proposed large solution is easy.

Chapter 1:
Competitive Facility location can be defined as a game in which two players alternatively select
nodes, with no neighbors selected, with assigned values. A player wins if their selected nodes
add to a target value B.

The Competitive Facility Location can be proved PSPACE-complete using the QSAT.

Mergesort Algorithm
Chapter 5:
Divide and conquer

Sort a given list of numbers by first dividing them into two equal halves, sorting each half
separately by recursion, and then combining the results.

𝑛
Recurrence relation: 𝑇(𝑛) ≤ 2𝑇( 2 ) + 𝑐𝑛 when n > 2 and T(2) ≤ c.
𝑛
More informally written as: 𝑇(𝑛) ≤ 2𝑇( 2 ) + O(n)

Counting Inversions
Using the Mergesort algorithm we will count inversions to solve collaborative filtering to match
preferences, or meta-search tools.

We do this by counting the inversions.

A sequence of 2,4,1,3,5 for instance has 3 inversions,. (2,1) (4,1) and (4,3).
Algorithm:
Sort-and-count
If the list has one element, then
There are no inversions
Else

13
 Divide the list into two halves:
A contains the first half of elements
B contains the second half of elements
(𝑟𝑎, A) = Sort-and-Count(A)
(𝑟𝑎, B) = Sort-and-Count(B)
(𝑟 , L) = Merge-and-Count(A,B)
EndIf
Return r = 𝑟𝑎+𝑟𝑏 + r and the sorted list L

Merge-and-count
​ Maintain a Current pointer into each list, initialized to point to the front elements
​ Maintain a variable Count for the number of inversions, initialized to 0
​ While both lists are nonempty:
​ ​ Let 𝑎𝑖 and 𝑏𝑗 be the elements pointed to by the Current pointer
​ ​ Append the smaller of these two to the output list
​ ​ If 𝑏𝑗 is the smaller element, then
​ ​ ​ Increment Count by the number of elements remaining in A
​ ​ End If
​ ​ Advance the Current pointer in the list from which the smaller element was ​
​ ​ selected
​ End While

Running time: O(nlogn)

Closest Pair of Points

Youtube Video pictures are from
Start by sorting the points by their x coordinates and then by their y coordinates to create two
different lists.
We then recursively divide the points in half and find the closest pair of points.

14
15
Integer Multiplication
Ya know, multiplying two n-digit numbers.
Recursive-Multiply(x,y)
𝑛/2
​ Write x = 𝑥1 × 2 + 𝑥0
𝑛/2
​ y = 𝑦1 × 2 + 𝑦0
​ Compute 𝑥1 + 𝑥0 and 𝑦1 + 𝑦0
​ p= recursive-multiply(𝑥1 + 𝑥0 , 𝑦1 + 𝑦0)
​ 𝑥1 𝑦1 = recursive-multiply(𝑥1, 𝑦1 )
𝑥0 𝑦0 = recursive-multiply(𝑥0, 𝑦0 )
𝑛 𝑛/2
Return 𝑥1 𝑦1 × 2 + (𝑝 − 𝑥1 𝑦1 − 𝑥0 𝑦0) × 2 + 𝑥0 𝑦0

𝑙𝑜𝑔23
Running time: O(𝑛 )

Subset sums and Knapsack

Chapter 6:
A dynamic programming problem where each node or item has a value and a “weight”. We want
to maximize the value and stay below the weight.

Greedy algorithms won’t work because of the process of addition. Ex: three items of weight
𝑤 𝑤 𝑤
{ 2
+1, 2
, 2
} . Picking the first item will be the least amount of weight, but the lowest value we
could get. And sorting won’t solve that problem.

The best way to do this is to consider that we have n items. Like scheduling we need to know if
𝑛𝑖 is a part of the optimal solution. To do this we need to get the summation of values if we
include 𝑛𝑖 and if we do not include it, that way we can choose the max value.

OPT(i,w) = max ∑𝑤𝑗

𝑗ϵ𝑠
AKA, if 𝑛𝑖 is not an element of the optimal solution then get the optimal solution of all elements
not including 𝑛𝑖 OPT(n,w) = OPT(n-1, w).
If 𝑛𝑖 IS an element of the optimal solution then get the optimal solution of all elements
including 𝑛𝑖’s weight OPT(n,w) = 𝑤𝑛OPT(n-1, w-𝑤𝑛).

16
Graphs
Chapter 3:

This is a graph. Wow!

Graphs: A way of encoding pairwise relationships among a set of objects.
Graphs are a collection of V nodes(or vertex) and E edges. G=(V,E).
Directed Graph: Edges within a directed graph have directions between nodes. AKA each
edge has an ordered pair (u,v) where u is the head and v is the tail of the edge. You can go from
u to v but NOT v to u. It is strongly connected if for every two nodes u and v, there is a path
from u to v and a path from v to u.
If a directed graph has no cycles we call it a directed acyclic graph (DAG). If graph G has
topographical ordering, then it is a DAG.

Midterm:
Q1: Recall the algorithm for topological sorting a graph
To compute a topological ordering of G:
​ Find a node v with no incoming edges and order it first.
​ Delete node v from G.
​ Recursively compute a topological ordering of G-{v} and append this order after v.
a)​ The algorithm will fail if a cycle exists. At what point will it fail?
b)​ There are m edges and n nodes in the graph. After the algorithm has failed can you
detect on in O(n) time? Describe the algorithm to do so.
Undirected Graph: Edges have no direction, you can go from u to v or v to u. It is connected if
for every pair of nodes u and v, there is a path from u to v. It is a tree if it does not contain a
cycle(every tree has exactly n-1 edges).
Types of paths in UNdirected graph:
●​ Simple: All vertices are distinct from each other.
●​ Cycle: Sequence of nodes “cycles” back to where it began.
Examples of ways to use paths:
●​ Transportation networks
●​ Communication networks
●​ Information networks

17
 ●​ Social networks
●​ Dependency Networks

Breadth-First Search
O(n)
Simplest algorithm for s-t connectivity.
Explore outward from s in all possible directions adding nodes one “layer” at a time.
BFS is not only determining the nodes that S can reach but also computing the shortest path to
them. For each layer j>=1 layer Lj consists of all nodes at distance exactly j from s.
Used to test bipartiteness - If a graph is bipartite then it can not contain an odd cycle.

Depth-First Search
Explores the graph by going as deeply as possible and only retreating when necessary. Start
from s and go to the first edge leading out to node v, continue until you reach a dead end, then
backtrack.

Greedy Algorithms
Chapter 4:
An algorithm is greedy if it builds up a solution in small steps, choosing a decision at each step
myopically to optimize some underlying criterion.
To prove a greedy algorithm is the optimal solution for a problem one must prove that it “stays
ahead” of any other algorithm at each step. OR use an exchange argument. To build an
exchange argument you consider any possible solution to the problem and gradually transform
it into the solution found by the greedy algorithm.

Problems optimized by greedy algorithms

Shortest paths in a graph

18
Minimum spanning tree
Huffman Codes
Interval Scheduling
Minimizing Lateness
Optimal Caching
Minimum Cost Arborescences

Divide and conquer

Chapter 5:
Algorithmic technique to divide the problem into parts, solve them recursively, and combine the
solutions together to get an overall solution.

Recurrence relation bounds the running time recursively in terms of the running time on smaller
instances. This is solved with the master theorem.

Ways to solve a recurrence to find the running time

“Unroll” the solution
●​ Analyze the first few levels
●​ Identify a pattern
●​ Sum over all of the levels of recursion
Substitute a solution and prove it works(AKA, guess and check)
●​ Prove by induction

Dynamic programming
Chapter 6:
Implicitly exploring the space of all possible solutions by carefully decomposing things into a
series of sub problems

19
We use it for:
Weighted Interval Scheduling
The most common way to do this is to add all of the elements together starting with value n,
assuming n is part of the solution we now need the value of all elements in the optimal solution
not including n. If n is not in the optimal solution we just need the value of all other elements in
the optimal solution.

Network Flow
A flow network is a directed graph G = (V, E) with the following features:
●​ Associated with each edge e is a capacity, which is a nonnegative number that we
denote c_e
●​ There is a single source node s ∈ V
●​ There is a single sink node t ∈ V.

Each “cut” of the graph puts a bound on the maximum possible flow value.
A minimum cut is the cut with the minimum possible capacity among all such partitions.
The value of the maximum flow equals the capacity of the minimum cut

Given a flow network G, and a flow F on G, we define the residual graph as:
●​ The node set of G_f is the same as that of G
●​ For each edge e = (u,v) of G on which f(e) < c_e there are c_e - f(e) leftover units of
capacity on which we could try pushing flow forward.

In short terms: The residual graph is the version of the network that shows what capacity is left
and what flow you can send backward to improve the overall flow.
An augmenting path is a simple s↝t path in the residual graph

No matter which cut you look at, the net flow crossing it equals the value of the flow. Therefore:
The maximum possible flow is limited by the smallest cut capacity.

●​ When looking at cut capacity: sum total edges going from source cut to sink cut

The following three conditions are equivalent for any flow f :

1.​ There exists a cut (A, B) such that cap(A, B) = val(f).
2.​ f is a max flow.
3.​ There is no augmenting path with respect to f. (ford fulkerson terminates)

Ford-Fulkerson terminates after at most [value of max flow] <= nC augmenting paths (c is the
capacity of the cut)

Capacity scaling algorithm: ​

Same as FF but instead of sending flow along any augmenting path (which might push a tiny

20
amount each time), we only use paths that can carry a large chunk of flow first, and we scale
down the minimum acceptable capacity for augmenting paths over time.

Level graph = BFS-layered version of the residual graph that keeps only forward edges to the
next layer and positive capacity.
Purpose = Guide Dinitz's algorithm to find blocking flows along shortest augmenting
paths, improving efficiency.

Dinitz algorithm
●​ Phase 1 — Build Level Graph
○​ Run BFS from source s
○​ Label each node with level distance
○​ If sink is NOT reached → we are done (Max Flow achieved)
●​ Phase 2 — Find a Blocking Flow
○​ Use DFS to find augmenting paths in level graph
○​ Push flow along each path
○​ Remove edges that fill up (capacity becomes 0)
○​ Continue until no more augmenting paths exist in level graph
Loop back to create a new Level Graph (because now structure of residual graph changed)
Keep going until BFS cannot reach the sink
This video has a good example and explanation of Dinitz

Extensions of max flow

●​ Multiple Sources & Multiple Sinks
○​ Solution:
Add a super-source s → connects to all original sources (infinite capacity)
Add a super-sink t → all original sinks connect into it (infinite capacity)
Then just run normal max flow.
●​ Circulation with Supplies and Demands
○​ Solution:
Add super-source s and super-sink t
Edges connect from s to supply nodes & from demand nodes to t
Run max flow algorithm
○​ If we solve the max flow on this, and we find out that the max
flow value is equal to the sum of the capacities of the edges out of the source,
and equal to the sum of the capacities of the edges into the sink, then it is a
circulation with the appropriate flow,
●​ Lower Bounds on Edge Flow
○​ Solution: Push the lower bound first → subtract ℓ(e)
Adjust node demands to reflect that initial flow
Reduce to circulation with demands, solve using max-flow

21
 ○​ If that circulation exists then theres a valid solution accounting for lower bounds.
●​ Undirected Graphs
○​ Solution: Replace each undirected edge with two directed antiparallel edges

Computational Tractability
Chapter 2:
AKA the efficiency of an algorithm.
If a program can be completed within polynomial time given any amount of n input we say it is
𝑑
efficient. c𝑁 for c>0 and d>0.
O: Big O notation is the upper bound of how long an algorithm takes to complete.
𝝮: Big omega notation is the lower bound of how short an algorithm takes.
𝚹: Big theta notation is the tight bounds of how much time an algorithm takes. If something is
both BigO(x) and Big𝝮(x), then it is Big𝚹(x).

To define the time complexity of an algorithm we count the number of steps it takes to complete
for each n input.
One “step” is equivalent to assigning a variable, looking up an entry in an array, following a
pointer, or performing an arithmetic operation on a fixed size integer.

22
Properties of Asymptotic Growth Rates

Transitivity: If a function f is O(g) and function g is O(h), then f is also O(h). However the more
correct definition is that function f is O(g) because it would be a tighter bound.

Sums of functions: If function f=O(h) and g=O(h), then f+g=O(h).

NP-Complete
No efficient algorithm is known for any of these problems but they are all equivalent. Meaning a
solution to any one of them would imply, in a precise sense, there is a solution to all of them.

PSpace-Complete
Strictly harder than NP-complete problems.

Problems
GitHub - mathiasuy/Soluciones-Klenberg: Algorithm Design (Kleinberg Tardos 2005) - Solutions

Chapter 6:

4.
Suppose you’re running a lightweight consulting business - just you, two associates,
and some rented equipment. Your clients are distributed between the east coast and the
west coast, and this leads to the following question.
​ Each month, you can either run your business from an office in New York or from
an office in San Francisco. In month i, you’ll incur an operating cost of 𝑁𝑖, if you run the

23
business out of NY; you’ll incur an operating cost of 𝑆𝑖 if you run the business out of SF.
(It depends on the distribution of client demands for that month).
​ However, if you run the business out of one city in month i, and then out of the
other city in i+1, then you will incur a fixed moving cost of M to switch base offices.
​ Given a sequence of n months, a plan is a sequence of n locations - each one
equal to either NY or SF - such that the ith location indicates the city in which you will be
based in on the ith month. The cost of a plan is the sum of the operating cost for each of
the n months, plus a moving cost of M for each time you switch cities. The plan can
begin in either city.
​ The problem. Given a value for the moving cost M, and sequences of operating
costs 𝑁1,...𝑁𝑛 and 𝑆1,...𝑆𝑛, find a plan of minimum cost. (Such a plan will be called
optimal)
​ Example. Suppose n=4, M=10, and the operating costs are given by the
following table.

Month 1 Month 2 Month 3 Month 4

NY 1 3 20 30

SF 50 20 2 4

​ The plan of minimum cost would be the sequence of locations [NY, NY, SF, SF],
with a total cost of 1+3+2+4+10 = 20, where the final term of 10 arises because you
change locations once.
a)​ Show that the following algorithm does not correctly solve this problem, by giving
an instance on which it does not return the correct answer.
for i = 1 to n
​ If 𝑁𝑖 < 𝑆𝑖 then
Output “NY in Month i”
Else
Output “SF” in Month i”
​ End

​ In your example, sway what the correct answer is and also what the algorithm
above finds.

b)​ Give an example of an instance in which every optimal plan must move (i.e.
change locations) at least 3 times.
Provide a brief explanation, saying why your example has this property.

24
 c)​ Give an efficient algorithm that takes values for n, M, and sequences of operating
costs 𝑁1,...𝑁𝑛 and 𝑆1,...𝑆𝑛, and returns the cost of an optimal plan.

5.

As some of you know well, and others of you may be interested to learn, a number of
languages (including Chinese and Japanese) are written without spaces between the
words. Consequently, software that works with text written in these languages must
address the word segmentation problem - inferring likely boundaries between
consecutive words in the text. If English were written without spaces the analogous
problem would consist of taking a string like “meetateight” and deciding that the best
segmentation is “meet at eight” (and not “me et at eight” or “meet ate ight” or any
humble number of even less plausible alternatives). How could we automate the
process?
​ A simple approach that is at least reasonably effective is to find a segmentation
that simply maximizes the cumulative “quality” of its individual constituent words. Thus,
suppose you are given a black box that, for any string of letters x=𝑥1𝑥2…𝑥𝑘, will return a
number quantity(x). This number can be either positive or negative; larger numbers
correspond to more plausible English words.
​ Given a long strong of letters y= 𝑦1𝑦2…𝑦𝑘 a segmentation of y is a partition of its
letters into a contiguous block of letters; each block corresponds to a word in the
segmentation. The total quality of a segmentation is determined by adding up the
qualities of each of its blocks. (So we’d get the right answer above provided that
quality(meet) + quality(at) + quality(eight) was greater than the total quality of any other
segmentation of the string.)
​ Give an efficient algorithm that takes a string y and computer a segmentation of
maximum total quality. (You can treat a single call to the black box of computing
quality(x) as a single computational step).

13.
​ The problem of searching for cycles in graphs arises naturally in financial trading
applications. Consider a firm that trades shares in n difference companies. For each
pair i≠j, they maintain a trade ratio 𝑟𝑖𝑗, meaning that one share of i trades for 𝑟𝑖𝑗 of j.
2
Here we allow the rate r to be fractional; that is, 𝑟𝑖𝑗 = 3
means that you can trade three
shares of i to get two shares of j.
​ A trading cycle for a sequence of shares 𝑖1, 𝑖2,...𝑖𝑘 consists of successively
trading shares in company 𝑖1 for shares in company 𝑖2, then shares in company 𝑖2 for

25
shares 𝑖3, and so on, finally trading shares in 𝑖𝑘 back to shares in company 𝑖1. After such
a sequence of trades, one ends up with shares in the same company 𝑖1 that one starts
with. Trading around a cycle is usually a bad idea, as you tend to end up with fewer
shares than you started with. But occasionally, for short periods of time, there are
opportunities to increase shares. We will call such a cycle an opportunity cycle, if
trading along the cycle increases the number of shares. This happens exactly if the
product of the ratios along the cycle is above 1. In analyzing the state of the market, a
firm engaged in trading would like to know if there are any opportunity cycles.
​ Give a polynomial-time algorithm that finds such an opportunity cycle, if one
exists.

Chapter 7:

2.
Figure 7.26 shows a flow network on which an s-t flow has been computed. The capacity of
each edge appears as a label next to the edge, and the numbers in boxes give the amount of
flow sent on each edge.
a)​ What is the value of this flow? Is this a maximum (s,t) flow in this graph?
b)​ Find a minimum s-t cut in the flow network pictured in figure 7.26, and also say what its
capacity is.

26
3.
Figure 7.27 shows a flow network on which an s-t flow has been computed. The capacity of
each edge appears as a label next to the edge and the numbers in boxes give the amount of
flow sent on each edge.
a)​ What is the value of this flow? Is this a maximum (s,t) flow in this graph?
b)​ Find a minimum s-t cut in the flow network pictured in figure 7.26, and also say what its
capacity is.

4.
Decide whether you think the following statement is true or false. If it is true, give a short
explanation. If it is false, give a counterexample.

​ Let G be an arbitrary flow network, with a source s, a sink t, and a positive integer
capacity 𝑐𝑒 on every edge e. If f is a maximum s-t flow in G, then f saturates every edge out of s
with flow (i.e., for all edges e out of s, we have f(e) = 𝑐𝑒).

5.
​ Decide whether you think the following statement is true or false. If it is true, give a short
explanation. If it is false, give a counterexample.

​ Let G be an arbitrary flow network, with a source s, a sink t, and a positive integer
capacity 𝑐𝑒 on every edge e; and let (A,B) be a minimum s-t cut with respect to these capacities

27
{𝑐𝑒 : e ∈ E}. Now suppose we add 1 to every capacity; then {A,B} is still a minimum s-t cut with
respect to these new capacities {1+𝑐𝑒 : e ∈ E}.

Chapter 8:

1.
For each of the two questions below, decide whether the answer is (i) “Yes”, (ii) “No”, or (iii)
“Unknown, because it would resolve the question of whether p = np”. Give a brief explanation of
your answer.
a)​ Let’s define the decision version of the interval scheduling problem from chapter 4 as
follows: Given a collection of intervals on a time-time, and a bound K, does the collection
contain a subset of nonoverlapping intervals of at least K?
​ Question: Is it the case that Interval Scheduling ≤𝑝 Vertex Cover?
b)​ Question: Is it the case that Independent Set ≤𝑝Interval Scheduling?

2 (reduce Independent Set to Diverse Subset).

A store trying to analyze the behavior of its customers will often maintain a two-dimensional
array A, where the rows correspond to its customers and the column correspond the the
products it sells. The entry A[i,j] specifies the quantity of product j that has been purchased by
customer i.
​ Here’s a tiny example of such an array A.

Liquid Detergent Beer Diapers Cat litter

Raj 0 6 0 3

Alanis 2 3 0 0

Chelsea 0 0 0 7

​ One thing that a store might want to do with this data is the following. Let us say that a
subset S of the customers is diverse if no two of the customers in S have ever bought the same
product (i.e., for each product, at most one of the customers in S has ever bought it). A diverse
set of customers can be useful, for example, as a target pool for market research.
​ We can now define the Diverse Subset Problem as follows: Given an m X n array A as
defined above, and a number k ≤ m, is there a subset of at least k of customers that is diverse?
​ Show that Diverse Subset is NP-complete.​

28