Lecture 10 : Exercices

1. List review

1.1

Create a list called my_list that contains 5 integer values.

1.2

Print every element in that list (my_list) using a for loop

1.3

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.

1.4

Write a recursive function recursive_max(L) that takes a list of integers L and returns the largest integer in that list.

2. Selection Sort

2.1

Write a function min_index(L) that takes a list L and returns the index of the smallest integer in L. Hint: you should use a for loop!

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)

2.2

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

2.3

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

3. Insertion Sort

3.1

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]

3.2

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.

3.3

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.

3.4

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]

3.5

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]

4. Median Finding

4.1

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)

5. Sorting points (optional)

5.1

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.

6. Binary search

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) )

2.2

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

2.3

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)

3.1

Given the array [−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.

Type your answer here:

3.2

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

Type your answer here:

3.3

What will happen if we run binarySearch([1, 9, 8, -1, 4, 11], 4)? Why does this not work? How would you fix it?

Type your answer here:

4.

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)

Optional Challenge Problems:

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.

Local maximum.

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.