7.25. Discussion Questions

  1. Draw the graph corresponding to the following adjacency matrix.

../_images/adjMatEX.png
  1. Draw the graph corresponding to the following list of edges.

    from

    to

    cost

    1

    2

    10

    1

    3

    15

    1

    6

    5

    2

    3

    7

    3

    4

    7

    3

    6

    10

    4

    5

    7

    6

    4

    5

    5

    6

    13

  2. Ignoring the weights, perform a breadth-first search on the graph drawn for question 1 or 2.

  1. What is the Big-O running time of the build_graph function?

System Message: ERROR/3 (/home/bmiller/Runestone/books/pythonds3/_sources/Graphs/DiscussionQuestions.rst, line 59)

Content block expected for the “shortanswer” directive; none found.

.. shortanswer:: BigO
  1. Derive the Big-O running time for the topological sort algorithm.

System Message: ERROR/3 (/home/bmiller/Runestone/books/pythonds3/_sources/Graphs/DiscussionQuestions.rst, line 63)

Content block expected for the “shortanswer” directive; none found.

.. shortanswer:: BigOTwo
  1. Derive the Big-O running time for the strongly connected components algorithm.

  2. Show each step in applying Dijkstra’s algorithm to the graph drawn for question 1 or 2.

  3. Using Prim’s algorithm, find the minimum weight spanning tree for the graph drawn for question 1 or 2.

  1. Draw a dependency graph illustrating the steps needed to send an email. Perform a topological sort on your graph.

  2. Express branching factor \(k\) as a function of the board size \(n\).

  3. Derive an expression for the base of the exponent used in expressing the running time of the knights tour.

System Message: ERROR/3 (/home/bmiller/Runestone/books/pythonds3/_sources/Graphs/DiscussionQuestions.rst, line 86)

Content block expected for the “shortanswer” directive; none found.

.. shortanswer:: DFS
  1. Explain why the general DFS algorithm is not suitable for solving the knight’s tour problem.

  1. What is the Big-O running time for Prim’s minimum spanning tree algorithm?

You have attempted of activities on this page