CS 163 / CS 265 Homework 1,  due Friday, January 18


1. Let G be a directed graph with 1000 vertices (numbered from 0 to 999) and 2500 edges. You may assume that a vertex number may be stored in two bytes, that a pointer from one object to another may be stored in four bytes, and that a collection or array of k objects may be stored in 4k bytes. You may also assume that a dictionary with k key-value pairs may be stored in 8k bytes.

(a) How many bytes would be required to store G, using the Goodrich-Tamassia representation discussed in class? In this representation, each vertex and edge is represented by an object, each vertex object has pointers to collections of its incoming and outgoing edges, each edge object has pointers to its two endpoint vertex objects, and the overall graph is represented by a graph object that has a pointer to a collection of its vertex objects.

(b) How many bytes would be required to store G, using the CLRS representation discussed in class? In this representation, the graph is represented by an array indexed by vertices, in which each array cell holds pointers to two singly-linked lists (one for the outgoing neighbors of the vertex and one for the incoming neighbors), and in which each list node stores one vertex number and one pointer to the next node in the list.

(c) How many bytes would be required to store G, using the van Rossum representation discussed in class? In this representation, the graph is represented by a dictionary in which the keys are the vertex numbers and the associated value for each key is a collection of the outgoing neighbors for that vertex.


2. With the same assumptions as in question 1, suppose that we wish to decorate each vertex of graph G by an 8-byte floating-point weight.

(a) Suppose that we use the Goodrich-Tamassia representation, that each vertex object has an additional pointer to its dictionary of decorations, and that each of these dictionaries contains one key-value pair with the key being the string "weight" and with value a pointer to an object storing the weight. How many additional bytes are required, over your answer from question (1), for these decorations?

(b) Suppose that we instead use the van Rossum representation, and implement the decoration by a single dictionary stored in a local variable called "weight", with one key in the dictionary for each vertex and with the associated value being a pointer to an object storing the weight. How many additional bytes are required, over your answer from question (1), for these decorations?


3. Suppose that a directed graph D has four different strongly connected components. We wish to add as few extra edges as possible (connecting pairs of vertices of D) so that the resulting augmented graph is strongly connected.

(a) What is the smallest number of extra edges that might be needed? Draw an example of a graph with four strongly connected components that requires this minimum number of edges.

(b) What is the largest number of extra edges that might be needed? Draw an example of a graph with four strongly connected components that requires this maximum number of edges.


4. Find an example of a graph, and a depth-first search ordering for that graph, with the property that there exist two vertices x and y that belong to the same strongly connected component but have different lowlink values from each other (as computed by Tarjan's strongly connected components algorithm). In your answer, show the graph, its depth-first search tree, and the lowlink values computed by the algorithm.


5*. (For CS 265 students only.) Devise a representation for (undecorated) graphs of the same size given in questions 1 and 2, that uses significantly fewer bytes than your answers to question 1. With your representation, it should still be possible to list the outgoing neighbors of a vertex, in constant time per neighbor, given as input the number of the vertex. Describe how to perform this listing process, and how many bytes your representation needs to represent the graph G. (Your representation does not need to be able to handle graphs of any larger size.