15-110 Summer 2015

Programming Assignment 8

Overview

For this assignment you will work with pseudorandom numbers.

As always, you are responsible for protecting your solutions to these problems from being seen by other students, both physically (e.g., by looking over your shoulder) and electronically.

A note on grading: For this assignment you will be graded on code style. For full credit, you must adhere to the code style standards available on the course resources page.

Introduction

For this assignment you will write a random number-based "autograder", and then evaluate its performance using a Monte Carlo method. To get started, download the file autograder_starter.py in a folder named pa8. Make a copy of this file, name it autograder.py, and put all your work there. When you are done, you will zip up and submit.

[3 points] For this problem you will write a random number-based "autograder". Suppose a TA for 15-110 wants to speed up the grading of programming assignments and asks you to write an autograder in exchange for extra credit on all the labs you have skipped (or "missed due to illness"). Unfortunately for her students, she wants the autograder to assign grades solely based on randomness for the sake of time. Since she really has it in for her students, she wants your autograder to return a score in the "A" range (90-100) only 10% of the time, in the "B" range (80-89) 20% of the time, in the "C" range (70-79) 30% of the time, in the "D" range (60-69) 30% of the time, and in the "R" range (less than 60) 10% of the time.

Write the function autograder() based on the outlined specifications by the soon-to-be-fired TA. The function doesn't need a parameter since it doesn't look at the work to be graded.

Details: Assume that the autograder uses integer grades only. One way to do this is via a call to randint(1,100) to help determine the range for the generated grade. This will generate integers uniformly distributed from 1 to 100, inclusive. Thus, 40% of the time we expect to see a number in the range 1 to 40, inclusive. Similarly, about 30% of the time we will see a number in the range 41 to 70, inclusive. And so on. This gives us a way to choose whether to give an A, B, C, D, or R. Then we can generate a random grade in the appropriate range with another call to randint. A grades are 90-100, B's are 80-89, C's are 70-79, D's are 60-69, and R's are below 60.

Example:
```
>>> autograder()
85
>>> autograder()
83
>>> autograder()
73
>>> autograder()
79
>>> autograder()
66
>>> autograder()
78
>>> autograder()
62
>>> autograder()
79
```
[6 points] Evaluating your autograder using a Monte Carlo Method.

Since you've never done this before, you'd like to check that your autograder is producing the right mix of grades. Fortunately you've been studying Monte Carlo methods, so you decide to run some experiments.
1. [4 points] The first step is to write a function that calls the autograder many times, counts the A's, B's, etc., and determines the proportion of each letter grade.
  
  Begin by initializing a dictionary, using letter grades as keys and counts as values. Initially all the counts are zero. Call autograder() many times, incrementing the count for "A" if the result is between 90 and 100, for "B" whenever if it is between 80 and 89, and so on. Finally, determine what proportion of all the grades were A's, B's, and so on. Return a dictionary mapping each letter grade to its proportion.
  
  Write a function run_autograder(num_experiments) that runs "experiments" as described above.
  - Input: num_experiments (the number of times to call autograder())
  - Output: a dictionary with letter grades ("A", "B", "C", "D", and "R") as keys. Each letter grade will be associated with the proportion of all numeric grades assigned that fall into the range for that letter grade.
  Hints: Refer to the lecture notes on hash tables and Python dictionaries, or to the Python tutorial on dictionaries accessible from the course resources page. You will find the following things helpful:
  - Initializing a dictionary: dict = { key1 : value1, key2 : value2, etc. }
  - Iterating through the items of a dictionary: for (k, v) in dict.items() (there's an example of this in show_grades)
  - Iterating through the keys of a dictionary: for k in dict.keys()
  This function might take approximately 15 lines of code.
  
  The following examples run 1000 experiments each. Of course, the outputs are not identical. Make sure you know why not!
```
>>> run_autograder(1000)
{'D': 0.312, 'C': 0.282, 'B': 0.195, 'A': 0.111, 'R': 0.1}
>>> run_autograder(1000)
{'D': 0.289, 'C': 0.289, 'B': 0.216, 'A': 0.105, 'R': 0.101}
>>> run_autograder(1000)
{'D': 0.309, 'C': 0.317, 'B': 0.198, 'A': 0.099, 'R': 0.077}
```
  If we run only 10 experiments each time, the outputs vary a lot more, because of the Law of Large Numbers:
```
>>> run_autograder(10)
{'D': 0.4, 'C': 0.1, 'B': 0.2, 'A': 0.1, 'R': 0.2}
>>> run_autograder(10)
{'D': 0.5, 'C': 0.2, 'B': 0.1, 'A': 0.1, 'R': 0.1}
>>> run_autograder(10)
{'D': 0.6, 'C': 0.2, 'B': 0.1, 'A': 0.0, 'R': 0.1}
>>> 
```
2. [2 points] Looking at the outputs is not a very efficient way to know whether your autograder is doing the right thing. You decide to automate this process too. You will write a function test_autograder(num_experiments, tolerance). The idea is to call run_autograder and then check whether the proportion for each letter grade is close to the expected value, within a given tolerance.
  - Inputs: num_experiments is passed to run_autograder; tolerance is a small floating point number that tells how far from the expected value the results are allowed to be.
  - Output: True or False, depending on whether the experimental results are close enough to the expected values.
  Algorithm:
  1. Call run_autograder and set grade_frequencies to the dictionary returned.
  2. For each letter grade, look up the grade frequency in grade_frequencies, subtract the expected value, and take the absolute value of the result (use abs). If this absolute value is more than tolerance, return False.
  3. Return True. (This step will only be reached if all the previous tests were within tolerance.)
  This function might take approximately 15 lines of code. Although step 2 may look as if you need a loop, it is perfectly acceptable (and probably simpler) to check the tolerance for each letter grade with a separate line of code.
  
  In the following example, again reflecting the Law of Large Numbers, we see that 10000 trials result in grade distributions that are within .01 of the expected values, but using only 100 trials fails to be within tolerance. Using a larger tolerance of .05 with 100 trials sometimes succeeds and sometimes fails. Make sure you understand why the same inputs can yield different outputs!
```
>>> test_autograder(10000, .01)
True
>>> test_autograder(100, .01)
False
>>> test_autograder(100, .05)
True
>>> test_autograder(100, .05)
False
```
[1 point] Assigning Grades

Since you've established that your autograder performs as specified, you deliver it to the TA. But now she realizes that she wants to be able to simply assign grades to all the people in her section with one function call before giving you extra credit. Write a function assign_grades(names) in autograder.py that takes a list names of names and returns a Python dictionary with names as keys and the associated numeric grades as values. It assigns each person's grade using the autograder() function.

Hint: You should be able to do this with five or six lines of code.

We've provided a function show_grades to display the dictionary for you more conveniently. Example:
```
>>> table = assign_grades(["Dilsun", "Penny", "Fred", "George", "Batman", "Annie", "Barack", "Voldemort", "Flavor Flav", "Tim"])
>>> table
{'Penny': 65, 'Flavor Flav': 79, 'Batman': 81, 'Fred': 76, 'George': 83, 'Dilsun': 55, 'Voldemort': 74, 'Annie': 94, 'Barack': 83, 'Tim': 69}
>>> show_grades(table)
Name                 Grade
Penny                 65
Flavor Flav           79
Batman                81
Fred                  76
George                83
Dilsun                55
Voldemort             74
Annie                 94
Barack                83
Tim                   69
```

Submission Checklist

Your pa8.zip should contain the following file:

autograder.py

Be sure to also download your submission from Autolab and unzip it to check that you submitted properly.