15110 SUMMER SESSION ONE - 2013

Problem Set 5 - due Monday, June 3 at 10:30AM in class

Reading Assignment

Read sections 5.1-5.6 in chapter 5 of the textbook Explorations in Computing.

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) Write a recursive Ruby function sum_positive(n) that has one parameter n that represents a positive integer. The function should return the sum of the first n positive integers. Your solution must use recursion and should not have a loop in it.
For example, if we call sum_positive(5), then the function should return the value 15 since 1 + 2 + 3 + 4 + 5 = 15.
HINT: The solution is very similar to the factorial function we did in class. Think about how factorial and sum_positive differ.
(2 pts) You are given the following recursive function in Ruby:
```
def f(n)
	if n == 0 or n == 1 or n == 2 then
		return n
	else
		return f(n-3) + f(n/3)
	end
end
```
Trace the computation of f(9) by drawing a recursion tree (like the one we drew for Fibonacci numbers), showing all of the recursive computations that need to be computed to find the value for f(9). Then using your recursion tree, compute the value of f(9).
(2 pts) In Ruby, in addition to non-negative indices, you can use negative index values when accessing array elements. These count backwards from the end of an array with -1 being an index for the last element in an array. The range notation for obtaining sub-arrays can also use negative elements or a mix of positive and negative elements. For example:
```
>> a = ["v", "w", "x", "y", "z"]
=> ["v", "w", "x", "y", "z"]
>> a[-1]
=> "z"
>> a[-2]
=> "y"
>> a[-3]
=> "x"
>> a[-3..-1]
=> ["x", "y", "z"]
>> a[1..-3]
=> ["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 Ruby function below to perform this computation recursively using the algorithm above:
```
def count3ending(list)

	if ________________________ then

		return 0

	end

	if ____________________________________ then

		return  ___________________________________

	else

		return 1 + ____________________________________
	end
end
```
Hint: you may want to use negative indices to obtain an array with all of the elements of list except the last element.
(1 pt) Suppose you try to use binary search on an unsorted array.
1. Give an example of an array of 7 unsorted elements where the key is in the array and binary search does find it by sheer luck. List what elements in the array that are examined by binary search to explain your answer.
2. Give an example of an array of 7 unsorted elements where the key is in the array but binary search would fail to find it. List the elements in the array that are examined by binary search to explain your answer.
(2 pts) Consider the array [16, 26, 55, 13, 21, 26, 31, 44] which we want to sort using merge sort:

Merge Sort Algorithm:
1. Sort the first half of the array using merge sort.
2. Sort the second half of the array using merge sort.
3. Merge the two sorted halves to get a sorted array.
1. Show the list after step 1 of the algorithm is completely done. (THINK: This should be easy. You don't have to show all the steps... just show the final result.)
2. Show the list after step 2 of the algorithm is completely done. (THINK: This should be easy. You don't have to show all the steps... just show the final result.)
3. Show the merge process of step 3 by tracing this step as shown in the course slides/notes.
4. Explain why this algorithm is recursive. What is its base case?
(2 pts) Quick sort 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[list.length/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 quick sort 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 quick sort stop partitioning a list into two sublists?) BE CAREFUL: This is a little trickier than it seems.
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.