CS 170 Reading Quiz -- Week 3, Wednesday

Please fill out this quiz, and press the "Submit" button at the end. Don't collaborate with anyone on quiz exercise solutions.

Please answer all questions.

Name:

SID: [No spaces and no dashes.]

1. Let G be an undirected graph with n vertices and m edges. Let v be a vertex in G, and let k denote the number of neighbors of v (i.e., the number of nodes connected to v by some edge).

(a) What is the running time to count how many neighbors v has, if the graph is represented using an adjacency matrix? Express your answer as a function of k,n,m, using Theta notation. Explain your answer briefly.

(b) What is the running time to count how many neighbors v has, if the graph is represented using adjacency lists? Express your answer as a function of k,n,m, using Theta notation. Explain your answer briefly.

2. Let G be an undirected graph with n vertices and m edges. Assume that there are no repeated edges (i.e., there is at most one edge for any given pair of vertices) and no self-loops (i.e., no edge of the form (v,v)).

(a) What is the largest that m could be, as a function of n?

(b) Suppose G is made up of a single connected component. What is the smallest that m could be, as a function of n?

3. What did you find difficult or confusing about the reading or the lectures, and what would you most like to see explained better? If nothing was difficult or confusing, and you understand the material pretty well, tell us what you found most interesting. Please be as specific as possible.

CS 170 home page