Assignment 2

Objective

Objective: The objective of this assignment is to practice working with data sequences (strings and lists), deepen your understanding on functions by tracing function calls and observing the data values as they execute. In addition, you will write several recursive functions to practice using this important divide-and-conquer strategy.

Preliminaries

In your work on this assignment, make sure to abide by the collaboration policies of the course.

If you have questions while working on this assignment, please post them on Piazza! This is the best way to get a quick response from your classmates and the course staff.

Task 1: Decision Statements

50 points; individual-only

In this problem you will write several functions that employ the power of recursion!

In Spyder, use the File -> New Window menu option to open a new editor window for your program, and save it using the the name a2task1.py. Make sure to specify the .py extension.

Here are the descriptions of the functions:

1. Write a function smaller(x, y) that takes two numbers x and y and returns the smaller of the two numbers.

   Examples:

   >>> smaller(20, 4)
   4
   >>> smaller(5, 8)
   5
   

   Note: You may not use the built-in function min(x,y). Practice writing your own if/else logic.

2. Write a function smallest(x, y, z) that takes three parameters and returns the smallest of the three.

   Examples:

   >>> smallest(20, 4, 17)
   4
   >>> smallest(10, 8, 4)
   4    
   >>> smallest(10, 8, 10)
   8   
   >>> smallest(10, 18, 10)
   10
   

   You may NOT use the built-in function min(x,y). Practice writing your own if/else logic.

3. Write a function is_factor(n, x) that takes a two integers n and x, and returns True if x is a factor of n and False otherwise.

   Examples:

   >>> is_factor(20, 4)
   True
   >>> is_factor(4321, 13)
   False
   >>> is_factor(5338, 17)
   True
   

4. Write a function has_vowel(s) that takes a string s and returns True if the string contains at least one vowel (any letter in 'aeiou') and False otherwise.

   Examples:

   >>> has_vowel('finance')
   True
   >>> has_vowel('czyk')
   False
   

   Hint: use the in operator to test for membership, i.e., ‘t’ in ‘python’

Task 2: Fun with recursion

50 points; individual-only

In this problem you will write several functions that employ the power of recursion!

In Spyder, use the File -> New Window menu option to open a new editor window for your program, and save it using the the name a2task2.py. Make sure to specify the .py extension.

Here are the descriptions of the functions:

1. Write a function mult(n, m) that takes two integers n and m as inputs and uses recursion to compute and return the product of those integers. To force you to use recursion, you may not use the multiplication operator (*). Rather, you should use recursion to add together n copies of m. For example, 4*5 = 5 + 5 + 5 + 5.

   Here are two examples of how mult should work:

   >>> mult(6, 7)
   42
   >>> mult(-3, 6)
   -18
   

   This function is similar to the power function from lecture. However, you will need a special case for when the first parameter is negative. To do so, add the following elif clause after your code that checks for the base case:

   elif n < 0:
       return -mult(-n, m)
   

   Note that this code uses the negation operator (-) to change the sign of a number. In particular:

   • -n gives us the opposite of the value of n
   • -mult(-n, m) gives us the opposite of the value returned by mult(-n, m).

   For example, the call mult(-3, 6) will return the opposite of the value returned by mult(3, 6).

2. Write a function copy(s, n) that takes as inputs a string s and an integer n, and that uses recursion to create and return a string in which n copies of s have been concatenated together. If n is less than or equal to 0, the function should return the empty string (i.e., the string ‘’, which does not have any spaces between the quotes).

   Here are some test cases:

   >>> copy('da', 2)
   'dada'
   >>> copy('Go BU!', 4)
   'Go BU!Go BU!Go BU!Go BU!'
   >>> copy('hello', 1)
   'hello'
   >>> copy('hello', 0)
   ''
   >>> copy('hello', -7)
   ''
   

3. Write a function double(s) that takes an arbitrary string s as input, and that uses recursion to construct and return the string formed by doubling each character in the string. Here are three examples:

   >>> double('hello')
   'hheelllloo'
   >>> double('python')
   'ppyytthhoonn'
   >>> double('')
   ''
   

4. Write a function dot(l1, l2) that takes as inputs two lists of numbers, l1 andl2, and uses recursion to compute and return the dot product of those lists – i.e., the sum of the products of the elements in the same positions in the two lists. For example, the dot product of [1, 2, 3] and [4, 5, 6] is 1*4 + 2*5 + 3*6 or 32.

   If the two lists do not have the same length or if either list is empty, dot should return 0.0. Here are some other examples:

   >>> dot([5, 3], [6, 4])     # get a decimal because the base case returns 0.0
   42.0
   >>> dot([1, 2, 3, 4], [10, 100, 1000, 10000])
   43210.0
   >>> dot([5, 3], [6])        # incompatible lengths
   0.0
   

   This function is somewhat similar to the the mylen function from lecture, but it needs to deal with lists instead of strings, and it needs to process two lists at the same time. You can find a modified version of mylen that handles both strings and lists here.

5. Write a function find_min(items), which uses recursion to find the minimum from a list of items.

   • For a list of numbers, the minimum will be the smallest number.

   • For a list of strings, the minimum will be the string closest to the start of the alphabet.

   Examples:

   >>> values = [14,8,7,12]
   >>> find_min(values)
   7
   >>> letters = ['z','h','e','l','m','c','s']
   >>> find_min(letters)
   'c'
   >>> values = [42]
   >>> find_min(values)
   42
   

   Hints:

   • Check for the base case! In a list with only one item, that item is the minimum.

   • Remember to use recursion on the remainder of the list, and do your one step to handle the value at the beginning of the list.

6. Write a function weave(s1, s2) that takes as inputs two strings s1 and s2 and uses recursion to construct and return a new string that is formed by “weaving” together the characters in the strings s1 and s2 to create a single string.

   In other words, the new string should alternate characters from the two strings: the first character from s1, followed by the first character from s2, followed by the second character from s1, followed by the second character from s2, etc.

   If one of the strings is longer than the other, its “extra” characters – the ones with no counterparts in the shorter string – should appear immediately after the “woven” characters (if any) in the new string.

   >>> weave('aaaaaa', 'bbbbbb')
   'abababababab'
   >>> weave('abcde', 'VWXYZ')
   'aVbWcXdYeZ'
   >>> weave('aaaaaa', 'bb')    # four extra 'a' characters at the end
   'ababaaaa'         
   >>> weave('aaaa', 'bbbbbb')  # two extra 'b' characters at the end
   'ababababbb'       
   >>> weave('aaaa', '')        # all of the 'a' characters are extra!
   'aaaa'       
   >>> weave('', 'bbbb')        # all of the 'b' characters are extra!
   'bbbb'       
   >>> weave('', '')        
   ''
   

   Hint: You will need more than one base case.

7. At the bottom of your a2task2.py file, add a __main__ section that includes at least one test call for each of the functions that you wrote for this problem. For example:

   if __name__ == '__main__':
       """ test function for the functions above """
       test1 = mult(6, 7)
       print('the first test returns', test1)
   

   This __main__ section does not require recursion. Also, remember that a __main__ section like this one does not need to return anything itself, because its only purpose is to call the other functions and print the results of those calls – and ensure that they are correct.

Submitting Your Work

Log in to GradeScope to submit your work.

Be sure to name your files correctly!

Under the heading for Assignment 2, attach each of the 2 required files to your submission.

When you upload the files, the autograder will test your program.

Notes:

• You may resubmit multiple times, but only the last submission will be graded.