Lesson_00_algorithms


Python Training - Lesson 0 - algorithms

Before we start writing code, we should first understand how to solve problems using well defined steps and procedures. Let me give you an example.

Example algorithm - sort numbers

Sort a list of numbers so that they are in a growing sequence. List : 27,2,1,63,8,26,3,2,8,1,3,3,4

Let's write some steps for a classic bubble sort.

Take the first pair. 27 and 2

If the second one is higher, leave it.

If it is lower, switch them.

Do this until they are sorted.

If you reach the end of list, go again, do another pass.

Now, most of the work is done. It's enough to solve the problem. To make it automatic, we need to write pieces of code for each of the steps. The tools you need to know will be covered later in the course, for now just look at how simple a Python program could be.


In [1]:
def bubble_sort(alist):
    for pass_number in range(len(alist)-1,0,-1):
        for i in range(pass_number):
            left, right = alist[i], alist[i+1]

            if left > right:
                left, right = right, left
            
            alist[i], alist[i+1] = left, right
                
            print(alist)

In [2]:
bubble_sort([27,2,1,63,8,26,3,2,8,1,3,3,4])


[2, 27, 1, 63, 8, 26, 3, 2, 8, 1, 3, 3, 4]
[2, 1, 27, 63, 8, 26, 3, 2, 8, 1, 3, 3, 4]
[2, 1, 27, 63, 8, 26, 3, 2, 8, 1, 3, 3, 4]
[2, 1, 27, 8, 63, 26, 3, 2, 8, 1, 3, 3, 4]
[2, 1, 27, 8, 26, 63, 3, 2, 8, 1, 3, 3, 4]
[2, 1, 27, 8, 26, 3, 63, 2, 8, 1, 3, 3, 4]
[2, 1, 27, 8, 26, 3, 2, 63, 8, 1, 3, 3, 4]
[2, 1, 27, 8, 26, 3, 2, 8, 63, 1, 3, 3, 4]
[2, 1, 27, 8, 26, 3, 2, 8, 1, 63, 3, 3, 4]
[2, 1, 27, 8, 26, 3, 2, 8, 1, 3, 63, 3, 4]
[2, 1, 27, 8, 26, 3, 2, 8, 1, 3, 3, 63, 4]
[2, 1, 27, 8, 26, 3, 2, 8, 1, 3, 3, 4, 63]
[1, 2, 27, 8, 26, 3, 2, 8, 1, 3, 3, 4, 63]
[1, 2, 27, 8, 26, 3, 2, 8, 1, 3, 3, 4, 63]
[1, 2, 8, 27, 26, 3, 2, 8, 1, 3, 3, 4, 63]
[1, 2, 8, 26, 27, 3, 2, 8, 1, 3, 3, 4, 63]
[1, 2, 8, 26, 3, 27, 2, 8, 1, 3, 3, 4, 63]
[1, 2, 8, 26, 3, 2, 27, 8, 1, 3, 3, 4, 63]
[1, 2, 8, 26, 3, 2, 8, 27, 1, 3, 3, 4, 63]
[1, 2, 8, 26, 3, 2, 8, 1, 27, 3, 3, 4, 63]
[1, 2, 8, 26, 3, 2, 8, 1, 3, 27, 3, 4, 63]
[1, 2, 8, 26, 3, 2, 8, 1, 3, 3, 27, 4, 63]
[1, 2, 8, 26, 3, 2, 8, 1, 3, 3, 4, 27, 63]
[1, 2, 8, 26, 3, 2, 8, 1, 3, 3, 4, 27, 63]
[1, 2, 8, 26, 3, 2, 8, 1, 3, 3, 4, 27, 63]
[1, 2, 8, 26, 3, 2, 8, 1, 3, 3, 4, 27, 63]
[1, 2, 8, 3, 26, 2, 8, 1, 3, 3, 4, 27, 63]
[1, 2, 8, 3, 2, 26, 8, 1, 3, 3, 4, 27, 63]
[1, 2, 8, 3, 2, 8, 26, 1, 3, 3, 4, 27, 63]
[1, 2, 8, 3, 2, 8, 1, 26, 3, 3, 4, 27, 63]
[1, 2, 8, 3, 2, 8, 1, 3, 26, 3, 4, 27, 63]
[1, 2, 8, 3, 2, 8, 1, 3, 3, 26, 4, 27, 63]
[1, 2, 8, 3, 2, 8, 1, 3, 3, 4, 26, 27, 63]
[1, 2, 8, 3, 2, 8, 1, 3, 3, 4, 26, 27, 63]
[1, 2, 8, 3, 2, 8, 1, 3, 3, 4, 26, 27, 63]
[1, 2, 3, 8, 2, 8, 1, 3, 3, 4, 26, 27, 63]
[1, 2, 3, 2, 8, 8, 1, 3, 3, 4, 26, 27, 63]
[1, 2, 3, 2, 8, 8, 1, 3, 3, 4, 26, 27, 63]
[1, 2, 3, 2, 8, 1, 8, 3, 3, 4, 26, 27, 63]
[1, 2, 3, 2, 8, 1, 3, 8, 3, 4, 26, 27, 63]
[1, 2, 3, 2, 8, 1, 3, 3, 8, 4, 26, 27, 63]
[1, 2, 3, 2, 8, 1, 3, 3, 4, 8, 26, 27, 63]
[1, 2, 3, 2, 8, 1, 3, 3, 4, 8, 26, 27, 63]
[1, 2, 3, 2, 8, 1, 3, 3, 4, 8, 26, 27, 63]
[1, 2, 2, 3, 8, 1, 3, 3, 4, 8, 26, 27, 63]
[1, 2, 2, 3, 8, 1, 3, 3, 4, 8, 26, 27, 63]
[1, 2, 2, 3, 1, 8, 3, 3, 4, 8, 26, 27, 63]
[1, 2, 2, 3, 1, 3, 8, 3, 4, 8, 26, 27, 63]
[1, 2, 2, 3, 1, 3, 3, 8, 4, 8, 26, 27, 63]
[1, 2, 2, 3, 1, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 2, 2, 3, 1, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 2, 2, 3, 1, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 2, 2, 3, 1, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 2, 2, 1, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 2, 2, 1, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 2, 2, 1, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 2, 2, 1, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 2, 2, 1, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 2, 2, 1, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 2, 1, 2, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 2, 1, 2, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 2, 1, 2, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 2, 1, 2, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 2, 1, 2, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 1, 2, 2, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 1, 2, 2, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 1, 2, 2, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 1, 2, 2, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 1, 2, 2, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 1, 2, 2, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 1, 2, 2, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 1, 2, 2, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 1, 2, 2, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 1, 2, 2, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 1, 2, 2, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 1, 2, 2, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 1, 2, 2, 3, 3, 3, 4, 8, 8, 26, 27, 63]
[1, 1, 2, 2, 3, 3, 3, 4, 8, 8, 26, 27, 63]

Example algorithm - IKEA furniture assembly

Now, let's complicate things a bit.

Given a list of pieces, each with information about what tool to use, and needed supplies like screws, how will you do it step by step?

Simple description

We can just take a new piece, get the tool, get the supplies, and do the instruction. Then, take the next one.

How to model this information?

Now, imagine that you need to explain this to the computer.

- Take a new piece

From where? We need a thing with all pieces. IKEA instructions tell you to do things in a sequence, so let's try a list. We need a list with all pieces.

- Take the required tool

How do we know which one? It seems like, for each piece, we need to know this. We need to connect this information. To keep things simple, let's keep this information in a list. So for example:


In [3]:
# Chair leg, screwdriver
# Chair seat, hammer
# Chair leg, screwdriver

- Take the supplies

Seems like a similar task to "mapping" tools. Let's extend the action list:


In [4]:
# Chair leg, screwdriver, 30mm screw
# Char seat, hammer, wooden peg
# Char leg, screwdriver, 30mm screw
# ...

But what if we no longer have any screws? We should stop the program. It also means, somewhere else in program, we should keep count of screws, and each time one is used, decrease the count by 1.

- Perform instruction

Now, everyone knows this is the hardest part. We need to tell the computer to do something with many elements. "Doing stuff" in programming is performed by instructions, or a sequence of instructions (called a procedure, function, method).

Lets say we define how to use a screw and screwdriver:


In [5]:
def screw_together( furniture_piece, supplies, tool):
    connected_furniture = tool.screw(furniture_piece, supplies)
    return connected_furniture

Now our list looks like this:


In [6]:
# list_of_actions =
# Chair leg, screwdriver, 30mm screw, screw_together( Chair leg, 30mm screw, screwdriver)
# ...

We managed to at least model the behavior. We know the minimum amount of information an algorithm needs to work its way to the end.

One additional thing is, actually it's really hard to write this down. And a single row of our action list has some duplicated information. Maybe we can write it easier:


In [7]:
# screw_together( Chair leg, 30mm screw, screwdriver)
# hammer_together( Chair seat,  wooden peg, hammer)
# screw_together( Chair leg, 30mm screw, screwdriver)
# ...

How does the algorithm look like?

Generally speaking, for each furniture element, perform the instruction using a tool and some supplies. In pseudo code:


In [8]:
for action in list_of_actions:
    action()


---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-8-c41688defd41> in <module>()
----> 1 for action in list_of_actions:
      2     action()

NameError: name 'list_of_actions' is not defined

Simple enough. But in the real world, it's better to hold such information in methods and classes. We will go back to this example when we learn more.

Complexity of calculations and memory usage

Complexity of calculation (time complexity)

This picture presents popular complexities - indicating how much computation is needed for a given input size n of a function.

The steeper upwards the function, the more computationally demanding a calculation is.

Examples:

O(1) - constant time - finding an element of dictionary (hash table) O(log n) - logarithmic - finding an item in a sorted array with binary search O(n log n) - linearithmic - sorting with "heapsort" algorithm, or a fast fourier transform O(n) - linear time - finding an item in an unsorted list O(n^2) - quadratic time - bubble sort algorithm

Complexity of memory (space complexity)

This value describes how much memory a normal physical computer would need to solve a given computational problem.

Lets say we have a function that accepts a number. Then, it will create a new variable in a loop, as many times as the number. This is a linear space complexity function.