[2022] CPSC 110 Introdunction to Computer Science - Assignment 7: Running Sum and Nilakantha Series
Assignment 7
- All assignments will be submitted through Canvas. If you submit multiple times, the most recent submission will be graded.
- Please review the collage’s plagiarism policies. As a general rule, copy/paste should never be used for any code. Ever. You may discuss topics with other students and reference online materials, but the final assignment must be written by the student. If you reference materials/people besides the textbook/instructor then cite this in a file contributions.txt. Full citations are not necessary, a bullet point list of the materials/people that you references is suitable.
- Code will be graded for functionality as well as quality. This means code that should be easy to read with descriptive variable names and appropriate comments.
- Code that cannot run successively in Python 3 will receive a zero. Make sure you are using the correct python verion and allow yourself enough time for thorough testing.
- At the start of each assignment will be a list of the required files for submission. All files should be compressed in one zip folder named yourname ASSIGN7 CPSC110.
For example: JOCELYNMINNS ASSIGN7 CPSC110
Assignment 7 Instructions:
• Total Points: 30
• Due: July 6, 2022, 11:59pm
• Requiered files:
1. timing.py
2. nilakantha.py
3. assign7.txt
4. contributions.txt
1 Running Sum [15 points]
Below are two versions of the same function: running sum. They will both produce the same output.
1 def running_sum_v1(aList): bList = aList[:]
length = len(aList)
for index in range(length):
2 bList[index] = bList[index] + sum(aList[:index])
3 return bList
4
5 def running_sum_v2(aList): bList = aList[:]
length = len(aList)
for index in range(1,length):
6 bList[index] = bList[index] + bList[index-1]
7 return bList
We are told by the creators of Python that:
len(list) has time T(n) = 1
sum(list) has time T(n) = n
1.1 Big-O of the functions
What is the Big-O of running sum v1 and running sum v2? Which function is better? Write your answer in a file assign7.txt
1.2 Timing the functions
We saw an example in the slides about timing a function. Write a main function that calls each function above, times how long they take and prints the result. You should time the function with each a list of size 100, a list of size 1,000 and a list of size 10,000 then prints the times for each test. Save your code in timing.py
Note that to get a list of size n, you can use:
aList = list(range(n))
For each length 100, 1000, and 10000 what times did you get from running sum v1 and running sum v2? Do these numbers makes sense given the answer in the previous part? Write your answer in a file assign7.txt
2 Nilakantha Series [15 points]
There are many mathematical formulas to determine the value of PI. The one we are focusing on today is the Nilakantha Series. This infinite series is used to estimate the value of Pi. It can be defined as:
Below is a Python function that that calculates the first n terms of the Nilakantha Series.
1 def nilakanthaSeries(terms):
2
3 for counter in range(terms):
4 result = 3
5 denom = 2
6 for n in range(counter):
7 result = result + (-1.0)**(n)*4.0/(denom*(denom+1)*(denom+2))
8 denom = denom + 2
9 pi = result
10 return pi
However, this code can be slow.
2.1 Orignal Code
What is the Big-O of this function? Write your answer in a file assign7.txt
2.2 Fixing Code
Improve this code so that it will be faster. Put your new version of the function in the file nilakantha.py
2.3 Fixed Code
What is the Big-O of the new function? Write your answer in a file assign7.txt
