Simple List Algorithms

In this project we implement simple algorithms related to lists like sorting a list or finding special values. The purpose of the projecct is threefold:

• familiarize yourself with Python’s syntax,

• learn to algorithmize, that is, how to combine available building blocks to solve a task,

• see and understand how basic algorithms frequently used in data science work.

Before you work through the project you should have read Building Blocks. Restrict yourself to Python features discussed there. Don’t use ready-made library functions.

Important

Don’t use list as name for a variable holding some list, although this would be quite expressive. Several names like print and int and list are already occupied by Python. Python won’t complain about reusing some of it’s predefined names as variables, but it’s considered bad practice.

Maxmium of a List

Given a list of integers we want to find the list’s greatest value.

Task: Describe a process (that is, algorithm) to find the maximum value of a list in your words, not Python code. Remember that the list may be of arbitrary length. For simplicity you may assume that the list is not empty.

Solution:

# your solution

Task: Implement your algorithm in Python. Proceed as follows:

1. Create a function get_max which takes a list as argument and, for the moment, always returns the length of the list.

2. Create a sample list, pass it to your function, and print the returned value to the screen.

3. If the framework is working correctly, implement your algorithm in get_max and make the function return the maximum value.

4. Test your code with several different sample lists. Include pathological cases like [1, 1, 1] and [1].

Solution:

# your solution

Task: What happens if you test your code with an empty list? Now add some code to your function to check whether the list is empty. If the list is empty get_max should print a message and return 0.

Solution:

# your solution

Mean of a List

Given a list of floats we want to find the list’s mean.

Task: Describe an algorithm for calculating the mean of a list. Assume that the list has at least one item.

Solution:

# your solution

Task: Implement your algorithm in Python. Proceed as follows:

1. Create a function get_mean which takes a list as argument and, for the moment, always returns the length of the list.

2. Create a sample list, pass it to your function, and print the returned value to the screen.

3. If the framework is working correctly, implement your algorithm in get_mean and make the function return the list’s mean.

4. Test your code with several different sample lists. Include obvious cases like [-1, -1, 1, 1] and pathological cases like [1].

Solution:

# your solution

Task: What happens if you test your code with an empty list? Now add some code to your function to check whether the list is empty. If the list is empty get_mean should print a message and return 0.

Solution:

# your solution

Count Values

Given a list of integers we want to count how often a given integer occurs in the list.

Task: Write a function count_value taking two arguments (the list and an integer) and returning the number of occurrences of the integer in the list. Proceed step by step as before. How to handle empty lists here?

Solution:

# your solution

Sorting a List

There exist plenty of algorithms for sorting values in lists. Here we consider selection sort for sorting a list of integers.

Fig. 88 Selection sorts devides the list into two parts: sorted items and unsorted items. It repeatedly walks (blue) through the unsorted items to find the smallest (red) unsorted item. Then it swaps the first unsorted item with the smallest unsorted item. The swapped item then belongs to the sorted part (yellow). Source: Joestape89, wikipedia.org, CC BY-SA 3.0, modified by the author.

Task: Write a function sort taking a list and returning the sorted list. Proceed step by step as before. Don’t forget to extensively test your code!

Solution:

# your solution