ICS 33: Intermediate Programming with Python

Due date and time: Friday, April 19, 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 (2 points)

Use the definition of O-notation from the Asymptotic Analysis lecture to prove whether the following statement is true.

• Is it true that the function 6n² + 16 is O(n²)?

What to submit

Submit one PDF named problem1.pdf, which contains your proof.

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.

1. 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.)
2. 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.)
3. 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.

1. Why do you think O-notation emerged as a popular technique for algorithm analysis, even though it categorizes functions so broadly?
2. 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.

1. 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?
2. 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.