Homework 1: Analysis of Algorithms and Hashtables
=================================================

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

Exercises
---------

Complete the exercises embedded in the Homework 2 notebook.

1. What happens if you pop from the end of a the list? Write a function called
   ``pop_right_list`` that pops the last element instead of the first. Use
   ``run_timing_test`` to characterize its performance.  Then use
   ``plot_timing_test`` with a few different values of ``exp`` to find the slope
   that best matches the data.  What conclusion can you draw about the order of
   growth for popping an element from the end of a list?

2. Write methods called ``add_dict`` and ``lookup_dict``, based on
   ``append_list`` and ``pop_left_list``. What is the order of growth for adding
   and looking up elements in a dictionary?

3. Go back and run ``run_timing_test`` with a larger value of ``max_time`` and
   see if the run time converges to the line with slope 2. Just be careful not to
   make ``max_time`` too big.

4. Write a function called ``lookup_hash_map``, based on ``lookup_better_map``,
   and characterize its run time. If things go according to plan, the results
   should converge to a line with slope 1.  Which means that ``n`` lookups is
   linear, which means that each lookup is constant time.  Which is pretty much
   magic.


Submission
----------

Please submit a single Jupyter notebook which completes the above exercises. It
should contain:

- Your ``pop_right_list`` method, your analysis with ``run_timing_test``, your
  plot using ``plot_timing_test`` and conclusion about its order of growth
- Your ``add_dict`` and ``lookup_dict`` methods, and your analysis of their
  order of growth
- Your plot for ``run_timing_test`` with a larger value of ``max_time``
- Your ``lookup_hash_map`` method and your analysis of its run time