Note: This assignment cannot be turned in late. I will be handing out solutions to this assignment on the day it is due.
Last modified:
Problem | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | ... |
---|---|---|---|---|---|---|---|---|---|---|
Credit | RC | RC | RC | EC | RC | RC | NA | RC | RC | ... |
where "RC" is "regular credit", "EC" is "extra credit", and "NA" is "not attempted" (not applicable). Failure to do so will result in an arbitrary set of problems being graded for regular credit, no problems being graded for extra credit, and a five percent penalty assessment.
See pg. 1083 of CLRS for the definition of a multigraph.
Hint: When processing the adjacency list associated
with a vertex, you will want to keep track of which edges you have
seen so as not to duplicate any edges. Use an array to "mark" edges
(i.e., vertices) that you have seen and processed in the adjacency
list. In
Hint: Consider any matrix entry (i,j) where i does not equal j (i.e., consider any matrix entry which is not on the main diagonal). The value of entry (i,j) causes either i or j to be eliminated from contention. Use this fact to "walk" through the matrix in an efficient fashion, allowing you to find the sink (if it exists) in Theta(n) time.
Hint: See pg. 1083 of CLRS for the definition of a bipartite graph.