3.2. 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

3.2.1. 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.

3.2.2. 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