Description
1. (10 points) Use the arithmetic sum to find the answer for 2 + 3 + 4 + … + 2018.
2. (10 points) Use the geometric sum to find the answer for 1 + 6 + 62 + 63 + … +
631.
3. (10 points) Use the geometric sum to find the answer for 1/3 + 1/32 + 1/33 + … +
1/320.
4. (10 points) Find the running time equation, T(n), of this python function. You don’t
have to solve the equation.
def foo(L): # L is a list
if L == []:
return 1
s = 0
for x in L:
for y in L:
s = s + x*y
A = L[0, len(L)//2]
B = L[len(L)//2, len(L)]
return foo(A) + s + foo(B)
5. (20 points) Use repeated substitution to find the running time of T(n) = 4n + T(n1). Assume T(1) = 1.
6. (20 points) Use repeated substitution to find the running time of T(n) = 4n +
T(n/3). Assume T(1) = 1.
7. (20 points) Use repeated substitution to find the running time of T(n) = n2 +
4T(n/2). Assume T(1) = 1.
Plagiarism Policy:
You can discuss how to solve the problems with your classmates, but the solution
must be your own. Using other people’s solution will result in a zero for the
assignment and possible additional penalties.
Submission:
Put your name as part of the file name and upload your submission to eCourseware
Dropbox. You can submit either Word doc or txt file.