ICS 33 Spring 2024
Exercise Set 6
Due date and time: Friday, May 24, 11:59pm
Getting started
First of all, be sure that you've read the Reinforcement Exercises page, which explains everything you'll need to know, generally, about how the reinforcement exercises will work this quarter. Make sure you read that page before you continue with this one.
Problem 1 (1 point)
Among the things we covered in our discussion of Inheritance was the use of the super notation, which solves what seems like a straightforward problem: Given a class Y that singly inherits from a class X, we can access an X.foo method from within the body of a Y.foo method by writing super().foo.
Of course, if we're authoring the class Y, then we know already that Y singly inherits from X, so we should also have been able to write some variant of X.foo instead of super().foo. This raises the question of why we need what seems like a heavier-weight notation like super().foo in place of the simpler X.foo instead.
Getting to the bottom of that issue will require us to learn one more thing that we've not yet discussed: How does super() behave in the presence of multiple inheritance? One way to understand that is through experimentation in the Python shell, so this problem asks you to construct such an experiment. (The goal here isn't to read the documentation and look up that behavior just to "be right"; the goal is to determine what you would need to try if you wanted to figure it out through experimentation.)
Perform an experiment in the Python shell that answers the following question.
- When a class inherits from more than one other class and uses super() to access a base class, what are the mechanics involved? (In other words, which base class method(s) are chosen? How are they chosen?)
For your experiment, assume that the Python shell begins fresh, and show the evaluation of each statement and its result, similar to how I've been doing in the Notes and Examples. Feel free to add a short sentence of commentary after each expression that you think needs it. In general, the goal here is similar to a problem you did in the previous set.
Follow your experiment with a few sentences that summarize what you've learned from it.
What to submit
Submit one PDF named problem1.pdf, which contains your experiment.
Problem 2 (4 points)
Background: What is a mixin class?
One of the main benefits offered by multiple inheritance is the ability to write what are sometimes called mixin classes, whose role is to provide a set of methods that can be shared by many classes, without imposing other design constraints on those classes. In other words, they act as a way to let us "copy and paste" methods (or other class attributes) into many other classes, but not much else. Most often, mixin classes will be made up only of methods or other class attributes, but will not make assumptions about the attributes of the objects on which those methods are called; that way, they can compatibly be inherited by many other classes, including in the presence of multiple inheritance.
As an example, consider this short mixin class; inheriting from it gives any class the ability to boo.
class Booer: def boo(self): return 'Boo!'
Inheriting from Booer adds that ability, but imposes no other constraints — Booer has no __init__ method, it doesn't use super(), and so on — which makes the following examples a safe and simple way to add the boo method to these classes.
class Person(Booer): # A Person object will have a boo() method def __init__(self, name, age): self._name = name self._age = age class Base: # A Base object will not have a boo() method def foo(self): return 13 class Derived(Booer, Base): # A Derived object will have a boo() method def bar(self): return 17
In the case of multiple inheritance involving mixins — where there's one "true" base class and additional mixins alongside it — we'll generally list any mixin classes first, then our "true" base class last, as I've done above with the Derived class. Since mixin classes tend not to offer the kinds of features that interact badly with the use of multiple inheritance, this lets them take precedence when their features are used, but stay out of our way otherwise.
There's no better way to understand a new technique than to put it to practical use, so let's try it.
The problem
In a Python module problem2.py, write a mixin class HashableByAttributes that provides one feature to any class that inherits from it: Making it hashable (in the Python sense that we've discussed previously) in a way that includes the values of all of its hashable attributes (while ignoring any others).
Once you've done that, write two additional classes in problem2.py that store different types of values in the attributes of their objects, though there's no particular requirement here about what the classes do. Inherit both of these classes from HashableByAttributes, so that they become hashable automatically, without you having to implement the functionality by hand.
Next, write a separate Python module named test_problem2.py, containing unit tests that test the behavior of your HashableByAttributes mixin class. (The two additional classes you wrote will help you to do that, and the fact that you'll be using those classes for testing purposes may help you to decide what features those classes might need.)
Limitations
The Python standard library is entirely off-limits in problem2.py. Your functions must not require any module to be imported.
The Python standard library is also entirely off-limits in test_problem2.py except for the use of the unittest module.
What to submit
Submit two Python scripts named problem2.py and test_problem2.py, which contain your solution to this problem as described above. Neither docstrings, comments, nor type annotations are required, since we've all agreed already on what problems we're solving here.
Problem 3 (3 points)
Let's revisit the problem of Searching, to see how the way we approach it might be different now that we've been Revisiting Recursion. If we search recursively, will it change the performance tradeoffs that arise when we face a problem like this? Let's find out.
Sequential search
Write a Python function named sequential_search that accepts two positional arguments, a collection and a search key, returning True if and only if an element in the collection is equivalent to the search key, or False otherwise. The collection can be anything iterable, but it must be traversed recursively, i.e., each call to the recursive function will only be permitted to interrogate one element, with any additional elements interrogated by additional recursive calls.
The time and memory requirements of your function, from an asymptotic perspective, should be as low as they can be made, given the constraints imposed by the problem and the fact that we're using Python to solve it. In other words, you shouldn't spend O(n3) time or memory if there's a way to spend O(n2) instead, but one O(n2) solution is as good as another, if that's as good as it gets. You'll need to decide whether a particular amount of time or memory is the minimum; we won't be willing or able to answer questions about that, since that's part of the problem we're asking you to solve here.
Underneath your function, write Python comments that answer the following three questions about it.
- What is the closest-fit O-notation that describes how much time is required to search a collection containing n elements? (You don't need to explain why.)
- What is the closest-fit O-notation that describes how much additional memory is required to search a collection containing n elements? (You don't need to explain why. Also, don't consider the memory used by the collection; we're only considering the memory needed specifically by your function.)
- How, if at all, would your closest-fit O-notations change if Python performed tail call elimination? (You don't need to explain why, but if your function can be written in a way that would improve your answer, make sure that it is.)
Binary search
Write a Python function binary_search that accepts two positional arguments, a collection and a search key, returning True if and only if an element in the collection is equivalent to the search key, or False otherwise. The collection is expected to be either a list or something that behaves like it (i.e., we expect to be able to ask it for a length, or to be able to index it with an integer), and to contain elements that are sorted in ascending order, but it must be traversed recursively, i.e., each call to the recursive function will only be permitted to interrogate one element, with any additional elements interrogated by additional recursive calls.
As with your previous function, your binary_search function must use as little time and memory (from an asymptotic perspective) as possible.
Underneath your function, write Python comments that answer the same three questions that you answered about your previous function.
- What is the closest-fit O-notation that describes how much time is required to search a collection containing n elements? (You don't need to explain why.)
- What is the closest-fit O-notation that describes how much additional memory is required to search a collection containing n elements? (You don't need to explain why. Also, don't consider the memory used by the collection; we're only considering the memory needed specifically by your function.)
- How, if at all, would your closest-fit O-notations change if Python performed tail call elimination? (You don't need to explain why, but if your function can be written in a way that would improve your answer, make sure that it is.)
Limitations
The Python standard library is entirely off-limits in this problem. Your function must not require any module to be imported.
What to submit
Submit one Python script named problem3.py, which contains your functions, along with your comments that answer the questions posed about each, and nothing else. Neither docstrings, comments, nor type annotations are required, since we've all agreed already on what problem we're solving here.
There is no credit being offered for writing automated tests — though you certainly might want to, since that's a great way to ensure that your code works as you expect — and we'd prefer you not submit them even if you do.
Problem 4 (2 points)
Write a Python function make_repeater, which requires exactly two positional arguments, which are as follows.
- The first positional argument is a repeatable function, which is one that can be called with only one positional argument, and whose result could safely be passed back into the same function as an argument.
- The second positional argument is a repeat count, a non-negative integer specifying how many times that function will be called.
The return value is a repeater function that itself requires one positional argument, an initial value, and calls the repeatable function the given number of times. The first time it's called, the initial value is passed to it; the second time it's called, the result of the first call is passed to it; the third time it's called, the result of the second call is passed to it; and so on. The result of the last call is the result returned by the repeater function.
Additionally, there are two performance requirements that must be met by your make_repeater function.
- Your make_repeater function must require O(1) memory to run.
- The repeater function returned by your make_repeater function must also require O(1) additional memory to run (i.e., independent of what the repeatable function does).
Here's an example of how you'd expect the function to behave when you're done with it.
>>> def square(n): ... return n * n ... >>> quadruple_square = make_repeater(square, 4) >>> quadruple_square(2) 65536 # square(square(square(square(2)))) = 65,536 >>> single_square = make_repeater(square, 1) >>> single_square(2) 4 # square(2) = 4 >>> do_nothing = make_repeater(square, 0) >>> do_nothing(2) 2 # No calls to square, because the repeat count was 0.
Limitations
The Python standard library is entirely off-limits in this problem. Your function must not require any module to be imported.
What to submit
Submit one Python script named problem4.py, which contains your function and nothing else. Neither docstrings, comments, nor type annotations are required, since we've all agreed already on what problem we're solving here.
There is no credit being offered for writing automated tests — though you certainly might want to, since that's a great way to ensure that your code works as you expect — and we'd prefer you not submit them even if you do.
Deliverables
In Canvas, you'll find a separate submission area for each problem. Submit your solution to each problem into the appropriate submission area. Be sure that you're submitting the correct file into the correct area (i.e., submitting your Problem 1 solution to the area for Problem 1, and so on). Under no circumstances will we offer credit for files submitted in the incorrect area.
Submit each file as-is, without putting it into a Zip file or arranging it in any other way. If we asked for a PDF, for example, all we want is a PDF; no more, no less. If you submit something other than what we asked for (e.g., a text file when we asked for a PDF, even if its filename ends in .pdf), we will not be offering you any credit on the submission. There are no exceptions to this rule.
Of course, you should also be aware that you're responsible for submitting precisely the version of your work that you want graded. We won't regrade an exercise simply because you submitted the wrong version accidentally.
Can I submit after the deadline?
Unlike some of the projects in this course, the reinforcement exercises cannot be submitted after the deadline; there is no late policy for these. Each is worth only 2% of your grade, with the lowest score dropped — see the Reinforcement Exercises page for details — so it's not a disaster if you miss one of them along the way.
You're responsible for making a submission in order to receive credit, which means you'll want to be sure that you've remembered to submit your work and verify in Canvas that it's been received. A later claim of having forgotten to submit your work or having misremembered the due date will not be grounds for a resubmission under any circumstances.
What do I do if Canvas adjusts my filename?
Canvas will sometimes modify your filenames when you submit them (e.g., by adding a numbering scheme like -1 or a long sequence of hexadecimal digits to its name). In general, this is fine; as long as the file you submitted has the correct name prior to submission, we'll be able to obtain it with that same name, even if Canvas adjusts it.