**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(n^{2}).
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 n^{2} 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.