Homework 2: Graphs
==================

+------------------------------------------------------------------------------+
| **Due Date**: 11:59pm February 6, 2025                                       |
|                                                                              |
| Homework should be submitted as a single Jupyter notebook to Dropbox         |
+------------------------------------------------------------------------------+

To do **in advance of this homework**:

* Make sure you have run the code in Allen Downey's Chapter 2 notebook (we will
  review this in lecture)

Exercises
---------

Complete the exercises corresponding to Exercise 2.1 -- 2.4 in Think Complexity
(version 2):

1. There are a few short exercises embedded in Chapter 2 notebook. Complete
   these in-place.
2. In Section 2.8 of the text, we analyzed the performance of
   ``reachable_nodes`` and classified it in :math:`O(n+m)`, where :math:`n` is
   the number of nodes and :math:`m` is the number of edges. Continuing the
   analysis, what is the order of growth for ``is_connected``?
   ::

      def is_connected(G):
        start = next(G.nodes_iter())
        reachable = reachable_nodes(G, start)
        return len(reachable) == len(G)

  You can indicate your answer directly in the notebook, using a Markdown cell
  with LaTeX.

3. In Allen Downey's implementation of ``reachable_nodes``, you might be
   bothered by the apparent inefficiency of adding *all* neighbours to the stack
   without checking whether they are already in ``seen``. Write a version of this
   function that checks the neighbours before adding them to the stack. Does this
   "optimization" change the order of growth? Does it make the functions faster?

4. There are actually two kinds of ER graphs. The one we generated in Chapter
   2, :math:`G(n,p)`, is characterized by two parameters, the number of nodes
   and the probability of an edge between the nodes.

   An alternative definition, denoted :math:`G(n,m)`, is also characterized by
   two parameters: the number of nodes, :math:`n`, and the number of edges,
   :math:`m`. Under this definition, the number of edges is fixed, but their
   location is random.

   Repeat the experiments we did in this chapter using this alternative
   definition. Here are a few suggestions for how to proceed:

   a. Write a function called ``m_pairs`` that takes a list of nodes and the
      number of edges, :math:`m`, and returns a random selection of :math:`m`
      edges. A simple way to do that is to generate a list of all possible edges
      and use ``random.sample``.
   b. Write a function called ``make_m_graph`` that takes :math:`n` and
      :math:`m` and returns a random graph with :math:`n` nodes and :math:`m`
      edges.
   c. Make a version of ``prob_connected`` that uses ``make_m_graph`` instead of
      make_random_graph.
   d. Compute the probability of connectivity for a range of values of
      :math:`m`.

   How do the results of this experiment compare to the results using the first type of ER graph?

Submission
----------

Please submit a single Jupyter notebook which completes the above exercises,
filling in Allen Downey's Chapter 2 notebook. There are already placeholders
in the notebook for your work.