**Homework 10: Sorting & Efficiency** **Reed CSCI 121 Spring 2025**   *complete the exercises by 9am on 4/15* The following exercises have a coding component and an analysis component. For each, you will write a function that performs some operation on a list and you will submit it (tested, and working) on Gradescope. In addition you will be asked to analyze the running time as a function of the length of the list it is given. In some cases, you will need to meet a target running time. In some other cases, you will get more points the more efficient your code runs. When a running time analysis is requested, include it in the comments of your code. These will be hand-graded, though an autograder might be built as part of our evaluation of that code. **Note on typing math:** There are standard ways to write mathematics in text. Use the caret symbol for exponentiation. Use `Theta` when you mean to write $\Theta$ for asymptotic notation. For example, if you would write $\Theta(n^2)$ in mathematical notation, you can write `Theta(n^2)` in the code. --- (##) `[Hw10 Ex1]` count ones Write a function `count_ones` that takes a *sorted* list containing only values of zero and one. It should return an integer that equals the count of the number of ones in that list. The code must be *efficient*: it should use $O(\log_2(n))$ time to compute that count, where $n$ is the size of the list. ~~~ none >>> count_ones([0,0,0,0,1,1]) 6 >>> count_ones([0,0,0]) 0 >>> count_ones([0]*10 + [1]*90) 90 >>> count_ones([]) 0 >>> count_ones([1]) 1 ~~~ Note that slicing a list takes time that is linear in the size of the slice, so you probably shouldn't use the slice operation. **Hint:** This should use a technique similar to binary search. (##) `[Hw10 Ex2]` selection sort In lecture tomorrow we will look at several sorting algorithms. Let's use this exercise to write the first. Selection sort works as follows: First, it scans through the list and finds the smallest value. It then swaps that value with the value at the start of the list. Having done that swap, the first element is properly placed. It then scans the list again, excluding the first element, to find the second smallest value. It swaps that value with the second element in the list. Having done that second swap, the first two elements are now correct. It continues in this way with more scans. Each scan finds the next lowest value and swaps it with the element where it should be placed. After enough scans, the whole list gets sorted. Write a function `selection_sort` that sorts the list it is given using selection sort. The function should not return anything. Instead, it should modify the list it is given, rearranging the items so that they are put in sorted order. What is the running time of this sorting algorithm? Include a comment in your code describing the (asymptotic) running time of `selection_sort` as a function of $n$, the number of elements in the list. (##) `[Hw10 Ex3]` count sort All the standard sorting algorithms we'll describe in lecture are *comparison based*. This means that they do all their work by comparing pairs of elements in the list they are given, arranging the values based on which is the smaller and larger of each pair. Here we consider an algorithm that doesn't perform its sorting based on pair-wise element comparisons. This algorithm, called *count sort*, is used in situations where a list contains integers drawn from a limited range. For example, the list ~~~ python [1, 2, 0, 0, 1, 3, 2, 1, 0, 1, 3, 3, 3, 1, 0, 1, 0] ~~~ only has values from 0 to 3. It works as follows: Assume that the numbers in our list are integers from 0 up to $m - 1$. There are two phases. In the first phase we scan through the list and count the number of occurrences of each integer in that list. This is done by making a list of counts `count` (of length $m$) where `count[i]` is the number of times that the value `i` occurs in the list we are sorting. It makes one pass through the list in order to figure out all these counts. For the list above, the `count` list is of length 4 and has the contents ~~~ python [5, 6, 2, 4] ~~~ because 0 appears five times, 1 appears six times, 2 appears twice, and 3 appears four times. In the second phase, we "rewrite" the list we are sorting to put things in the correct order. That is, we do the work to place the $m$ values in order into the list according to their counts. For the example list, this second phase places five 0s, six 1s, two 2s, and four 3s to obtain the list contents ~~~ python [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3] ~~~ Write the function `count_sort` that takes a list and a parameter $m$ describing the range of its values. (It can assume then that the list will have values from $0$ to $m-1$.) It should sort its contents using count sort. The function should not return anything. Instead, it should modify the list it is given, rewriting its values in sorted order. What is the running time of this sorting algorithm? Include a comment in your code describing the (asymptotic) running time of `count_sort` as a function of $n$, the number of elements in the list, and $m$, the size of its element range. --- --- In each of the next two exercises you are asked to write the code for a function. You should then also write an analysis of the running time of the function you have written. That is, you should say what its asymptotic runtime is, along with a short description of how you know that. Any correct solution that is correctly analyzed will get half of the hand-grade credit. However, there are multiple ways to write these functions, and they don’t all have the same (asymptotic) runtime. You will get the full credit if you find the fast ways of doing them. (##) `[Hw10 Ex4]` two sum The function `two_sum` takes a list of integers and a target value. It should return `True` if there are two numbers in the list that add up to the target value and `False` otherwise. For example ~~~ >>> two_sum([-4, 7, -2, 1, 3], -1) True >>> two_sum([-4, 7, -2, 1, 3], 6) False ~~~ The first result is because -2 and 1 (or -4 and 3) sum to -1. (##) `[Hw10 Ex5]` max slice sum The function `max_slice_sum` should take a list of integers. It should return the sum of a slice of the list that is the largest possible. For example, ~~~ >>> max_slice_sum([2, 1, -3, 4, -1, 2, 1, -5, 4]) 6 ~~~ because both `[4, -1, 2, 1]` and `[2, 1, -3, 4, -1, 2, 1]` have a sum of 6, and this is the largest possible. Your function should consider empty slices. Because both an empty list and an empty slice have a sum of 0, then ~~~ >>> max_slice_sum([]) 0 >>> max_slice_sum([-1]) 0 >>> max_slice_sum([-1,-2]) 0 ~~~ Note, for your design and for your analysis, that slicing a list takes time that is linear in the size of the slice.