CS 124
Fall 2023

Problem Set 9

due by 10 p.m. on Saturday, September 30, 2023

suggested self-deadline of Friday September 29, 2023

Preliminaries

In your work on this assignment, make sure to abide by the collaboration policies of the course.

If you have questions while working on this assignment, please post them on Piazza or come to TA Help Hours.

Make sure to submit your work on Gradescope.

Problem 1: Plotting your pi estimates

50 points; pair-optional or group-of-3-optional

Begin by downloading the file ps9pr1.ipynb and opening it in Jupyter Notebook. We’ve given you some starter code that demonstrates how to scatter plot points in a circle.

Add a title cell using Markdown, containing the problem set information, your name, the date.

This problem builds off of Problem Set 8, Problem 2, (estimating pi), where you will visualize the random dart throwing in a Jupyter Notebook and Matplotlib.

For a refresher, please review the video for Class 8.

  1. Check the the starter Jupyter Notebook and make sure you can run it and understand it.

    • We have also provided an example Matplotlib section of code that will generate a circle with a scatter plot.

    • We have also provided a modified throw_dart() function that returns a list in the format [x,y,hit] where x, and y are the coordinates of the dart, and hit is a True or False value.

    • To demonstrate how to use this function, we provide a test_throw_darts() function.

  2. Complete the missing section of throw_n_darts(n), using the previous examples as a guide. Use it to generate data for 100 dart throws.

  3. Copy the Matplotlib example code into a new cell and modify it so that it:

    • Plots the misses as red circles (c=’r’, marker=’o’)
    • Plots the hits as green plusses (c=’g’, marker=’+’)

  4. Set the title of the plot to be 

    estimating $\pi$
    .

  5. Repeat the experiment with 10 dart throws and 1000 dart throws.

  6. Include the estimate of pi that each experiment calculates (you may borrow your calculation from PS7).

  7. Use Markdown cells to explain what each section of code is doing and how the experiment works. You may borrow text from the PS7 assignment page.

  8. Format your entire Notebook so that it’s beautiful and the flow from start to the end makes sense.

Important guidelines

  • You must format your Jupyter Notebook nicely. Some of the points will be awarded for clean and neat style.

  • Please Run All Cells before submitting your notebook file on Gradescope.

  • This submission will be manually graded, so you may use a certain amount of creativity as long as the required elements are easily found.

  • See submission instructions for directions on how to also submit a PDF version.

Problem 2: Exploring algorithmic complexity with runtime plots

50 points; open collaboration

For this problem, open collaboration is encouraged.

  • What this means:

    • You are not limited to working with a single pair.

    • You can discuss any detail and share code* with anybody in the class - as long as you credit them in your submission.

    • You can collaborate and work together with as large of a group as you want.

  • However:

    • Your submission must reflect a true collaborative effort.

    • You cannot simply submit the work of others.

    • You must understand and be able to explain every detail of your submission.

  • Posting on Piazza clarification:

    • For this problem, it’s ok to publicly post small parts your submission as long as you provide context.

      • For example, “here’s how I handled this tricky part of the problem”

    • Don’t post full “solution” that would defeat the purpose of the collaborations noted above.

Create a new Jupyter Notebook file, save it using the the name ps8pr2.ipynb

For this part of the assignment, you should pick several functions that we have used in the past few weeks to explore algorithmic complexity.

You will use the following code to time how long it takes to execute a section of code:

import timeit
start_time = timeit.default_timer()

# function to test, for example
throw_n_darts(1000000)

elapsed = timeit.default_timer() - start_time

Requirements:

Important guidelines

  • You must format your Jupyter Notebook nicely. Some of the points will be awarded for clean and neat style.

  • Please Run All Cells before submitting your notebook file on Gradescope.

  • This submission will be manually graded, so you may use a certain amount of creativity as long as the required elements are easily found.

  • See below for directions on saving a PDF version of the notebook.

Saving a PDF version of your Jupyter Notebook

When you upload your .ipynb file to Gradescope, the images of the plots will not be included. We need you to also submit a PDF version of your notebook.

One suggested way to do this is:

  1. Run All from the Cell menu.
  2. Go to the File menu, and select File -> Download As... -> HTML (.html)
  3. This will download a file with the same name as the notebook, except ending in .html
  4. Find this HTML file and open it with your web browser.
  5. Verify that the web browser displays the notebook with graphics correctly.
  6. Use the web browser’s print function.
  7. In the print menu, select Save as PDF as the destination rather than an actual printer. This will appear in different places for different web browsers.
  8. Save the resulting PDF file in a location where you can find it for uploading.
  9. Open the PDF file and verify that it looks correct.

Submitting Your Work

You should use Gradesope to submit the following files: