Programming with Python (exercises)

Stefan Güttel, guettel.com

(based on course notes written by Vedran Šego, vsego.org)

Exercises: Lists

A note on testing the programs with lists

You can load a list of numbers using one of several methods. For example, you can load a list of integers like this:

L = list()
n = int(input("The number of list elements: "))
for k in range(n):
    L.append(int(input(str(k+1) + ". element: ")))

However, while testing your program, it gets boring to retype the list with each run. Instead of the above, do this:

def load_a_list_of_ints():
    """
    Loads a list of integers by first asking for its length.
    """
    L = list()
    n = int(input("The number of list elements: "))
    for k in range(n):
        L.append(int(input(str(k+1) + ". element: ")))
    return L

#x = load_a_list_of_ints()
x = [ 17, 23, 11, 13, 19 ]
the_rest_of_your_code()

In other words, make an input function (load_a_list_of_ints in the above example), comment out its call

#x = load_a_list_of_ints()

and set a fixed value for the list:

x = [ 17, 23, 11, 13, 19 ]

After your code works properly for that one example, you can try a few more by changing the value of x.

In the end, remove or comment out the fixed value of x:

#x = [ 17, 23, 11, 13, 19 ]

uncomment the input, i.e., remove # from #x = load_a_list_of_ints() so you get

x = load_a_list_of_ints()

and test that the program properly loads a list and does with it what needs to be done.

Of course, the same approach can be used with the other input methods that we've seen in lectures. Furthermore, the break statement (which we shall see later on) in some of those can be replaced with return L.

The problems

Problem 1. Without using Python's built-in functions for reversing lists, write your own function my_reverse that accepts a single parameter L (a list) and reverses its elements.

Hint: Swap the first and the last element, then the second and the second to last, etc. Where should this swapping stop?

Problem 2. Without using Python's built-in functions for reversing lists, write your own function my_reverse that accepts a single parameter L (a list) and returns a new list with the same elements but in a reverse order. The list L has to remain unchanged.

Problem 3. Without using Python's built-in functions for sorting lists, write your own function my_sort that accepts a single parameter L (a list) and sorts it.

Hint: How would you sort a sequence of numbers IRL (in real life) if you had them each written on its own piece of paper?

One way to do it: take a look at the first, the second,... $k$-th number. For each of them find the smallest one behind it. Then swap that one with the $k$-th one (unless the $k$-th one is that smallest one), and move to the next, $(k+1)$-th one. This is called selection sort.

Note: This is an exercise in list manipulations. When sorting in Python, always use its own sorting functions, as these implement much faster algorithms.

Problem 4. Without using Python's built-in functions for sorting lists, write your own function my_sort that accepts a single parameter L (a list) and returns a new list with the same elements but in an ascending order. The list L has to remain unchanged.

Problem 5. Write a function that takes two parameters: a sorted list L (you don't have to check that it is sorted) and a variable el. The function has to return None if el is not in the list, or its index if it is.

Do not use sets and similar methods, nor Python's built-in functions like index.

Instead, implement a binary search algorithm. This is the same algorithm that you use when searching for something in a sorted index at the end of a book: look at the middle term and decide where to look next (to the left or the right) and proceed until the element is found or you realize that it doesn't exist. Each step cuts the number of candidates in half (so, a list with $2^{\color{red}{10}} = 1024$ elements is searched in at most $\color{red}{10}$ steps).

Searching the internet for a simple explanation of how it works would probably be useful here.

Note: Python has a module bisect which, as its documentation says, provides support for maintaining a list in sorted order without having to sort the list after each insertion. However, it can also be used for binary search.

Further help

Detailed explanations of the solutions for the problems in this exercise are given in the lab classes notes.