Computational Algorithms in Python

Computational Algorithms in Python Homework Sample

What will the function mystery(1) output when called, display a stack trace of the recursive function calls. The code for finder, calls a recursive method finder_rec, what is returned from the sample output and what does the function actually do. Write a version that works iteratively rather than recursively. The final code performs a search to find if there is an element that is present more than once, how does the number of operations change as the length of the list increases. Modify the code to count the number of comparisons and return that instead of true / false. Which 5 element list would return the best case running time, and which would return the worst. For further Python programming assignment help contact us for a quote.

Question 1:


The recursion tracing diagram:

Here the function recursively calls itself and value of n before calling until n is 4. When n is 4 it each called functions returns printing the value of n in itself. So first numbers are printed in increasing order and then in decreasing order. Just like if the numbers are printed and pushed into a stack then popped and printed.

Question 2:

i) 1001.
ii) Finder method is just calling finder_rec method using the data and the length of data-1. Finder_rec method recursively iterating through the whole array and return the maximum value of the array.
It is storing the current value of iteration in v1 and maximum value of the subarray until the current value in v2. Then it is comparing v1 and v2 and returning that which is bigger.
The recursion tracing diagram:

iii) Commented code:

def finder(data):
return finder_rec(data, len(data)-1)

def finder_rec(data, x):
if x == 0:
return data[x] #The base case, i.e. for 1 length array the only would be the # maximum

v1 = data[x] # Storing the current value
v2 = finder_rec(data, x-1) # Storing the maximum value of the subarray until the current # value

# Returning the greater value between v1 and v2
if v1 > v2:
return v1
return v2

iv) Iterative method:

def iter(data):
x = -float(‘inf’) #setting value of x minus infinity

#iterating through all numbers in the array
for number in data:
if number > x:
x = number
return x

Question 3:

The best case complexity is O(1). When a duplicate element of the first number is in the 2nd position then it will return at the first iteration i.e. in constant time.
The worst case complexity is O(n2). When there is no duplicate in the array the algorithm will iterate through the array for each of the number and then finally it will return.
The code:
def contains_duplicates(elements):
x = 0
for i in range(0, len(elements)):
for j in range(0, len(elements)):
if i == j:
x += 1
if elements[i] == elements[j]:
return x
return x

d) input for the best case : [1, 1, 2, 3, 4]
e) input for worst case: [1, 2, 3, 4, 5]
f) For the first array the algorithm will take longer.
For finding the duplicate in the first array the algorithm iterates through the array 3 times where for second one it runs only for 1 time. In second iteration it finds the value.