1. In a recursive function, the ______________ identifies when to stop.
2. Put the following complexity classes in order from the most efficient to the least efficient.
3. Given the following algorithm for selection sort, which complexity class does this algorithm belong to?
Selection_sort(A)
for i = 1 to A.length
min = i
for j = i + 1 to A.length
if A[j] < A[min]
min = j
#end for
swap A[i], A[min]
# end for
4. Select the best answer.
A higher-order function is a function that
5. We discussed Python sequences and protocols this semester. Which of the following is NOT a Python sequence? (hint: all sequences are "sliceable")
Questions 6 to 11 are coding questions.
6. Higher Order. You will write THREE (3) short functions for this question.
Write the following three functions as specified in sections (a) (b) and (c) below. All three functions should mutate the list that is passed to them. All functions are side- effect functions; none of them should return a value.
(a) Provide a function named add_value that takes two parameters. The first parameter is a list of numbers (ints or floats) and the second parameter is the value that will be added to each element of the list. This function mutates the list by adding the second parameter to each element of the list and storing the new values in the indices where the old values were.
Given: add_value(lst, val) and a list named lst with the elements [1, 2, 3]
Example: A call to add_value(lst, 1) would result in lst holding the values: [2, 3, 4]
(b) Provide a function named multiply_value that takes two parameters. The first parameter is a list of numbers (ints or floats) and the second parameter is the value that will be multiplied to each element of the list. This function mutates the list by multiplying the second parameter to each element of the list and storing the new values in the indices where the old values were.
Given: multiply_value(lst, val) and a list named lst with the elements [1, 2, 3]
Example: A call to multiply_value(lst, 2) would result in lst holding the values: [2, 4, 6]
(c) Provide a function named higher_order that takes three parameters. The first parameter is a list of numbers (ints or floats) and the second parameter is the value that will be applied in a mathematical operation to each element of the list. The third parameter is going to be one of the two functions you wrote for (a) and (b), which will implement the mathematical operation. This function mutates the list by applying the function to each element of the list and storing the new values in the indices where the old values were.
Given: higher_order(lst, val, function) and a list named lst with the elements [1, 2, 3]
Example: A call to multiply_value(lst, 2, multiply_value) would result in lst holding the values: [2, 4, 6]
7. Flip Lists.
Write a function that takes as input a list that contains nested lists. Each of the nested lists have two (2) elements each (we'll call them "pairs"). For each pair (nested list), swap the values in the pair. This function should mutate the original list passed in. Specification:
8. Write a class named Rectangle that meets the following specifications. The detailed spec is below:
Given the following Point class (copy the code for this into your exam solution and use it for this question):
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def get_x(self):
return self.x
def get_y(self):
return self.y
Create a class named Rectangle that does the following. Remember: spelling of your methods and class must follow the specification precisely!
You need to provide an appropriate constructor, area method, __eq__ method, and a method named contains.
Users of your class should be able to create new instances of Rectangle using your constructor/initializer by passing it an x, y coordinate position which represents the lower left corner of the Rectangle, a width for the Rectangle, and a height for the Rectangle.
If the width or the height specified during creation is less than or equal to zero (<=0) raise a ValueError exception
Example: r = Rectangle(0, 1, 2, 3) # create a Rectangle with lower corner at (x=0, y=1), width == 2 and height == 3
Example: r = Rectangle(0,1, 0, 0) # raise a ValueError
Your Rectangle also must provide the following three methods:
area(): returns the area of the Rectangle. (fyi: Area is width * height)
Example: r.area()
contains(a_point) : Determines if an instance of the Point class (given previously) resides "inside" of the Rectangle, based on cartesian coordinates for both. Returns True or False depending on if the point is considered "inside" the rectangle or not. For the purpose of this question, you can assume points that fall on the line of a Rectangle are considered to be "inside" the Rectangle.
Example:
r = Rectangle(0, 0, 2, 2)
p = Point(1, 1)
r.contains(p) # True
p = Point(-1, -1)
r.contains(p) # False
__eq__(other) : Determines if two Rectangles are equal to each other. For this question, equality is determined by simply comparing the area of both rectangles (no other comparisons are needed). If the areas are equal, two rectangles are considered equal.
Example:
r = Rectangle(-2, -2, 4, 4)
r2 = Rectangle(0, 0, 2, 2)
r == r2 # False
9. Recursive Ducks
The Python loop below should look familiar. We used it earlier in the semester to print the words Jack, Kack, Lack, and Mack to the terminal.
prefixes =
"JKLM"
suffix =
"ack"
for pre in
prefixes:
print(pre +
suffix)
Of course, that's an iterative solution. For this question, write a recursive function called ducks that accepts a dictionary and two strings (prefixes and suffix) that adds to, or updates the dictionary by using each letter in the prefixes as a key in the dictionary, and the suffix as the value in the dictionary. If a key already exists in the dictionary, update the value accordingly. Do NOT hardcode your solution - we may pass different prefixes and suffixes besides our friendly duck names when we test your code. You must provide a recursive solution for this problem to earn credit.
Example
dictionary = {}
ducks(d, "JKLM", "ack") # results in the dictionary containing {'J': 'ack', 'K': 'ack', 'L': 'ack', 'M': 'ack'}
10. Write a function that meets the following specifications.
Write a function named is_missing that accepts a list of n-1 unsorted integers, which are known to be in the range 1 through n. But since there are only n-1 things in the list, some number in is missing. Your function returns the value of the missing number.
You are allowed to use the built-in sorting functions if you wish to do so (you are NOT required to). Regardless of your choice, you should be aware of the implications on time complexity from the standpoint of upper-bound (Big-Oh),
Example:
lst = [2, 3, 4]
is_missing(lst) # returns 1
| Example Inputs to your Function | Expected Result |
| [2, 3, 4] | 1 |
| [4, 1, 3, 6, 7, 2] | 5 |
| [4, 1, 3] | 2 |
| [1] | 2 |
11. Write a function that meets the following specifications.
Palindromic numeric ambigram
A palindrome is a word, phrase or number that reads the same forwards and backwards. An ambigram something (such as an image of a written word or phrase) 2 Quiz saved at 6:43pm Upload that is intended or able to be oriented in either of two ways for viewing. When you flip an ambigram upside down, it can create the same image OR another word.
For example, with a specialized font, the word "ambigram" is an ambigram when you rotate it 180 degrees.
As another example, the word "mom" becomes "wow" when rotated.
For this question, we're keeping it simple and going to limit ourselves to integers only. We will use the following "digital clock" number font for illustration
1 2 3 4 5 6 7 8 9 0
Given this, the numbers 1, 2, 5, 8 and 0 are exactly the same if they are rotated 180 degrees in either direction.
Write a function that meets the following specifications: