Last modified:
Problem | 01 | 02 | 03 | 04 | 05 | 07 | 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. 1172 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... (Why?)
Note: You should obtain improvements in at least three out of the four cases described in these exercises.
Hint: A d-ary heap is an array indexed starting at 0 where the parent of the element in position i, p(i), and the k-th child of the element in position i, childk(i), are defined as follows: