[Solved] CS1134-Homework 2-Using the definitions of O and of

Homework #2

Question 1:

Use the definitions of O and of in order to show the following:

1. 5 n³ + 2 n² + 3 n = O ³

b . 7n² + 2 n 8 =

c . Show that if d(n)=O(f(n)) and e(n)=O(g(n)), then the product d(n)e(n) is O ( f (n)g(n)).

Question 2 :

Give a characterization, in terms of n, of the running time of the following four functions:

de f example1(lst):

Return the sum of the prefix sums of sequence S.

n = len(lst) total = 0

for j in range(n):

for k in range(1+j):

total += lst[k]

return total def example2(lst): Return the sum of the prefix sums of sequence S.

n = len(lst) prefix = 0

total = 0

for j in range(n):

prefix += lst[j]

total += prefix

return total

def example3(n): i = 1

sum = 0

while (i < n*n):

i *= 2

sum += i return sum

def example4(n):

i = n

sum = 0

while (i > 1):

for j in range(i):sum += i*j

i //= 2

return sum

Question 3:

Implement a function def factors(num) . This function is given a positive

integer num, and returns a generator, that when iterated over, it will have all of nums divisors in an ascending order.

For Example, if we execute the following code: for curr_factor in factors(100): print(curr_factor)

The expected output is:

1 2 4 5 10 20 25 50 100

Implementation requirement: Pay attention to the running time of your

implementation. The for loop like the above, should run in a total cost of .

Question 4:

The number e is an important mathematical constant that is the base of the natural logarithm. e also arises in the study of compound interest, and in many other applications.

Background of e: https://en.wikipedia.org/wiki/E (mathematical constant)

e can be calculated as the sum of the infinite series:

4 4 4 4

= 1 +______ +____ +____ +___

The value of e is approximately equal to 2.71828. We can get an approximate value of e, by calculating only a partial sum of the infinite sum above (the more addends we add, the better approximation we get).

Implement the function def e_approx(n). This function is given a positive integer n, and returns an approximation of e, calculated by the sum of the first (n + 1) addends of the infinite sum above.

To test your function use the following main:

def main():

for n in range(15):

curr_approx = e_approx(n)

approx_str = {:.15f} .format(curr_approx)

print(n = , n, Approximation:, approx_str)

Note: Pay attention to the running time of e_approx. By calculating the factorials over for each addend, your running time could get inefficient. An efficient

implementation would run in .

Question 5:

Implement the function def split_parity(lst) . That takes lst, a listof integers. When called, the function changes the order of numbers in lst so that all the odd numbers will appear first, and all the even numbers will appear last. Note that the inner order of the odd numbers and the inner order of the even numbers dont matter.

For example, if lst is a list containing [1, 2, 3, 4], after calling split_parity, l s t could look like: [ 3, 1, 2, 4].

Implementation requirements:

1 . You are not allowed to use an auxiliary list (a temporary local list).

2 . Pay attention to the running time of your implementation. An efficient

implementation would run in a linear time. That is, if n is the length of lst, the

running time should be .

Question 6:

Implement the function def two_sum(srt _lst, target). This function is given:

• srt _lst a list of integers arranged in a sorted order
• target an integer

When called, it returns two indices (collected in a tuple), such that the elements in their positions add up to target. If there are no such indices, the function should return None.

For example, if srt_lst=[-2, 7, 11, 15, 20, 21], and target=22, your function would return (1, 3) because srt_lst[1]+ srt_lst[3]=7+15=22

Note: Pay attention to the running time of your function. Aim for a linear time algorithm.

Question 7:

Implement the function def findChange(lst01). This function is given l s t 0 1 , a list of integers containing a sequence of 0 s followed by a sequence of 1 s.

When called, it returns the index of the first 1 in l s t 0 1 .

For example, if lst01 is a list containing [0, 0, 0, 0, 0, 1, 1, 1], calling findChange(lst01) will return 5.