HW 12 (Searching and sorting)

This assignment is a problem set (no coding). You'll legibly handwrite or type your solutions, and submit your answers as a PDF.

1. List each item I will compare to (in order) if I'm using binary search to look for "June" in the following list:

   lst = ["January", "July", "March", "May", "November", "September"]
   

   Assume that I use integer division len(lst)//2 to compute the middle index (this means that if the list has an even number of items, I will compare with the larger of the two middle items).

2. What is the big-O running time of the following function in terms of n, where n is the length of someList? (Recall that to find the big-O running time, you count how many operations will be completed in terms of n and (e.g., how many times a particular line inside of a nested for loop will be reached) and then remove any constants).

   def mystery(someList):
       total = 0
       for i in range(len(someList)):
           for j in range(len(someList)):
               total = total + 2 * someList[i]
   
       for i in range(len(someList)):
           print(total + someList[i])
   
       return total
   

3. Both selection sort and insertion sort have an outer loop that iterates through the whole list. Suppose we're sorting the following list:

   lst = [63, 27, 54, 72, 90, 99, 45, 18]
   

   Write down what lst looks like at the end of each iteration of the outer loop for (a) insertion sort and (b) selection sort. You should have a sequence of lists for each part (a) and part (b) and the final list in each sequence should be fully sorted.

4. Show how merge sort would sort the same list:

   lst = [63, 27, 54, 72, 90, 99, 45, 18]
   

   In your answer, you should tell me what each step of the sorting process is (what part of the list are you working with, and what's its current order?) For example, if I were to explain how [78, 38] is sorted using merge sort, I would say that we recurse on the first half of the list and on the second half. The first half is [78] which is trivially sorted because it has length 1. Same with the second half of the list, [38]. Then we merge the two sorted lists [78] and [38] to form the list [38, 78]. Your explanation doesn't need to keep reporting all of the same details, but you should tell me at a minimum what lists are being merged together in what order. The latter part could be conveyed by drawing a tree diagram and labeling with numbers what order the steps occur in.

When you finish, add acknowledgements and a reflection to your work.

You'll need to hand in a PDF on Gradescope. If you're working in Google Docs or Microsoft word, there should be an option to export your file as a PDF. You can also go to print the document, and then (on the Mac dialogue in the lab computers) in the lower left corner, select PDF.

If you've handwritten your responses, you can scan it via an on-campus printer, or take a picture and paste those into a PDF. (You can also do this option if you're typing some of the results and handwriting others, e.g., diagrams.) Please make sure your work is legible! (Both your handwriting and the quality of the scan/photo)

This assignment was adapted from Anna Rafferty's and Layla Oesper's teaching materials. Thanks for sharing!