MATH 1MP3 Homework #4 Due: 11:59pm, Sunday, March 18.
Important notes:
- To start the assignment, download the plain text files homework4.py found here: https://ms.mcmaster.ca/~matt/1mp3/homework/homework4. py and grades.txt found here: https://ms.mcmaster.ca/~matt/ 1mp3/homework/grades.txt. You should also download the python
file poly_functions.py found here: https://ms.mcmaster.ca/~matt/ 1mp3/homework/poly_functions.py - Your assignment must be submitted as a plain text file called yourmacid homework4.py,
where yourmacid is replaced with your macid from your McMaster email address. Note that yourmacid is not your student number or your entire McMaster email address.
Since my McMaster email address is valeriot@mcmaster.ca then the file that I would submit would be valeriot homework4.py. You must submit this file to the Dropbox on the MATH 1MP3 Avenue to Learn site.
Do not submit a file that ends with .txt or .rtf or .pages or ….
- There are two separate questions in this assignment, but your solutions will be contained in the single plain text file that you will submit. The solution to each question consists of python code that implements the functions described in each question.
- To complete your assignment, place your code for each question in between the commented lines that can be found in the file. You must also provide a document string for each function that includes a clear and concise description of what the function does, along with the type and use of each argument to the function. The docstrings should also contain a reasonable selection of test cases, when appropriate. To see what form your document strings should have, check out the document
1
strings that were provided for the functions from homework assignment #2. Do not alter any other part of the homework4.py file and do not add python code in any other parts of the file that you submit.
- The pycharm IDE can help to automate the production of the doc- string. Just after each def statement in the file, delete the existing double quotes, type “”” (three double-quotation marks) and hit enter. The editor will produce a documentation string stub that consists of a blank line, used to enter some descriptive text, and also include a new line for each of the function arguments and the return value. Alterna- tively, if you place your cursor over the function name, a small light bulb icon will appear. If you click on it and select Insert documentation string stub, the docstring stub will be produced. Here is a link to a page that deals with this topic: https://www.jetbrains.com/help/ pycharm/using-docstrings-to-specify-types.html. Note that you will also need to add some test cases within your docstring, when ap- propriate.
- There are two import statements near the top of the homework4.py file: your code cannot contain any other import statements. It should also not contain print statements. The functions use the return statement to return the result of the function call, so print statements should not occur in your solution. While developing and testing your code, it might be helpful to use print statements, but they should be removed before submitting your solution.
- Any file that is submitted for grading that does not conform to the above specifications may lead to a grade of 0 on the assignment.
- Before submitting your solution, you should make sure that it runs properly. To do this, you can open the file yourmacid homework4.py in the pycharm editor and then click the right mouse button to open a menu. In the menu, select “Run file in Console” to load your function definitions in the python console. Then, within the console you can test your functions using the command line.
- Carefully read over each of the following two questions.
- Once you have produced code for a given question, you should run it in
pycharm on a wide variety of test cases. Since the function definitions 2
that are provided in the file homework4.py do not contain document strings or test cases, you will need to carefully test your solutions by coming up with a good set of representative test cases. Make sure that you consider extreme or border line cases as well. Just because your code runs correctly on a few sample test cases does not mean that it will run correctly on all possible inputs.
- Your grade for each question will depend on whether or not your code correctly handles the test cases that we will run on your solutions, as well as the quality of the document strings that you provide for each function.
- Do not leave this until the last minute, since you might encounter computer/internet/Avenue issues.
- If you have questions about this assignment that haven’t been answered in the lectures, labs, or office hours, you can write to the TA Yicheng Chen (cheny312@mcmaster.ca) (or to the instructor) for help. Please note that we may not respond to emails sent less than 24hrs before the assignment is due.
- Late assignments will not be accepted.
- All work submitted for grading must be your own. You may discuss homework problems and related material with other students, but you must not submit work copied from others or from the internet.
3
Question #1
This question comes in five parts and deals with processing files that contain student grades for a course.
- (a) Create a function called mcmaster_grade(number) that has one ar- gument that is a number between 0 and 100 that represents a grade. The function should return the corresponding grade point value for this grade, using the McMaster 13 point grading system. Details can be found here:
https://registrar.mcmaster.ca/exams/grades.
For example, any grade that is less than or equal to 49.5 corresponds to the grade value 0, any grade that is greater than 49.5 and less than or equal to 52.5 corresponds to the grade value 1, and so on.
- Note that there are 13 possible grade values, ranging from 0 (which corresponds to a grade of F), to 12 (which corresponds to a grade of A+).
- Your code will probably make use of several if-elif-else type statements.
- Some examples:
– mcmaster_grade(22.4) returns 0, – mcmaster_grade(85) returns 11,
– mcmaster_grade(62.51) returns 5.
- (b) Produce a function student_grades(filename) that has one argu- ment filename that is the name of a plain text file that contains the grades for the students in a particular course. Each line of the file begins with the (first) name of a student, followed by a sequence of numbers that lie between 0 and 100. The elements of each line are separated by blank space ” “. The function should create and return a dictionary that has as keys the student names from the file and values a 1-dimensional NumPy array of numbers of type float that contains the sequence of grades for that student.
4
- The first entry of each line of the file will be the name of a student. You can assume that the name does not contain any spaces, but it may contain hyphens, in addition to upper and lower case letters. For example, the names JOHN-DAVID and SALLY appear in the sample grades.txt file.
- You may assume that the number of grades that are recorded for each student is the same throughout the file. In the sample file grades.txt, there are eight grades recorded for each student.
- TheNumPymoduleisimportedasnpatthetopofthehomework3.py file and so you do not need to import it again.
- Before converting the sequence of grades to a NumPy array you will first need to clean up each line and split it into separate strings. You will probably want to use the strip and split string functions for this. Keep in mind that each line of the file will be read in as a string.
- You can assume that there are no duplicate names in the file.
- We have worked through examples in class that read files and produce dictionaries from them. You can review those examples to see how to approach this question.
(c) Produce a function weight_avg(grades, w) that has two arguments: grades is a 1-dimensional NumPy array that contains numbers, and w is an optional argument that is a list of numbers of the same length as grades. The function should return the weighted average of the numbers in grades using the corresponding numbers in w as weights.
- Given a sequence of numbers a0, a1, . . . , an−1 and a sequence of weights w0, w1, . . . , wn−1, the weighted average of the numbers is
w0 ·a0 +w1 ·a1 +…+wn−1 ·an−1. w0 +w1 +…+wn−1
- The weighted average of a 1-dimensional NumPy array can be eas- ily calculated using the NumPy function np.average (but there are other ways to do this, for example by using the dot product function). If you use this function, then your solution to question #1 (c) will be pretty short.
5
- Each line in the sample file grades.txt contains eight grades: the first 3 are quiz grades, the next 3 are homework grades, the 7th is a midterm test grade, and the last is the final exam grade.
In the file homework4.py, the default value for the variable w in the function has been set to the list [5, 5, 5, 5, 5, 5, 20, 50]. This provides a weighting of 5% for each of the quizzes and home- work assignment grades, 20% for the test grade, and 50% for the exam grade. - With this weighting the list of grades for the student JOHN-DAVID should have a weighted average of 66.1.
- You can assume that the lengths of grades and w are the same, and so your code does not need to check for this.
- (d) Create a function student_average(st_gr, w) that has two argu- ments: st_gr is a dictionary of the type that is produced in part (b), namely, the keys of this dictionary are student names, and the val- ues are 1-dimensional NumPy arrays that contain the student’s grades. The optional argument w is a list of numbers of the same length as the 1-dimensional arrays from st_gr that will be used as weights to compute the weighted average for each student. The default value for wissetto[5, 5, 5, 5, 5, 5, 20, 50].
The function should return a dictionary whose keys are the student names from st_gr and whose values are the student’s averages, ob- tained using the weights from w. It should not alter the dictionary st_gr.
- You can assume that the length of w is the same as the lengths of the 1-dimensional NumPy arrays from the dictionary st_gr and so your code does not need to check for this.
- For example, if the dictionary st_gr is produced from the sam- ple file grades.txt using the function students_grades and if st_avg is produced by running student_average(st_gr) then st_avg[’JOHN-DAVID’] = 66.1.
- Your solution should use the function from part (c) to compute the weighted averages for each student in the dictionary.
- (e) Create a function mcmaster_grade_student(st_avg) that has one ar- gument that is a dictionary that has students names as keys and their
6
average in a course as values. The function from part (d) produces dictionaries of this sort.
The function mcmaster_grade_student(st_avg) produces a dictio- nary that has as keys the 13 McMaster grade values: 0, 1, 2, …, 12, and values the list of students from st_avg that have the given grade value.
- So, if gr_st = mcmaster_grade_student(st_avg) then gr_st[1] is the list of all students that have a grade value of 1 (or a grade of D-).
- This function takes the dictionary st_avg and inverts it to pro- duce a new dictionary. Before inverting it, it should first convert a given average to the corresponding McMaster grade value (prob- ably using your function from part (a)).
- We’ve worked through how to invert a dictionary in class; you could review the notes and codes from that lecture to see how to approach this question.
Sample Output When the above functions are run on the sample file grades.txt, the following should be produced by your code. In addition to testing your code on this file, you should create your own small grades files, using different numbers of grades to test your code out.
• st_gr = student_grades(’grades.txt’) should produce the follow- ing dictionary st_gr. Some of the middle parts are not displayed. The order of the items may vary, but this doesn’t matter.
{’JOHN-DAVID’: array([68., 84., 72., 84., 60., 32., 88., 57.]), ’BRETT’: array([76., 72., 80., 92., 0., 0., 52., 64.]), ’ERIN’: array([ 80., 72., 100., 68., 52., 0., 92., 79.]), ’MAGALI’: array([80., 76., 84., 64., 36., 16., 56., 76.]), ’JONAH’: array([ 96., 100., 92., 96., 60., 60., 100., 94.]), ... ,’JASON’: array([84., 76., 76., 88., 44., 52., 84., 84.]), ’SAM’: array([52., 56., 84., 68., 0., 20., 52., 38.]), ’ZHEN’: array([96., 88., 84., 88., 52., 52., 88., 68.])}7
• st_avg = student_average(st_gr) should produce the following dic- tionary:
{’JOHN-DAVID’: 66.1, ’BRETT’: 58.4, ’ERIN’: 76.5, ’MAGALI’: 67.0,
’JONAH’: 92.2, ’SPENCER’: 61.5, ’DAI’: 78.6, ’JULIA’: 86.6,
’GEOFFREY’: 54.6, ’RICHARD’: 59.9, ’JESSE’: 72.6, ’MINGYU’: 40.8,
’PAUL’: 71.6, ’SALLY’: 34.2, ’JASON’: 79.8, ’SAM’: 43.4, ’ZHEN’: 74.6}
• gr_st = mcmaster_grade_student(st_avg) should produce the fol- lowing dictionary. The ordering may vary; what is important is that the dictionary that you produce contains the same set of key:value pairs.
{5: [’JOHN-DAVID’], 3: [’BRETT’], 9: [’ERIN’, ’DAI’], 6: [’MAGALI’],
12: [’JONAH’], 4: [’SPENCER’, ’RICHARD’], 11: [’JULIA’],
2: [’GEOFFREY’], 8: [’JESSE’, ’ZHEN’], 0: [’MINGYU’, ’SALLY’, ’SAM’],
7: [’PAUL’], 10: [’JASON’]}
Question #2
This question implements Newton’s Method for approximating the roots of polynomial functions. Recall that Newton’s Method, when applied to a dif- ferentiable function f(x) will start with some initial guess x0 of a zero of f and then will produce a sequence of approximations x1, x2, . . . . The formula for producing xn+1 from xn is:
xn+1 =xn − f(xn). f′(xn)
Consult Section 4.8 from your copy of Dr. Stewart’s Calculus textbook for more details and examples.
This question makes use of two functions from homework assignment #3, namely
polynomial_function(coeffs) and polynomial_derivative(coeffs). homework4.pycontainsthestatementimport polynomial_functions as poly
so that these two functions are available to be used. Make sure that you have 8
downloaded this file from the course website and that it is in the same folder as your copy of homework4.py.
You cannot make use of any math or numpy module functions in your solutions to any parts of this problem.
(a) Produceafunctionnext_approx(coeffs, xn)thathastwoarguments: coeffs is a list of numbers that are the coefficients of a polynomial p(x), and xn is a number that the Newton’s Method formula will be applied to. The function will return the new approximation obtained from the formula. The default value for xn has been set to 0 in the file homework4.py.
- Your code does not need to check for division by zero; this will happen if the polynomial p(x) is a constant function, or p′(xn) = 0, but don’t worry about this.
- As an example, next_approx([-5, -2, 0, 1], 2) should re- turnthenumber2.1andnext_approx([-2, 0, 0, 0, 0, 0, 1], 2) should return the number 1.6770833333333333.
- You should use poly.polynomial_function(coeffs) and poly.polynomial_derivative(coeffs) to compute the values of the polynomials p(x) and p′(x) needed for the Newton’s Method formula. The expression
p = poly.polynomial_function([-5, -2, 0, 1])
will produce the function p(x) = x3 − 2x − 5 and the expression p(2) will produce the value -1.
(b) Produceafunctionapprox_root(coeffs, x0, tol, max_steps)that has four arguments:
- coeffs: a list of numbers, representing the coefficients of a poly- nomial p(x),
- x0: the initial guess for a root of p(x). The default value is x0 = 0.
- tol: a float with default value 1e-4 that determines the accuracy
of the approximation to be produced,
- max steps: a positive integer with default value 10 that deter- mines the maximum number of times to apply the Newton’s Method formula.
9
This function will start with the initial guess/approximation of x0 as a zero of the polynomial p(x) determined by coeffs and then will suc- cessively produce approximations using the Newton’s Method formula until the difference between successive approximations has size less than or equal to tol or the number of steps has exceeded max_steps.
Once this has occurred, the function will return the tuple of length 3 whose first entry is the last approximation produced, xn, the value p(xn), and the number of steps needed to compute the approximation.
Forexample,approx_root([-5, -2, 0, 1], 2)shouldreturnthetu- ple
(2.094551481698199, 1.739762112151766e-09, 3), approx_root([-5, -2, 0, 1]) should return the tuple
(-2.022194255464349, -9.224908997053978, 10),
and approx_root([-5, -2, 0, 1], tol = 1e-8, max_steps = 100)
should return the tuple
(2.0945514815423265, -1.7763568394002505e-15, 19),
- As successive approximations are computed, you will need to keep track of the current one, maybe call it x_old and then use it to produce the next approximation, maybe call it x_new.
- You will probably want to use a while loop and test if the absolute value of the difference between x_new and x_old is less than or equal to the value of tol. We did something similar to this when looking at the grid and bisection methods in class.
- You will also need a step counter so that the while loop can be terminated whenever the number of steps exceeds max_steps.
- You should use the function from part (a) of this question at some point in your code.
(c) Produce a function nth_root(a, n, tol, max_steps) that has four arguments:
• a: a positive number,
10
- n: a positive integer.
- tol: a float with default value 1e-4 that determines the accuracy
of the approximation,
- max steps: a positive integer with default value 10 that deter- mines the maximum number of times to apply the Newton’s Method formula.
The function will return the approximation of the nth root of a, using Newton’s Method. The function will stop execution once the difference between successive approximations is less than or equal to tol or the number of steps exceeeds max_steps.
- You cannot use the python exponentiation function in your solu- tion.
- You do not need to check that a and n are positive.
- Example 2 from Section 4.8 of Dr. Stewart’s calculus textbook illustrates how to use Newton’s Method to approximate the nth rootofanumber. Sincec= √n aifandonlyifcisazeroofthe polynomial p(x) = xn − a, then Newton’s Method can be used to approximate a root of xn − a, and hence an nth root of a.
- You should use the function approx_roots from part (b). If you do then your code for part (c) will be short. All that you need to do is to produce the appropriate coefficients list for the polynomial xn−a. For example, the coefficient list for x3−2 is [-2, 0, 0, 1].
- Theresultofexecutingnth_root(2, 6)isthevalue1.1224620510405428 and the result of executing nth_root(100, 2, 1e-6) is 10.0.
11