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.
  1. Outline an algorithm to determine if a DAG is a lattice.
  2. What is the asymptotoc order of its running time?
  3. 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.