Description
Background:
We discussed in class a technique called “decrease and conquer”. The main idea, abstractly, is that to solve a problem with API, say, f(A), we utilize the same strategy by invoking f(B), where the problem size of B is less than A.
Examples we discussed in class includes computing the length of a list:
def rec_len(L):
if L==[]:
return 0
else:
first = L.pop(0)
return rec_len(L) + 1 # here’s the decrease and conquer step
Although the implementation of decrease and conquer can be iterative or recursive, a recursive implementation is often more natural and easier.
To do this assignment, please (a) review class materials for decrease and conquer, (b) make sure you know how to manipulate lists in Python, e.g. popping an item off the list and concatenating two lists.
Assignment:
1. (30 points) We discussed in class a decrease and conquer strategy to find the minimum number in a list. The Python function was like this:
def my_min(L):
if L==[]:
print(“undefined behavior.”)
return
if len(L) == 1:
return L[0]
first = L.pop(0)
smallest_of_the_tail = my_min(L)
if first