Sample solutions for HW6

• [23.1-6] Such a universal sink would need to have arcs into it from every other vertex and no arc into any other vertex. Checking an entry A[i,j] of the adjacency matrix, we eliminate the vertex i if A[i,j]=1, or the vertex j if A[i,j]=0. Assume that we have established an index i<=n such that no vertex <i, except possibly for j, is the universal sink. Examining A[i,j] allows to increment i to i+1 and either keeping j unchanged (when A[i,j]=1), or setting it to i (when A[i,j]=0). Once i exceeds n, we verify that j is the universal sink by scanning the j column. The first part takes n accesses and so does the second part.

• [23.2-7] Find a vertex v with the largest shortest path distance to any given vertex as the root of the tree. The distance between v and a vertex u the furthest away from v is the diameter of the tree. The algorithm requires two BFS traversals of the tree, ie., linear time.

• [25.1-1] Edges (u,x) and (u,v) can be switched with edges (s,x) and (x,v), respectively.

• [26.1-2] This represents the cheapest way of getting from i to i (disregarding a possible positively weighted self-loop).

• [26.1-3] It is the identity (neutral) element of matrix "multiplication" (according to the semiring (min,+)).

• [26.1-6] Set the entries of the pointer matrix P¹[i,j] to i if the edge (i,j) exists or i=j and to NIL otherwise. (Alternatively, initialize the diagonal entries of the matrix P° to the corresponding self-loops and others to NIL.) As the current minimum is discovered in line 7 of EXT-SHORT-PATHS, set the corresponding value of P'[i,j] to k.