Consider a directed, weighted graph G with |V| vertices and |E| edges. What is the worst-case time complexity of determining whether G contains an edge between vertices u and v (in either direction), if G is implemented using an adjacency matrix?

Consider a directed, weighted graph G with |V| vertices and |E| edges. What is the worst-case time complexity of running a Breadth-First Search (BFS) on G, if G is implemented using an unsorted adjacency list?

Consider a directed, weighted graph G with |V| vertices and |E| edges. What is the worst-case time complexity of counting the incoming edges of vertex v, if G is implemented using an unsorted adjacency list?

Consider a directed, weighted graph G with |V| vertices and |E| edges. What is the worst-case time complexity of finding the edge of largest weight, if G is implemented using an unsorted adjacency list?

Consider a directed, weighted graph G with |V| vertices and |E| edges. What is the worst-case time complexity of counting the incoming edges of vertex v, if G is implemented using an adjacency matrix?

Each of the recurrences below appears somewhere in this week's material. In a bottom-up implementation, which one can be evaluated using only a constant amount of extra space — keeping a fixed number of previously computed values rather than the whole table?