CS 163/265, Winter 2025, Practice Problem Set 1

1. If the web graph has $n$ vertices, what is the minimum possible pagerank that any vertex can have, as a function of $n$? Describe what needs to be true of a vertex to cause it to have this minimum value. (Use the version of pagerank defined in the lecture notes, not other variations.)

2. Gaze with horror at the "Notes" section of https://en.wikipedia.org/w/index.php?title=24-cell&oldid=1262995924. Write the Python representation for a directed graph with vertices m, r, s, t, ab, ad, ai, al, am, ar, bz, ca, cf, ci, cj, ck, cl, cm, ct, cu, cv, cy, cz, and dd, where each edge of your graph represents a note linked within another note. For instance, your graph should have edges from m to s and from m to cf. (It would be tedious to include all the other notes, so just use the ones listed here. For instance, the full graph of all the notes would also have another edge from m to ax, but we are not including ax in this question.)

3. Draw two depth-first search trees rooted at vertex m, for the graph from question 2 and for the graph obtained from it by reversing the direction of each of its edges. Use these two trees to answer the question: is this graph (and its reverse) strongly connected?

4. Find a directed graph, with the property that all vertices are reachable from the starting vertex, and two orderings of its vertices: (1) an ordering that can be generated by breadth-first search, but not by depth-first search, and (2) an ordering that can be generated by depth-first search, but not by breadth-first search. (Your graph will need to have at least four vertices for this to be possible.)