In Project 1, we used compressed sparse row (CSR) format to store the adjacency matrix of a graph. Another data structure that could be used is an adjacency list (AL), an array of linked lists, one per vertex. The linked list for vertex v stores the neighbors of v (and corresponding edge weights, if any).

Following is a small example of a graph and its adjacency list. Note that the neighbor lists are not ordered by increasing column index.

In the following, assume that there are n vertices, m_head is an n-long array of Node pointers with each entry initialized to NULL, and the Node structure consists of an integer column index ci and a Node pointer m_next. Graphs are unweighted, so there is no need to store edge weights.

1. Describe in pseudocode the procedure for adding an edge to the graph. Your procedure should be correct whether or not some edges have already been added. Within each list, nodes do not need to be stored in order of increasing column index.
2. Compare the memory requirements for CSR and AL as functions of n, the number of vertices, and m, the number of edges.
3. For which data structure (CSR or AL) is insertion of an edge faster? Suppose we added the requirement that the linked lists for AL must be stored in order of increasing column index; which would be faster then? Explain your answers!
4. Give a technical reason why you might prefer one of the two data structures over the other. Justify your answer. There's no single right answer to this question.

0 2 4 143 04 4