For each problem, please identify on your paper which problem you are doing.
Homework 8
CRLS: 16.1.3, 16.3-2, 16.3-6 (double points), 16-2.
17.1-3, 17.2-2, 17-2.
Homework 9
"Lattices:" A DAG is a lattice if there is one vertex that can reach
every vertex and one vertex that can be reached by every vertex.
- Outline an algorithm to determine if a DAG is a lattice.
- What is the asymptotoc order of its running time?
- Describe how it works on the graph of 9 nodes with directed
(from, to) arcs
between the following nodes:
(1,2) (2,4) (3,4) (5,3) (6,3)
(7,3) (8,2) (9,1) (9,5) (9,6) (9,7) (9,8).
CRLS: 18.1-3, 18.2-1, 18.3-1,
22.1-7, 22.2-6, 22.2-8, 22.4-1, 22.4-3, 22.5-4.
Homework 10
"DGs:" Give a weighted directed graph and a source vertex such that
neither the depth-first search tree nor the breadth-first search
tree is a shortest-path tree, regardless of how the adjacency lists
are ordered.
"Shortest Cycle:"
This solution to the problem of finding the shortest cycle in an
undirected graph does not work because of a fundamental flaw
in the strategy, not a detail. What's wrong?
"When a back edge, say vw, is encountered during a depth-first
search, it forms a cycle with the tree edges from w to
v.
The length of the cycle is depth[v] - depth[w] +1, where
depth is the depth of the DFS tree. So, do a depth-first
search, keeping track of the depth of each vertex. Each time a back
edge is encountered, compute the cycle length and save it if it is
smaller than the shortest one previously seen."
"Hypersink:"Most algorithms that use graph adjacency matrices are
in OMEGA(n2).
BUT:
Let G = (V,E) be a digraph with n vertices. Vertex s is a
hypersink
if, for every v in V except s, there is an edge vs and no edge of the
form sv. Give an algorithm to determine whether G has a hypersink, G
being specified by its n by n adjacency matrix.
How many matrix entries are examined by your algorithm in the worst
case? An n2 algorithm is easy, but there is a linear
solution.
CLRS: 24.1-1, 24-3, 25.3-1, 25.3-4,
Homework 11: Max Flow and LP
CLRS 26.1-2, 26.1-8, 26.2-4, 26.3-1.
CLRS 29.1-2, 29.1-5, 29.2-1, 29.2-2, 29.3-2, 29.3-4, 29.5-5.
Homework 12: CG
CLRS 33.1-1, 33.1-2, 33.1-3, 33.1-4, 33.1-7, 33.2-4 (see 33.1-5),
33.2-7,
either 33-3 or 33-4.
Homework 13: FFT
CLRS 30.1-1, 30.1-7, 30.2-2, 30.2-3, 30.2-5, 30-1.