CSE 373, Autumn 2002: Homework 7

Not to be turned in.

For all program or data structure design problems such as the two below you must provide pseudocode (see the manual) and an adequate explanation of the methods. It is often helpful to include small examples demonstrating the methods. Straight pseudocode with no additional documentation is not enough.  Your pseudocode can contain English if needed.
  1. Design an algorithm based on depth-first search to determine if a graph is bipartite and if it is not return an odd length cycle in the graph.  You algorithm should use the adjacency list representation of a graph.  Your algorithm should run in linear time.  Hint: there are two labels for marking 1 and 2.  A new vertex visited from a vertex marked 1 is marked 2 and a new vertex visited from a vertex marked 2 is marked 1.
  2. Some project planning applications use a labeled acyclic directed graphs to represent the jobs and job times on a project. A vertex in the graph represents a job and its label represents the time the job will take.  A directed edge from one vertex to another represents the fact the job represented by the first vertex must be completed before the job represented by the second vertex.  Assume we have a directed acyclic graph G =({1,2,...,n},E) with vertices labeled by non-negative integers c1, c2, ... ,cn . The label ci represents the time job i will take.  Assume futher that every vertex is reachable by some path  from vertex 1, vertex 1 has in-degree 0, vertex n is reachable by some path from every vertex, and n has out degree 0.  Vertex 1 represent the beginning of the project and vertex n represent the end of the project.  The length of a path from 1 to n is the sum of the labels on the vertices along the path.  Design an algorithm based on the topological sort algorithm to find the length of a longest path from 1 to n in the graph.  The length of the longest path represents how long the entire project will take.  Sometimes a longest path is called a critical path.  Your algorithm should use the adjacency list representation of a graph.  The labels can be stored in an additional array.  Your algorithm should run in linear time. Hint: ultimately you will need to compute the length of the longest path from 1 to every other vertex.  In the topological sort, when a vertex achieves in-degree 0, the length of the longest path from 1 to it should be known.