JamCoders

 💾 Download
In [ ]:
%config InteractiveShell.ast_node_interactivity="none"
def f(globals, locals):
    import base64
    code="ZGVmIG1ha2VfcHJpbnRfbG9jYWxzKCk6IAogICAgIyBJbiBhIGZ1bmN0aW9uIHRvIHByZXZlbnQgbG9jYWxzIGFuZCBpbXBvcnRzIGZyb20gbGVha2luZy4KICAgIGdsb2JhbCBtYWtlX3ByaW50X2xvY2FscwogICAgZGVsIG1ha2VfcHJpbnRfbG9jYWxzICAjIE9ubHkgcnVuIHRoaXMgZnVuY3Rpb24gb25jZS4KCiAgICBpbXBvcnQgSVB5dGhvbgogICAgaW1wb3J0IGFzdAogICAgaW1wb3J0IGluc3BlY3QKCiAgICBjbGFzcyBWaXNpdG9yKGFzdC5Ob2RlVmlzaXRvcik6CiAgICAgICAgZGVmIF9faW5pdF9fKHNlbGYpOgogICAgICAgICAgICBzZWxmLnZhcmlhYmxlcyA9IHNldCgpCiAgICAgICAgZGVmIHZpc2l0X05hbWUoc2VsZiwgbmFtZSk6CiAgICAgICAgICAgIHNlbGYudmFyaWFibGVzLmFkZChuYW1lLmlkKQogICAgICAgICMgVE9ETzogUG9zc2libHkgZGV0ZWN0IHdoZXRoZXIgdmFyaWFibGVzIGFyZSBhc3NpZ25lZCB0by4KCiAgICBBTExPV19UWVBFUyA9IFtpbnQsIGZsb2F0LCBzdHIsIGJvb2wsIGxpc3QsIGRpY3QsIHR1cGxlLCByYW5nZV0KICAgIGRlZiBmaWx0ZXJfdmFyaWFibGVzKHZhcmlhYmxlcywgbG9jYWxzKToKICAgICAgICBmb3IgdiBpbiB2YXJpYWJsZXM6CiAgICAgICAgICAgIGlmIHYgaW4gbG9jYWxzIGFuZCB0eXBlKGxvY2Fsc1t2XSkgaW4gQUxMT1dfVFlQRVM6CiAgICAgICAgICAgICAgICB5aWVsZCB2CiAgCiAgICAjIFVuZm9ydHVuYXRlbHksIHRoZXJlIGRvZXNuJ3Qgc2VlbSB0byBiZSBhIHN1cHBvcnRlZCB3YXkgb2YgZ2V0dGluZwogICAgIyB0aGUgY3VycmVudCBjZWxsJ3MgY29kZSB2aWEgdGhlIHB1YmxpYyBJUHl0aG9uIEFQSXMuIEhvd2V2ZXIsIGJlY2F1c2UKICAgICMgd2UgYXJlIGdldHRpbmcgY2FsbGVkIGZyb20gSVB5dGhvbiBpdHNlbGYgYW5kIHdlIGFyZSBhbHJlYWR5IGluc3BlY3RpbmcKICAgICMgdGhlIHN0YWNrdHJhY2UsIHdlIG1pZ2h0IGFzIHdlbGwganVzdCBwZWVrIGludG8gaXRzIGZyYW1lLi4uCiAgICBpZiBJUHl0aG9uLl9fdmVyc2lvbl9fID09ICI1LjUuMCI6CiAgICAgICAgIyBjb2xhYgogICAgICAgIGRlZiBnZXRfYXN0KGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGFzdC5Nb2R1bGUoZnJhbWUuZl9iYWNrLmZfYmFjay5mX2xvY2Fsc1sibm9kZWxpc3QiXSkKICAgICAgICBkZWYgZmluZF9sb2NhbHMoZnJhbWUpOgogICAgICAgICAgICByZXR1cm4gZnJhbWUuZl9sb2NhbHMKICAgICAgICBkZWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfYmFjay5mX2NvZGUuY29fZmlsZW5hbWUuZW5kc3dpdGgoIklQeXRob24vY29yZS9pbnRlcmFjdGl2ZXNoZWxsLnB5IikKCiAgICBlbGlmIElQeXRob24uX192ZXJzaW9uX18gPT0gIjguNC4wIjoKICAgICAgICAjIGxhYiBjb21wdXRlcnMKICAgICAgICBkZWYgZ2V0X2FzdChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBhc3QuTW9kdWxlKGZyYW1lLmZfYmFjay5mX2JhY2suZl9sb2NhbHNbIm5vZGVsaXN0Il0pCiAgICAgICAgZGVmIGZpbmRfbG9jYWxzKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfbG9jYWxzCiAgICAgICAgZGVmIGF0X3RvcF9sZXZlbChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBmcmFtZS5mX2JhY2suZl9jb2RlLmNvX2ZpbGVuYW1lLmVuZHN3aXRoKCJJUHl0aG9uL2NvcmUvaW50ZXJhY3RpdmVzaGVsbC5weSIpCiAgICBlbHNlOgogICAgICAgIHByaW50KGYicHJpbnRfbG9jYWxzKCkgbm90IHN1cHBvcnRlZCBvbiBJUHl0aG9uIHZlcnNpb24ge0lQeXRob24uX192ZXJzaW9uX199IikKCiAgICBkZWYgZ2V0X2NlbGxfbmFtZXMoZnJhbWUpOgogICAgICAgIHRyZWUgPSBnZXRfYXN0KGZyYW1lKQogICAgICAgIHZpc2l0b3IgPSBWaXNpdG9yKCkKICAgICAgICB2aXNpdG9yLnZpc2l0KHRyZWUpCiAgICAgICAgcmV0dXJuIGZpbHRlcl92YXJpYWJsZXModmlzaXRvci52YXJpYWJsZXMsIGZyYW1lLmZfbG9jYWxzKQoKICAgIGRlZiBmaW5kX3doaWNoKGZyYW1lKToKICAgICAgICAjIEZyYW1lIGlzIHRoZSBmcmFtZSB3aG9zZSBsb2NhbHMgd2UgYXJlIGludGVyZXN0ZWQgaW4gcHJpbnRpbmcuCiAgICAgICAgaWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgIyBUaGUgcGFyZW50IGZyYW1lIG9mIHRoZSBpbnRlcmVzdGVkIGZyYW1lIGlzIGEgbW9kdWxlLCBtb3N0IGxpa2VseQogICAgICAgICAgICAjICJpbnRlcmFjdGl2ZXNoZWxsIi4gVGhpcyBtZWFucyB3ZSBhcmUgaW4gdGhlIGdsb2JhbCBzY29wZSwgc2luY2UKICAgICAgICAgICAgIyBvbmx5IHRoZSBnbG9iYWwgc2NvcGUgc2hvdWxkIGJlIGRpcmVjdGx5IHJ1biBieSB0aGUgaW50ZXJhY3RpdmUgc2hlbGwuCiAgICAgICAgICAgIHJldHVybiBzZXQoZ2V0X2NlbGxfbmFtZXMoZnJhbWUpKQogICAgICAgICMgVGhlIHBhcmVudCBmcmFtZSBpcyBub3QgYSBtb2R1bGUsIHNvIHdlIGFyZSBpbiBhIGxvY2FsIHNjb3BlLgogICAgICAgIHJldHVybiBzZXQoZnJhbWUuZl9sb2NhbHMpCgogICAgZGVmIHByaW50X2xvY2Fscygqd2hpY2gsIHR5cGVzPUZhbHNlKToKICAgICAgICAiIiJQcmludCB0aGUgbG9jYWwgdmFyaWFibGVzIGluIHRoZSBjYWxsZXIncyBmcmFtZS4iIiIKICAgICAgICBpbXBvcnQgaW5zcGVjdAogICAgICAgICMgY3VycmVudGZyYW1lKCkgZnJhbWUgaXMgcHJpbnRfbG9jYWxzLiBXZSB3YW50IHRoZSBjYWxsZXIncyBmcmFtZQogICAgICAgIGZyYW1lID0gaW5zcGVjdC5jdXJyZW50ZnJhbWUoKS5mX2JhY2sKICAgICAgICBsb2NhbHMgPSBmaW5kX2xvY2FscyhmcmFtZSkKICAgICAgICB3aGljaCA9IHNldCh3aGljaCkgaWYgd2hpY2ggZWxzZSBmaW5kX3doaWNoKGZyYW1lKQogICAgICAgIGxsID0ge2s6IHYgZm9yIGssIHYgaW4gbG9jYWxzLml0ZW1zKCkgaWYgayBpbiB3aGljaH0KICAgICAgICBpZiBub3QgbGw6CiAgICAgICAgICAgIHByaW50KCJwcmludF9sb2NhbHM6IG5vIGxvY2FscyIpCiAgICAgICAgICAgIHJldHVybgogICAgICAgIGlmIHR5cGVzOgogICAgICAgICAgICBwcmludCgiXG4iLmpvaW4oZiJ7a306IHt0eXBlKHYpLl9fbmFtZV9ffSDihpAge3Z9IiBmb3IgaywgdiBpbiBsbC5pdGVtcygpKSkKICAgICAgICBlbHNlOgogICAgICAgICAgICBwcmludCgiOyAiLmpvaW4oZiJ7a30g4oaQIHtyZXByKHYpfSIgZm9yIGssIHYgaW4gbGwuaXRlbXMoKSkpCgogICAgcmV0dXJuIHByaW50X2xvY2FscwoKcHJpbnRfbG9jYWxzID0gbWFrZV9wcmludF9sb2NhbHMoKQ=="
    exec(base64.b64decode(code), globals, locals)
f(globals(), locals())
del f

def assertEqual(want, got):
    if want == got:
        print("Test case passed.")
        return

    print()
    print("--------- Test case failed. ---------")
    print(f"Want: {repr(want)} (type: {type(want).__name__})")
    print(f"Got:  {repr(got)} (type: {type(got).__name__})")
    print("-------------------------------------")
    print()

Week 3 Lecture 1b : Exercises

1. Insertion Sort

Insertion sort is a simple sorting algorithm. The general idea is to move all elements from the given list into a new list, while keeping the new list sorted. This is the pseudocode for a given list lst.

  1. Create a new empty list new_lst
  2. For each element x in lst, add x to new_lst -- while keeping new_lst sorted. More specifically, insert x immediately before the first element in new_lst that is larger than x.

For example if you want to sort the list,L = [8, 5, 7, 1, 9, 3] using insertion sort, it would look like this

L = [ 8, 5, 7, 1, 9, 3]; new_list = []
L = [ 5, 7, 1, 9, 3]; new_list = [8]
L = [ 7, 1, 9, 3]; new_list = [5, 8] since 5 is less than 8, we inserted it before 8.
L = [ 1, 9, 3]; new_list = [5, 7, 8] since 7 is greater than 5 but less than 8, we inserted it between 5 and 8.
L = [ 9, 3]; new_list = [1, 5, 7, 8]
L = [ 3]; new_list = [1, 5, 7, 8, 9]
L = [ ]; new_list = [1, 3, 5, 7, 8, 9]

1.1

The key challenge in implementing insertion sort is inserting elements from the original list lst int new_lst while keeping new_lst sorted; we'll need to manipulate new_lst using list slicing to insert each element into the correct position.

So first, let's go back and recall list slicing and concatanating. If you're given the list L = [1, 2, 4] and you want to insert the element 3 into the list such that L remains sorted, you can do

L = L[0:2] + [3] + L[2:] to get L = [1,2,3,4].

Why? Because L[0:2] = [1,2] and L[2:] = [4]. Therefore, L[0:2] + [3] + L[2:] is the same thing as [1, 2] + [3] + [4].

Below, you are asked to insert 7, 13, 17, and 23 in to the correct position in L (after all insertions, L should be sorted).

In [ ]:
L = [2, 5, 11, 15, 16, 19, 21]
In [ ]:
#Write your solution here. Insert 7, 13, 17 and 23.
In [ ]:
# TEST_CASE
expected = [2, 5, 11, 15, 16, 19, 21, 7, 13, 17, 23]
print(L == expected)

1.2

When we use insertion sort, we need to find the list of elements that are less than the element we are trying to insert so we can insert the element right after the elements that are less than it and add the rest of the elements after we add the new element. (Similar to what we did in 1.1) Get all the elements that are less than the numbers we are trying to insert, add the number and add the rest of elements.

Try to write a function less(L, k) that takes a sorted list L and returns a list of all the elements of L that are less than k.

For example, given a list [1, 4, 7, 9, 10] and k = 8, the function would return the list [1, 4, 7].

In [ ]:
def less(L, k):
    """Returns a list of elements from L that are less than k.
    Arguments:
        L (list of ints)
        k (int): An integer
    Returns: (sorted list of ints)
    Effects: None.
    """
    #Write your solution here
    return
In [ ]:
# TEST_CASE
L = [1, 4, 7, 9, 10, 13, 15]

k = 12
assertEqual(less(L, k), [1, 4, 7, 9, 10])

k = 0
assertEqual(less(L, k), [])

k = 16
assertEqual(less(L, k), [1, 4, 7, 9, 10, 13, 15])

1.3

Now let's write a function that is similar to the one we wrote in 1.3 but here instead of returning the list of elements that are less than k, let's return the index of the largest element that is less than k.

If we have a list, L = [1,2,5,7,9,13] and k = 10, the largest element that is less than 10 from the list L is 9, and the function should return the index of 9 that is 4.

If all the elements in L are greater than k, the function should return -1.

Now, write a function find_position(L, k) that finds the position of the greatest item in L that is less that k :
For example :

find_position([1, 2, 4, 5], 3) should return 1 because 2 is the greatest item less than 3 and is in position 1.
find_position([9, 10, 11, 13, 14], 12) should return 2.

In [ ]:
def find_position(L, k):
    """Returns the index of the greatest number that is less than k.
    Arguments:
        L (sorted list of ints)
        k (int)
    Returns: (int)
    Effects: None.
    """
    # Write your solution here
    return
In [ ]:
# TEST_CASE
L = [1, 2, 4, 5]
k = 3
assertEqual(find_position,(L,k), 1)

L = [9, 10, 11, 13, 14]
k = 12
assertEqual(find_position(L, k), 2)

L = [9, 10, 11, 13, 14]
k = 8
assertEqual(find_position(L, k), -1)

L = [9, 10, 11, 13, 14]
k = 15
assertEqual(find_position(L, k), 4)

1.4

Using find_position(L, k), write a function insert(L, k) that inserts k into a sorted list L. (Hint: what does find_position return?)

As input the function takes k, the element to insert and L, the sorted list to insert k into.

For example:

insert([4,6,8,9], 5)
  - Needs to find the position of the largest element that is less than 5(find_position)
  - Then insert 5 next to the largest element that is less than 5(which is 4)
  - Therefore the output should look like [4,5,6,8,9] 
insert([2,5,6,9,10,34], 8)(Think about the output of this one)
In [ ]:
def insert(L, k):
    """Inserts k at the right position in L where L remains sorted.
    Arguments:
        L (sorted list of ints)
        k (int)
    Returns: (sorted list of ints)
    Effects: Updates the List L.
    """
    #Write your solution here
    return
In [ ]:
# TEST_CASE
L = [4, 6, 8, 9]
k = 5
assertEqual(insert([4, 6, 8, 9], 5), [4, 5, 6, 8, 9])

L = [2, 5, 6, 9, 10, 34]
k = 35
assertEqual(insert(L, k), [2, 5, 6, 9, 10, 34, 35])

L = [2, 5, 6, 9, 10, 34]
k = 1
assertEqual(insert(L, k), [1, 2, 5, 6, 9, 10, 34])

1.5

WATCH THIS VIDEO (CLICK ME)

Here is the pseudo-code for insertion sort:

  1. Create an empty list, new_lst
  2. Then add the first element from L to new_lst
  3. Then add the rest of the elements to new_lst at the right location(Hint: Use insert(L, k))

Write a function insertion_sort(L) that takes a list L and inserts elements of L in a new list using insert(L, k).

Here is how the function should work :
L = [ 8, 5, 7, 1, 9, 3] and new_list = []
L = [ 5, 7, 1, 9, 3] and new_list = [8]
L = [ 7, 1, 9, 3] and new_list = [5, 8]
L = [ 1, 9, 3] and new_list = [5, 7, 8]
L = [ 9, 3] and new_list = [1, 5, 7, 8]
L = [ 3] and new_list = [1, 5, 7, 8, 9]
L = [ ] and new_list = [1, 3, 5, 7, 8, 9]

In [ ]:
def insertion_sort(L):
    """Sorts L using insertion sort algorithm(watch video).
    Arguments: L (list of ints)
    Returns: (list of ints)
    Effects: Sorts the list
    """
    #Write your solution here
    return
In [ ]:
# TEST_CASE
L = [1, 4, 5, 3, 2, 7, 0]
assertEqual(insertion_sort(L), [0, 1, 2, 3, 4, 5, 7])

L = [1, 4, 5, 3, 2, 0, 7]
assertEqual(insertion_sort(L), [0, 1, 2, 3, 4, 5, 7])

L = [5, 6, 11, 12, 13]
assertEqual(insertion_sort(L), [5, 6, 11, 12, 13])

L = [12, 11, 13, 5, 6]
assertEqual(insertion_sort(L), [5, 6, 11, 12, 13])

2. Selection Sort

Selection Sort works by finding the minimun element from the list L and swaping it with the first element.

  1. Find the smallest element from the list
  2. Swap it with the element at index 0
  3. Find the second smallest element and swap it with the element at index 1.
  4. Repeat until list is sorted.

For example,

L = [8, 5, 7, 1, 9, 3]
L = [1, 5, 7, 8, 9, 3] #Swapped 8 and 1
L = [1, 3, 7, 8, 9, 5] #Swapped 5 and 3
L = [1, 3, 5, 8, 9, 7] #Swapped 7 and 5
L = [1, 3, 5, 7, 9, 8] #Swapped 8 and 7
L = [1, 3, 5, 7, 8, 9] #Swapped 8 and 9

2.1

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

For example, in the list [66, 94, 71, 53] the result would be 3 since the smallest integer is 53.

In [ ]:
def min_index(L):
    """Returns the index of the smallest element in L.
    Arguments: L (list of ints)
    Returns: (int)
    Effects: None
    """
    # Write your solution here
    return


club_points_list = [66, 67, 71, 94, 95, 70, 53, 98, 96, 101, 88, 78]

print(min_index(club_points_list) == 6)
In [ ]:
# TEST_CASE

L = [2, 5, 98, 1, 0, 67]
assertEqual(min_index(L), 4)

M = [3, 6, 1, 0, 7, 9]
assertEqual(min_index(M), 3)

2.2

WATCH THIS VIDEO (CLICK ME)

Write a function, using a for loop, selection_sort(L) that takes a list L and sorts elements of L using selection sort.

Hint use: the min_index(L) function you defined above

Here is how the function should work :
L = [8, 5, 7, 1, 9, 3]
L = [1, 5, 7, 8, 9, 3]
L = [1, 3, 7, 8, 9, 5]
L = [1, 3, 5, 8, 9, 7]
L = [1, 3, 5, 7, 9, 8]
L = [1, 3, 5, 7, 8, 9]

Your code should work like this:

  1. Find the index of the smallest element from the list
  2. Swap it with the 0th element
  3. Then find the smallest element from the same list but without the first element (because it is the smallest and we want it right there)
In [ ]:
def selection_sort(L):
    """Sorts L using selection sort algorithm (watch video).
    Arguments:
        L (list of ints)
    Returns: (list of ints)
    Effects: Sorts the list
    """
    #Write Your Code Here
    return
In [ ]:
# TEST_CASE

L = [1, 54, 6, 7, 90, 0, 20]
expected = [0, 1, 6, 7, 20, 54, 90]

assertEqual(selection_sort(L), expected)

L = [2, 5, 3, 0, 91, 73, 56, 2, 93, 10, 10]
expected = [0, 2, 2, 3, 5, 10, 10, 56, 73, 91, 93]
assertEqual(selection_sort(L), expected)

L = [9, 5, 4, 9]
expected = [4, 5, 9, 9]
assertEqual(selection_sort(L), expected)

2.3

Write the same function but using recursion. (selection_sort_rec(L)).

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

For example, if you have an array [1, 3, 0, 2, 9] the output of the recursive sort function should be [0, 1, 2, 3, 9]

In [ ]:
def selection_sort_rec(L):
    """Sorts L using selection sort algorithm(watch video).
    Arguments:
        L (list of ints)
    Returns: (sorted list of ints) 
    Effects: Sorts the list
    """
    #Write your solution here
    return
In [ ]:
# TEST_CASE

L = [1, 54, 6, 7, 90, 0, 20]
expected = [0, 1, 6, 7, 20, 54, 90]

assertEqual(selection_sort_rec(L), expected)

L = [2, 5, 3, 0, 91, 73, 56, 2, 93, 10, 10]
expected = [0, 2, 2, 3, 5, 10, 10, 56, 73, 91, 93]
assertEqual(selection_sort_rec(L), expected)

L = [9, 5, 4, 9]
expected = [4, 5, 9, 9]
assertEqual(selection_sort_rec(L), expected)

3. Median Finding

The median element of a list L is the element whose value is "right in the middle" of the list; that is, it 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 1.1 (recursive_sort)

In [ ]:
def median(L):
    """Find the median in list L.
    Arguments: L (list of ints)
    Returns: (int)
    Effects: None
    """
    #Write your solution here
    return 

print(median(club_points_list) == 88)

print(median([1, 2, 3]) == 2)
print(median([1]) == 1)
print(median([5, 4, 1, 4, 3]) == 4)
In [ ]:
#TEST_CASE
L=[7, 5, 4, 1, 3, 2, 4, 9, 9, 7]
assertEqual(median(L), 5)

M=[4, 6, 78, 90, 12, 43, 9]
assertEqual(median(M), 12)

4. Sorting points (optional)

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 the coordinates is smaller. ([2,3] > [3,0], because 2+3 > 3+0)

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 [ ]:
def sort_points(L):
    """Sorts L.
    Arguments:
        L (list): A list that contains points([x, y] coordinates).
    Returns: (list) the sorted list.
    Effects: Sorts the list
    """
    #Write your solution here
    return
In [ ]:
# TEST_CASE

L = [[2, 3], [4, 5], [6, 3], [4, 0]]
expected = [[4, 0], [2, 3], [6, 3], [4, 5]]
assertEqual(sort_points(L), expected)


L = [[0, 3], [3, 0], [2, 1], [1, 2]]
expected = [[0, 3], [3, 0], [2, 1], [1, 2]]
assertEqual(sort_points(L), expected)