A3 review session

First, open session on any questions regarding A3.

See if you can answer the following:

  • What is the maximum length of a chain of words that could be returned by a solution to A3?
  • What is the document retrieval function supposed to do?
  • How is relevance measured given what the function is doing? Is this reasonable?
  • Could there be issues with the way relevance is measured in the question above?
  • Are there other ways we could improve this function to get better results?

Complexity problems

Some practice for the final exam:

  1. What is the maximum number of edges you can have in a directed graph with no loops?

  2. What is the complexity of INSERTING a new node into a graph that is stored as an adjacency matrix?

  3. What is the complexity of REMOVING a node from a graph stored in an adjacency list?

  4. Which of the following will have a lower complexity on AVERAGE?
    • counting the edges in a graph stored as an adjacency matrix
    • counting the edges in a graph stored as an adjacency list

  5. In the question above, does it matter whether the graph is directed or undirected?

  6. What does it mean to say ‘on average’ for graphs? What are we averaging over?

Additional Exercises

  1. What is the complexity for BFS and DFS? (Look at W11 for review).

  2. What is the complexity of finding two nodes with the largest distance in the graph? (Look at W11 for definition of distance)

  3. BFS always gives you the shortest path, while DFS may give you a much longer one. Do you think DFS is even necessary? If so, what are some advantages of DFS over BFS?

  4. Is it possible to perform DFS iteratively, as opposed to recursively? If you think so, how would you do this? (Hint: Look at BFS closely!)