Program files x86 google drive googledrivesync exe

Python Homework

Python Homework 3 Assigned: 12/3

Due: 12/7, 11:59pm

Possible Points: 100

Submit on Canvas a zip file containing your solution code for each problem (just the .py, .h, and .cpp files, please do not submit the solution/project files), turn in at least one .py and one .cpp file for each problem. Each problem specifies what you should title the file containing your solution so that the autograder can find it. Incorrectly named programs will not be graded and thus will get 0 points for the problem.

Since the assignment will be graded using an automated grading system you should have your program’s output match the sample output shown. If your program fails to run using Visual Studio 2017 it will receive zero points. If your program fails to run properly (runtime errors or wrong output) points will be deducted based on how correct is the program.

If you have any questions or concerns about the assignment do not hesitate to post on the discussion forum on canvas, send us message on canvas, or see us after class or during office hours.

Students are expected to write their source code from scratch, those who copy code from each other or web (including from Canvas examples) will be reported for cheating. We will also look at your code so do not just hard-code the answer and print it.

You have to write the solution both in Python and C++ (as exten- sion module). We recommend to first solve the problem in Python and then write the C++ extension code. Further, start with the pro- vided template. We will not penalize for 'self': unreferenced formal parameter warning. Additionally, the timings may differ, but we still expect you to match the formating, i.e, show the required number of significant digits. All input reading, timing, and printing must be done in Python.

1

1. Factorial: 10 points Files: factorial.py, factorialmodule.cpp

Compute a factorial of a given number, first in Python and then using C++ extension. The definition of a factorial of number n is as follows.

n! = n(n − 1)(n − 2)...1 (1)

Use int64_t in the C++ extension for the computations. In the wrapper function use PyLong_AsLongLong to convert from PyObject to int64_t and PyLong_FromLongLong to convert int64_t back to PyObject. Match the output format and use the provided timing code to measure the elapsed time for Python and C++ code.

Example Input

2 10 40

Expected Output

Case 0: Python: factorial of 10 is 3628800 Python: elapsed time 0.0056 ms C++: factorial of 10 is 3628800 C++: elapsed time 0.0112 ms Case 1: Python: factorial of 40 is 815915283247897734345611269596115894272000000000 Python: elapsed time 0.0073 ms C++: factorial of 40 is -70609262346240000 C++: elapsed time 0.0112 ms

2. Root Finding: 20 points File: root_finding.py, root_findingmodule.cpp

This assignment is to use Newton’s method to find the roots of an equation, starting the search at some point and finding the root to some desired accuracy or number of iterations. The equation you will be computing roots of is:

x5 + 6x4 + 3x3 − x − 50 (2)

2

Newton’s method works by starting from some (hopefully close) guess of the root and then iteratively updating it until we get close enough to the actual root of the equation. In other words, you iteratively compute the next best guess for the root using the following formula until convergence:

xn+1 = xn − f(xn) f ′(xn)

(3)

Your program does not need to compute f ′(x), instead compute the derivative by hand (or using WolframAlpha or however you prefer) and write the expression in your program. You can test for convergence by checking if xn+1 ≈ xn, specifically you should stop the root finding when the relative error has reached some threshold:

∣∣∣∣xn+1 − xnxn+1 ∣∣∣∣ ≤ ε (4)

or you have executed n iterations of the root finding method. You can find more information about Newton’s method on Wikipedia.

For computing absolute values, sine, cosine and powers you will want to use some of the functions in the cmath header (#include ), documented here.

The input to your program for each case will be the x value to start the search at followed by the number of iterations n and the tolerance ε. Your program should then find the root of equation (1) starting the search at x until the root is found to the desired tolerance or you have run the maximum number of iterations. When your program has found the root to within the desired precision or run out of iterations print it out to match the format below. Your program will need to run for at least one iteration to find the error between the guess and where we think the root is, even if the guess is exactly on.

You can reuse our/your solution from the previous homework.

Example Input

6 -5.2 100 1e-10 -1.0 100 1e-6 -5 1000 1e-10 1 10 1e-4 -7 100 1e-7 1 5 1e-10

Expected Output

3

https://en.wikipedia.org/wiki/Newton's_method
http://en.cppreference.com/w/cpp/header/cmath
Case 0: Python: root is -5.390653718237257 Python: elapsed time 0.0347 ms C++: root is -5.390653718237257 C++: elapsed time 0.0020 ms Case 1: Python: root is -5.390653718237257 Python: elapsed time 0.0188 ms C++: root is -5.390653718237257 C++: elapsed time 0.0017 ms Case 2: Python: root is -5.390653718237257 Python: elapsed time 0.0112 ms C++: root is -5.390653718237257 C++: elapsed time 0.0017 ms Case 3: Python: root is 1.5264066185662863 Python: elapsed time 0.0102 ms C++: root is 1.5264066185662863 C++: elapsed time 0.0017 ms Case 4: Python: root is -5.390653718237257 Python: elapsed time 0.0122 ms C++: root is -5.390653718237257 C++: elapsed time 0.0020 ms Case 5: Python: root is 1.5264080242772753 Python: elapsed time 0.0086 ms C++: root is 1.5264080242772753 C++: elapsed time 0.0026 ms

3. Lists: 30 points Files: lists.py, listsmodule.cpp

Implement a function that computes a sum of a given list both in Python and then as an extension in C++. Print the sum as in the example output and measure the time it took to compute the sum.

Implement a function that counts the occurences of a specified number in a list. The function needs to take two arguments, a list of numbers and a number for which to count occurrences. Print the output to match the example below.

Do not use built-in functions to compute the sum or count.

Documentation of list object manipulation functions

4

https://docs.python.org/3/c-api/list.html
Example Input

3 1 2 3 4 5 6 7 8 9 9 1 1 1 1 1 1 2 1 1 9 8 5 1 9 9 0 7

Example Output

Case 0: Python: sum 45 Python: elapsed time 0.0017 ms Python: 9 occurs 1 times Python: elapsed time 0.0122 ms C++: sum 45 C++: elapsed time 0.0119 ms C++: 9 occurs 1 times C++: elapsed time 0.0122 ms Case 1: Python: sum 8 Python: elapsed time 0.0010 ms Python: 1 occurs 6 times Python: elapsed time 0.0119 ms C++: sum 8 C++: elapsed time 0.0013 ms C++: 1 occurs 6 times C++: elapsed time 0.0017 ms Case 2: Python: sum 42 Python: elapsed time 0.0033 ms Python: 7 occurs 0 times Python: elapsed time 0.0013 ms C++: sum 42 C++: elapsed time 0.0010 ms C++: 7 occurs 0 times C++: elapsed time 0.0013 ms

4. Sudoku Solver: 40 points Files: sudoku_solver.py, sudoku_solvermodule.cpp and the provided files sudoku.py, sudoku.h without modifications

Use the provided sudoku solver (sudoku.py and sudoku.h) to solve sudoku

5

board both in Python and C++. If there is a solution, then convert it to a list of lists and return it back to Python where you print it in the format below. If there is no solution, return None. Represent the sudoku board as a list of lists, where each list is a row.

For the C++ extension you will need to convert sudoku board (list of lists) to the struct sudoku_board, pass it into the solver alongside another board’s pointer where the solution will be stored if found. Convert the solution (if any) back to list of lists and return it to Python interpreter. If there is no solution, return None and as for the Python solver print no solution.

Example Input

2 0 0 0 0 0 0 0 0 0 6 0 0 1 9 5 0 0 0 0 9 8 0 0 0 0 6 0 8 0 0 0 6 0 0 0 3 4 0 0 8 0 3 0 0 1 7 0 0 0 2 0 0 0 6 0 6 0 0 0 0 2 8 0 0 0 0 4 1 9 0 0 5 0 0 0 0 8 0 0 7 9 6 0 0 0 0 0 0 0 0 6 0 0 1 9 5 0 0 0 0 9 8 0 0 0 0 6 0 8 0 0 0 6 0 0 0 3 4 0 0 8 0 3 0 0 1 7 0 0 0 2 0 0 0 6 0 6 0 0 0 0 2 8 0 0 0 0 4 1 9 0 0 5 0 0 0 0 8 0 0 7 9

Expected Output

Case 0: Python: 3 4 5 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 5 3 4 2 8 6 1 7 9 Python: elapsed time 960.8519 ms C++:

6

3 4 5 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 5 3 4 2 8 6 1 7 9 C++: elapsed time 9.8189 ms Case 1: Python: no solution Python: elapsed time 224.6007 ms C++: no solution C++: elapsed time 2.1440 ms

7

Python Homework 3
1. Factorial: 10 points
2. Root Finding: 20 points
3. Lists: 30 points
4. Sudoku Solver: 40 points