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:
- (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 <smallest_of_the_tail:
return first
else:
return smallest_of_the_tail
Trace by listing in order all recursive function calls resulted from the following function call my_min([10,5,20,7,10]).
- (30 points) Employ the decrease and conquer strategy to write a recursive Python function to compute the sum of a list. Here’s the API:
# Input: a list of numbers
# Output: a number, which is the sum of all numbers in the list
defmy_sum( a_list ):
# your code …
- (30 points) Employ the decrease and conquer strategy to write a recursive Python function to reverse a list. Here’s the API:
# Input: a list of things
# Output: another list, which is the reverse of the input list
def my_reverse( a_list ):
# your code…
- (10 points) Employ the decrease and conquer strategy to write a recursive Python function to compute the depth of a binary tree. The depth of a binary tree is the longest distance from the root to anyleaf. Here’s the API:
# Input: root node of a binary tree
# Output: a number, which is the depth of the tree rooted by the input node
def my_depth( a_root_node ):
# your code…
Plagiarism Policy:
You can discuss how to solve the problems with your classmates, but the code must be your own. Using other people’s code will result in a zero for the assignment and possible additional penalties.
Submission:
Put the solutions in one Python (.py) file. Put your name as part of the file name. For example: JohnSmith_hw1.py.
Upload your Python file to the Assignment 1 folder in theeCourseware Dropbox.