For the following problems, design an algorithm (write out either steps or pseudocode by hand), analyze the maximum number of steps it take to run in terms of n (the number of nodes of the graph) as in Section 1.3.3 of the notes, code up the algorithm and test it out to make sure it works properly. Unless stated otherwise, assume we are working with graphs represented by adjacency matrices.

Problem 1: Make a program is_adjacent(A,i,j) that returns True if there is an edge from vertex i to vertex j, and False otherwise.

Problem 2: Make a program AL_is_adjacent(G,u,v) that, given a graph G as an adjacency list, returns True if there is an edge from vertex i to vertex j. Note to test if an object x is an element of a set S, you can use the code x in S. For the analysis, assume that the command x in S takes at most |S| steps to carry out. (I believe the Python implementation is much more efficient than this, but this is the naive bound.)

Problem 3: Make a program EmptyGraph(n) that makes the adjacency matrix of a graph on n vertices with no edges.

Problem 4: Make a program CompleteGraph(n) that makes the adjacency matrix of a (simple) graph with an edge between all possible pairs of vertices i and j.

Warning: you might think to make a vector onesv = [1, 1, ..., 1] of all 1s, set A = [onesv, onesv, ..., onesv] and then just go through and set each A[i][i] = 0. The problem is, in the matrix A, each row is the same list, so the command A[0][0] = 0 will set the whole first column equal to zero. (You can try this for, e.g., a 3x3 matrix to see what I'm talking about.)

Problem 5: Make a program CycleGraph(n) that generates a "cycle graph" on {0, 1, 2, ..., n-1}, i.e., an undirected graph with edges from i to i+1 for each i = 0, 1,2, ..., n-2, and an edge from n-1 to 0. (See p. 21 in the Chapter 1 notes for how to do this as an adjacency list.)

Problem 6: If you finish all of these, you can get started on Exercises 1.3.7 and 1.3.8 that are part of the homework due next week.