ICS 33 Spring 2024, Exercise Set 2

Problem 2 (3 points)

Consider the following Python function, whose central job is to manipulate a list.


def do_something(x):
    for i in range(len(x) // 2):
        x[i], x[-1 - i] = x[-1 - i], x[i]

I've given the function an open-ended name, but, as a first order of business, see if you can figure out what problem it's meant to solve. (Yes, of course, I can't stop you from running the function in a Python shell to deduce what it does, but challenge yourself to figure it out without being told or shown the answer; that's how you learn the skill of reading code and building an understanding of what it does, which is a vitally important skill if you want to develop real-world software.)

Once you've figured out what problem the function solves by working out the details, you'll also have a pretty good understanding of how it solves the problem, which will allow you to answer the following questions about it — which are the only questions for which we're asking you to submit your answers.

If we say that the length of the list x is n, what is the closest-fit O-notation that best describes the amount of time it will take for this function to run? (You don't need to explain why; an O-notation is all we're looking for here.)
If we say that the length of the list x is n, what is the closest-fit O-notation that best describes the amount of memory required by this function? (You don't need to explain why; an O-notation is all we're looking for here.)
How would your answers to the first two questions above change if the function was written this way instead?
```
def do_something(x):
    result = []

    for i in range(len(x)):
        result.append(x[-1 - i])

    return result
```
In no more than a sentence or two each, briefly explain why your answer to each of the first two questions did or didn't change given the rewritten function.

What to submit

Submit one PDF named problem2.pdf, which succinctly answers the three questions above.

Problem 3 (2 points)

As we talked about when we discussed Asymptotic Analysis, O-notation is one of the most commonly used tools for analyzing how long an algorithm might take to run, how much memory it might require, and so on. Despite the fact that it's emerged as a go-to technique for this kind of analysis — and has remained in that lofty position for decades — it's important that we understand that O-notation has its limitations, two of which we discussed in that lecture:

Its mathematical definition allows us to dramatically overstate a result, by proving for example, that 3n² + 4n + 5 is O(n⁵). (We can overcome this limitation with the simple discipline of choosing the "closest-fit" result, so this is certainly no deal-breaker; let's ignore this issue, for the purposes of this problem.)
Even when we stick with a closest-fit result, O-notation considers many, many functions to be in the same category. Just because we know that two functions have the same closest-fit O-notation doesn't mean that we know that they're the same function.

To keep focused on the second of these issues, answer the following two questions about it.

Why do you think O-notation emerged as a popular technique for algorithm analysis, even though it categorizes functions so broadly?
Suppose that you've analyzed two algorithms and determined that the same closest-fit O-notation can be used to describe how long they'll take to run. What could you do next to determine which of the algorithms you should implement in practice?

What to submit

Submit one PDF named problem3.pdf, containing your answers to the two questions above.

Problem 4 (2 points)

During our recent conversation about Searching, we discussed the mechanics of how Python lists behave behind the scenes. One aspect of their behavior that we glossed over a bit, but that's worth considering in detail, is their management of spare capacity, which is to say that they routinely use more storage than they actually need. At first blush, this seems like a wasteful choice; why not use exactly and only what's needed at any given time? One way to understand why is to consider how well Python lists might work if they limited their memory usage as much as possible, contrasted with their actual behavior.

Suppose you had a Python list whose size and capacity are both n, and you then appended n additional elements to it, one at a time. Now, contrast the two scenarios, recalling that increasing the internal capacity of a list requires allocating a new block of memory, moving the contents of the old block into the new one, and then destroying the old one afterward.

Suppose that a list's capacity is always exactly its size. What would be the "closest-fit" O-notation for the amount of time necessary to perform all n append operations?
Suppose, instead, the list's capacity is doubled whenever full. What would be the "closest-fit" O-notation for the amount of time necessaty to perform all n append operations?

Justify each of your answers with no more than a sentence or two of explanation.

What to submit

Submit one PDF named problem4.pdf, containing your answers to the two questions above.

Problem 5 (1 point)

The provided implementation of binary_search from our conversation about Searching is sensitive to how the given list is sorted; it only works properly when given a list that's sorted into ascending order.

Suppose that you wanted to modify it so that it instead is capable of handling a list that's sorted into descending order instead. What is the minimum amount of change necessary to achieve this goal? Do not rewrite and submit the entire function. Instead, show only the lines that have changed; there's no need to explain the way in which they've changed.

For example, if you thought the right fix was to return 'Boo' instead of returning None on the last line, you would simply submit this — no more, no less.


return 'Boo'

What to submit

Submit one PDF named problem5.pdf, containing your modifications.

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.