Print every element in that list (`my_list`

) using a `for`

loop

The function `minimum(L)`

finds the minimum element in a list `L`

:

```
def minimum(L):
min_so_far = L[0]
for element in L:
if element < min_so_far :
min_so_far = element
return min_so_far
```

Now, write a function `maximum(L)`

that takes a list of integers `L`

and returns the largest integer in that list.

Write a **recursive** function `recursive_max(L)`

that takes a list of integers `L`

and returns the largest integer in that list.

In [ ]:

```
def min_index(L):
# Complete the function here!
return
print(min_index([1, 2, 3, 4]) == 0)
print(min_index([55, 66, 33, 22]) == 3)
```

Here is the iterative implementation of selection sort that you saw in lecture:

```
def selection_sort(L):
for i in range(len(L)):
min_idx = i + min_index(L[i:])
L[i], L[min_idx] = L[min_idx], L[i]
return L
```

Write a **recursive** function of selection sort called `recursive_sort(L)`

. Hint: you should use the function `min_index(L)`

from 2.1:

In [ ]:

```
def recursive_sort(L):
# Complete the function here
return
```

You're given the list `L = [1, 2, 4, 5]`

. Using slicing, insert the element `3`

in the list such that `L`

remains sorted.

In [ ]:

```
L = [1,2,4,5]
```

Write a function `less_print(L, k)`

that takes a sorted list `L`

and prints all the elements of `L`

that are less than `k`

.

Write a function `find_position(L, k)`

that finds the index of the greatest element in `L`

that is less that `k`

:

For example :

`find_position([1, 2, 4, 5], 3)`

should return `1`

because `2`

is the greatest element less than `3`

and is in index `1`

.

`find_position([9, 10, 11, 13, 14], 12)`

should return `2`

.

Using `find_position(L, k)`

, write a function `insert(k, L)`

that inserts `k`

into a sorted list `L`

so that the list stays sorted.

As input the function takes `k`

, the element to insert and `L`

, the sorted list to insert `k`

into.

For example:

```
insert(5, [4,6,8,9]) == [4,5,6,8,9]
insert(8, [2,5,6,9,10,34]) == [2,5,6,8,9,10,34]
```

Write a function `insertion_sort(L)`

that takes a list `L`

and inserts elements of `L`

in a new list using `insert(k,L)`

.

Here is how the function should work :

`L = [ 1, 4, 5, 3, 2, 7, 0]`

and `new_list = []`

`L = [ 4, 5, 3, 2, 7, 0]`

and `new_list = [1]`

`L = [ 5, 3, 2, 7, 0]`

and `new_list = [1, 4]`

`L = [ 3, 2, 7, 0]`

and `new_list = [1, 4, 5]`

`L = [ 2, 7, 0]`

and `new_list = [1, 3, 4, 5]`

`L = [ 7, 0]`

and `new_list = [1, 2, 3, 4, 5]`

`L = [ 0]`

and `new_list = [1, 2, 3, 4, 5, 7]`

`L = []`

and `new_list = [0, 1, 2, 3, 4, 5, 7]`

The **median** element of a list `L`

is the element that is smaller or equal to half of the elements in `L`

.

For example,

The median of `[1, 2, 4, 5, 6]`

is `4`

.

The median of `[7, 5, 4, 1, 3, 2, 4, 9, 9, 7]`

is `5`

.

Write a function `median(L)`

that takes a list `L`

and returns the median of the list `L`

.
Hint : The list `L`

is not sorted. You need to use your sort function from 3.1 (`recursive_sort`

)

In [ ]:

```
def median(L):
# Complete the function here
return
print(median([1, 2, 3]) == 2)
print(median([1]) == 1)
print(median([5, 4, 1, 4, 3]) == 4)
```

We want to sort a list of points (x, y) in a plane. For example `L = [[2, 3], [4, 5], [6, 3], [4, 0]]`

.

We define the order of the points as `[a, b] < [c, d]`

if `a+b < c+d`

. In other words, a point is smaller than an other point if the sum of x + y is smaller.

So according to this ordering, the list `[[4, 0], [2, 3], [6, 3], [4, 5]]`

is a sorted one.

Modify the function `min_index(L)`

from 2.1 so that `recursive_sort`

from 2.3 works for sorting points.

In binary search, we look for an element x in a **sorted list** by first comparing x to the midpoint of the list. If `x < midpoint`

, search the left half of the list. Otherwise, search the right half. Then repeat until we either find x or there are no elements to look through.

The code below can be used to play the *Guess The Number* game. Let's say you have a number x and you want your friend to guess it. They make a guess and then you tell them if your number is less, greater or equal to their guess.

Try playing the game by running the code below using different inputs.

In [ ]:

```
#This code returns the number of guesses made
def guess(x, left, right):
if x > right or x < left:
print("Invalid number!")
return -1
mid = (left+right)//2
print("My guess is:", mid)
if mid == x:
print("Exactly!\n")
return 1
if mid > x:
print("But that is too big!\n")
return 1 + guess(x, left, mid-1)
if mid < x:
print("But that is too small!\n")
return 1 + guess(x, mid+1, right)
print( guess(56, 1, 100) )
```

What are the **left** and **right** values for each of the 4 guesses made in `guess(56,1,100)`

?

What are the **left** and **right** values for each of the guesses made in `guess(1,1,100)`

?

Here is an implementation of binary search using a `while`

loop. Run this cell before continuing:

In [ ]:

```
def binarySearch(a, x):
computer_num = 3
cnt = 0
left = 0
right = len(a) - 1
while left+1!=right:
mid = (left+right)//2
cnt += 1
if a[mid] == x:
break
if a[mid] > x:
right = mid - 1
else:
left = mid + 1
print("Number of guesses:", cnt)
print("Your number is:", a[mid])
return cnt
binarySearch([1, 2, 4, 6, 7, 10], 4)
```

`[−1,3,6,10,15]`

if we are searching for `10`

what values of the array do we look at? Put a `print`

statement in the function `binarySearch`

above to check if you are correct.

What are the values of **left** and **right** for `binarySearch([-1, 0, 1, 3, 5, 7, 11], 5)`

?

What will happen if we run `binarySearch([1, 9, 8, -1, 4, 11], 4)`

? Why does this not work? How would you fix it?

Given a sorted list of strings `L`

, and an element in the list `t`

, write a function called `findInd(L, t)`

that uses binary search to determine the index of `t`

in `L`

.

`findInd(['ape', 'bubble', 'candy', 'tape', 'yellow', 'zebra'], 'tape') == 3`

`findInd(['ape', 'bubble', 'candy', 'tape', 'yellow', 'zebra'], 'zebra') == 5`

`findInd(['ape', 'bubble', 'candy', 'tape', 'yellow', 'zebra'], 'ape') == 0`

In [ ]:

```
def findInd(L, t):
# Complete the function here!
return
print(findInd(['ape', 'bubble', 'candy', 'tape', 'yellow', 'zebra'], 'tape') == 3)
print(findInd(['ape', 'bubble', 'candy', 'tape', 'yellow', 'zebra'], 'zebra') == 5)
print(findInd(['ape', 'bubble', 'candy', 'tape', 'yellow', 'zebra'], 'ape') == 0)
```

Given a list `L`

and a value `x`

, use a `for`

loop to find the index of the first time that `x`

appears in `L`

.
If `x`

does not appear in `L`

, return `-1`

.

You are given an unsorted list `L`

of nonnegative integers. For example,
`L = [200, 500, 30, 0, 1, 4]`

Find any number in the list that is greater than the numbers to the left and right of it.
Return the index of the number.
For example,
`localMax(L)`

should return `500`

.

The first element is a local max if it is greater than the second element. The last element is a local max if it is greater than the second to last element.

For example:

`L = [1, 2, 3, 4, 5]`

`localMax(L) == 5`

.

Hint: Use recursion.