CS 503, Advanced Programming I

Quiz 5, 4 April 2006

  1. Give an algorithm to determine the number of paths of length n > 0 between any pair of vertices in an undirected graph.

    See Nyhoff, page 886.

  2. A colleague of yours proposes the following as an improved algorithm for testing graph connectedness:
    Compare the number of edges to the number of vertices. If there are less than |V| - 1 edges, there can't be a spanning tree and the graph is not connected. If there are at least |V| - 1 edges, there is a spanning tree and the graph must be connected.
    How successful do you think your colleague's algorithm will be? Explain.

    Your colleague's algorithm is half-successfull. If a graph has less than |V| - 1 edges, it can't possibly be connected by your colleague's reasoning. However if a graph has at least |V| - 1 edges, it's not necessarily the case that you can construct a spanning tree for the graph. For example, the graph

    your colleague's downfall

    has the necessary number of edges according to your colleague, but is not a connected graph.

  3. The concept-graph algorithm given in Assignment 5 has similarities with Dijkstra's algorithm. Describe and justify one point of similarity and one point of difference between the two algorithms.

    Your two answers should demonstrate a knowledge of both the purpose and function of the two algorithms. "They both work on graphs." is not a good description of similarities. Oh, and keep your answers short (no more than a half-page per answer, say).

    The concept-graph algorithm is similar to Dijkstra's algorithm because they both incrementally build a graph by adding an edge that crosses from the graph to a node that is not in the graph. They differ in that Dijkstra's algorithm adds the only the edge with the smalest weight, while the concept-graph algorithm adds the node with the largest weight back into the graph and adds all edges from the new node back into the graph.

  4. Provide a worst-case asymptotic analysis of the space requirements for each of the three ways of representing undirected graphs.

    The adjacency-matrix representation takes O(V2) space, the adjacency-list representation takes O(E + V) space, the same as the edge-list representation.

This page last modified on 8 April 2006.