This assignment is an intriguing variation of Problem 6.45. Consider the problem of conv...

This assignment is an intriguing variation of Problem 6.45. Consider the problem of converting a directed graph g into its undirected counterpart g‘. The graph g‘ has an edge from vertex u to vertex v if and only if there is an edge from u to v or from v to u in the original graph g. The graph g is represented by its adjacency matrix G as follows. If N is the number of vertices in g, then G is an N × N matrix and its entries are all either 0 or 1. Suppose the vertices of g are named v₀, v₁, v₂, . . . , v_N−1. Then G[i][j ] is 1 if there is an edge from v_i to v_j and is 0 otherwise. Observe that the elements on the diagonal of an adjacency matrix are always 1 and that the adjacency matrix of an undirected graph is symmetric. This code can be written with a simple loop:

Your job is to devise a conversion routine that runs as fast as possible. As before, you will need to apply concepts you learned in Chapters 5 and 6 to come up with a good solution.