15110 SUMMER SESSION TWO - 2014

Problem Set 5 - due Tuesday, July 15 at 9:00AM in class

Instructions

Type or neatly write the answers to the following problems.
Please STAPLE your homework before you hand it in.
On the first page of your homework, include your name, andrew ID and the assignment number.
You must hand in your homework at the start of class on the given due date.

Exercises

(1 pt) Wil Wheaton, child star of Star Trek: The Next Generation and currently appearing in The Big Bang Theory and The Wil Wheaton Project, shows off his new t-shirt below. Explain his t-shirt computationally.
(2 pts) You are given the following function in Python:
```
def f(n):
    if n == 0 or n == 1 or n == 2:
        return n
    else:
        return f(n-3) + f(n//3)
```
Trace the computation of f(9) by drawing a tree (like the one we drew for Fibonacci numbers), showing all of the computations that need to be computed to find the value for f(9). Then using your tree, compute the value of f(9).
(2 pts) In Python, in addition to non-negative indices, you can use negative index values when accessing list elements. These count backwards from the end of an list with -1 being an index for the last element in a list. The range notation for obtaining sub-lists can also use negative elements or a mix of positive and negative elements. For example:
```
>>> a = ["v", "w", "x", "y", "z"]
>>> a
["v", "w", "x", "y", "z"]
>>> a[-1]
"z"
>>> a[-2]
"y"
>>> a[-3]
"x"
>>> a[-3:-1]
["x", "y"]
>>> a[1:-2]
["w", "x"]
```
If we refer to integers whose 1's digit is 3 (3, 13, 23, 33, etc.) as "3-ending", then a recursive algorithm that takes a list of positive integers and counts the number of "3-ending" integers in that list can be described as follows:
1. If the list is empty, then the number of "3-ending" integers is 0.
2. Otherwise, if the last element of the list is not "3-ending", then the number of "3-ending" integers in the list is the number of "3-ending" integers in the list without the last element.
3. Otherwise (the last element of the list must be "3-ending"), the number of "3-ending" integers in the list is 1 plus the number of "3-ending" integers in the list without the last element.
Complete the Python function below to perform this computation recursively using the algorithm as specified above:
```
def count3ending(list):

    if ________________________:

        return 0

    if ____________________________________:

        return  ___________________________________

    else:

        return 1 + ____________________________________
```
Hint: you will want to use negative indices to obtain a list with all of the elements of list except the last element.
(1 pt) Suppose you try to use binary search on an unsorted list.
1. Give an example of a list of 7 unsorted elements where the key is in the list and binary search does find it by sheer luck. Identify the elements in the list that are examined by binary search to explain your answer.
2. Give an example of a list of 7 unsorted elements where the key is in the list but binary search would fail to find it. Identify the elements in the list that are examined by binary search to explain your answer.
(2 pts) Consider the list [16, 26, 55, 13, 21, 26, 31, 44] which we want to sort using merge sort as discussed in class.
1. Including the original call to msort to start the sorting, how many times is msort called to sort this list? Draw a recursion tree to explain your answer.
2. Show the final merge step that is performed that leads to the complete sorted list. First, show the contents of newlist1 and newlist2 after these 4-element sublists have been sorted. Then trace the merge function, step by step, similar to what is shown in the course slides to create the final sorted list.
(2 pts) Quicksort is another algorithm for sorting data. In this version of the algorithm, we compare all of the elements in the list to the middle element (list[len(list)//2]), which we will call the pivot. All of those that are less than the pivot go into one list and all of those that are greater than or equal to the pivot go into a second list. Then we sort these two sublists (recursively). The final sorted list is the first sorted sublist followed by the pivot followed by the second sorted sublist.
For example, if we want to sort the list
```
list = [56, 42, 82, 75, 18, 58, 27, 61, 84, 41, 21, 15, 71, 90, 33]
```
we create two lists, separating the elements based on the pivot 61:
```
list1 = [56, 42, 18, 58, 27, 41, 21, 15, 33]
list2 = [82, 75, 84, 71, 90]
```
Each sublist is sorted recursively (final results shown for each sublist):
```
list1 = [15, 18, 21, 27, 33, 41, 42, 56, 58]
list2 = [71, 75, 82, 84, 90]
```
and the final result is
```
[15, 18, 21, 27, 33, 41, 42, 56, 58] + [61] + [71, 75, 82, 84, 90]
=> [15, 18, 21, 27, 33, 41, 42, 56, 58, 61, 71, 75, 82, 84, 90]
```
Consider this Quicksort algorithm sorting a list of n integers.
1. Into what two sublists would this algorithm split the list [56, 42, 18, 58, 27, 41, 21, 15, 33] ?
2. This algorithm is recursive. What is the base case for this recursion? (In other words, when does Quicksort stop partitioning a list into two sublists?)
3. Explain when this algorithm would have an order of complexity of O(n log n). Give a simple example to justify your answer.
4. Explain when this algorithm would have an order of complexity of O(n²). Give a simple example to justify your answer.