Description
Assignment:
1. (20 points) Use the definition of O to prove that 5n3 + 10n2 + 1 is in O(n4)
2. (20 points) Use the definition of Ω to prove that 5n3 + 10n2 + 1 is in Ω(n3)
3. (20 points) Use the geometric sum to find the answer for 1 + 6 + 62 + 63 + … + 631.
4. (10 points) Use repeated substitution to find the running time of T(n) = 4n + T(n-1).
Assume T(1) = 1.
5. (10 points) Use repeated substitution to find the running time of T(n) = 4n + T(n/2).
Assume T(1) = 1. If you can do problem 3 and know how to use substitution, you
should be able to do this problem.
6. (20 points) Write a recursive Python function that takes as input two sorted lists of
numbers and returns a sorted union of the two input lists. For example,
union([1,5,10,20], [2,4,10]) returns [1,2,4,5,10,10,20].
The function should look like this:
# Input: A and B are both sorted lists
# Output: C is sorted and is a union of A and B.
def union(A, B):
# your code goes here
# …
return C
The following observations can be helpful:
• Problem size is len(A) + len(B)
• Compare the first elements of A and B.
• Suppose A[0] < B[0]. Then, you can remove A[0] and know that it is the first
element of the union.
• How do you the same problem with problem size len(A) + len(B) - 1? Answer:
use the same strategy.
• Do not trace function calls. Instead abstract the same strategy as a recursive
call.
• Of course, you will need to take care of “smallest” cases, where you can’t
remove the first element of A or B.
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 Python code in one Python (.py) file. Put other work in a separate text file.
Put your name as part of the file name. For example: If your name is John Smith,
name your files like this: JohnSmith_hw3.py and JohnSmith_hw3.txt (or
JohnSmith_hw3.docx).
Upload your submission to the Assignment 3 folder in the eCourseware Dropbox.
