Algorithm in Python for beginner

Course Q&A Machine Learning Specialization MLS Resources
1

Hello,

As a beginner to Python, we need to learn both the syntax (so that we can read and write), and try to write some algorithms (so that we can build useful stuff). To me, syntax without algorithm is boring, so I write this to walk through how we think when coding some simple algorithms. They are, of course, relevant to these courses, because we are going to implement our ideas and our mathematical formula as algorithms.

However, since we can’t share assignment solutions, these demos are not exactly the exercises. They are only going to give you some ideas behind, with the hope that when you work on the real exercises, you will find them “easier to digest”.

Afterall, we can’t claim we know Python if we just know the syntax but have never used it to achieve some goals, can we?

If you find it difficult to read any code below, this means that it is time to learn some syntax. Here are some references to text tutorials.

My approach is to write down my thinking process, with the hope that you will know why I have added the code and how it goes from zero to one.

Have fun and cheers,
Raymond

Table of Content for the walk-through:

Here are some additional websites about algorithms (thinking and design):

A1: Summing over a list of numbers

Given

numbers = [1, 2, 9, 4, 5, 7, 3]

For me, I will add the first number to the second, and then the result of it to the third, and repeat until all the numbers are added. A critical detail here is that, every time we add up two numbers, we need to REMEMBER the addition result, so that we can reuse the result and add it to the next number.

We use the same concept in designing the following algorithm. First, we set up an “accumulator” variable called X that REMEMBERS the intermediate results. Second, and another critical point, we initialize it to 0, not to 1, not to 2, and not to any other numbers but 0. It is because if the list had been an empty one ( numbers = []), then whatX remembers should be 0. That is why we initialize it to 0.

Algorithm progress = 40%

X = 0
numbers = [1, 2, 9, 4, 5, 7, 3]

Then, the syntax to iterate over all the numbers in the list is for number in numbers.

Algorithm progress = 60%

X = 0
numbers = [1, 2, 9, 4, 5, 7, 3]
for number in numbers:

But the above code won’t work because we have not instructed what the computer should do with each number. In mind we know what to do, but we need to code it down:

Algorithm progress = 100%

X = 0
numbers = [1, 2, 9, 4, 5, 7, 3]
for number in numbers:
    X = X + number  #Note that all instructions, that are supposed to be under the for-loop, has to be indented once (= 4 spaces)
print(X)

X + number adds the number to our accumulator X, and then we assign the result back to X so that it remembers the latest result, as promised. Note that all instructions in the loop has to be indented once (which takes 4 spaces). Without proper indentation, the instruction might not be considered to be within the loop, and this is a very common source of problem in assignments.

A2: Computing a summation in a formula (relevant to course 1 and 2 exercises, and based on A1)

In the courses, we are often asked to implement formula like this:
\frac{\lambda}{2m} \sum_{i=0}^{n-1}a_i^2

Moreover, a_i^2 can even be replaced with some very long mathematical expressions. To prepare ourselves for that, at least we need to know how to compute this simple version, because with this foundation, we only need to replace a_i^2 with the other expressions, be it a_i^2 + b_i^2 \times c_i^2 or something even scarier.

We first need to think about how WE will compute this. My steps are to first finish \sum_{i=0}^{n-1}a_i^2 and then multiply that result by \frac{\lambda}{2m}. This kind of intuition is very important as it guides how we code. Let’s do it!

Given

a = [4, 6, 3, 7, 0]

This part \sum_{i=0}^{n-1}a_i^2 can be read as, “take each element of a out, square it, and be summed together.” Again, since we need to iterate over the elements, we need the for-loop:

Algorithm progress: 10%

a = [4, 6, 3, 7, 0]
for i in range(len(a)):

This time we use range to generate a list of indices like the i in \sum_{i=0}^{n-1}a_i^2.

Then the instruction for each i is to use it to index an element in a, and then square it. Therefore:

Algorithm progress: 30%

a = [4, 6, 3, 7, 0]
for i in range(len(a)):
    a[i] ** 2

Since we are summing numbers together, we use the “accumulator” trick demonstrated in section A1 of this post. Here we go:

Algorithm progress: 80%

a = [4, 6, 3, 7, 0]
X = 0
for i in range(len(a)):
    X = X + a[i] ** 2

And finally we complete it with multiplying it with the \frac{\lambda}{2m}:
Algorithm progress: 100%

a = [4, 6, 3, 7, 0]
m = len(a)
lambda = 10

X = 0
for i in range(len(a)):
    X = X + a[i] ** 2

answer = lambda / 2 / m * X

B1. Find the maximum number among a list of numbers

Given

numbers = [3, 5, 18, 4, 3]

We want the computer to find out the maximum number among them. Again, how are WE going to do it? This example is probably too short that, even with a glimpse. we can immediately tell the answer. However, what if we have a list of 1000 numbers? We probably will need to go through the list from left to right, and remember the largest number you have come across so far, won’t we? This is how we are going to implement the algorithm: looking from left to right and remember only the largest number seen so far. Let’s get started!

Algorithm progress: 5%

numbers = [3, 5, 18, 4, 3]
max_number = ?

max_number is our variable for remembering the largest number. Again, it is critical to think carefully how to initialize it. We can’t initialize it to a large number like 100, because it will be larger than the actual largest number of the list. So, what do we do? We initialize it to a very small number, and is reasonably small enough to be smaller than the actual maximum. For example,

Algorithm progress: 20%

numbers = [3, 5, 18, 4, 3]
max_number = -999999999

I know it looks stupid, but it will work. Then we iterate through the list. Again, we use for loop for the job.

Algorithm progress: 40%

numbers = [3, 5, 18, 4, 3]
max_number = -999999999
for i in range(len(numbers)):

So, the loop’s instructions are to compare the remembered max_number with each number from the list, and IF the number is larger than the remembered number, we replace the remembered number with that number.

Algorithm progress: 100%

numbers = [3, 5, 18, 4, 3]
max_number = -999999999
for i in range(len(numbers)):
    if numbers[i] > max_number:
        max_number = numbers[i]
print(max_number)

The last print-line will give us 18 as expected. Note that two indentation levels are used. We shift the if-statement to the first indentation level so that it runs inside the loop for every number. We shift the assignment statement to the second indentation level so that it runs only if it passes the if-checking.

B2. Find the value of x that makes the maximum y (Relevant to course 3, and based on section B1)

Given

X = [ 1, 4, 5, 7 ]
Y = [ 2, 9, 1, 6 ]

These two lists have four numbers each. The objective is to find the value in X that is corresponding to the maximum numbers among Y. In this example, that value of X is 4, because it corresponds to 9.

The idea is very similar to B1, except that this time we have two numbers to remember:

  1. the maximum value of Y, and
  2. the corresponding value of X.

If we copy the work from section B1, and make some changes to the variable names:

Algorithm progress: 70%

X = [ 1, 4, 5, 7 ]
Y = [ 2, 9, 1, 6 ]

max_Y = -999999999
for i in range(len(Y)):
    if Y[i] > max_Y:
        max_Y= Y[i]

what we want is to add another variable (called max_X) to remember the value of X that corresponds to the maximum value of Y

Algorithm progress: 80%

X = [ 1, 4, 5, 7 ]
Y = [ 2, 9, 1, 6 ]

max_X = 0
max_Y = -999999999
for i in range(len(Y)):
    if Y[i] > max_Y:
        max_Y= Y[i]

This time, the initial value of X doesn’t matter at all because we don’t compare it with another number. My natural choice is to initialize it to 0. Now we only need to add a statement to assign the value to max_X. Where would you add that statement?

Algorithm progress: 100%

X = [ 1, 4, 5, 7 ]
Y = [ 2, 9, 1, 6 ]

max_X = 0
max_Y = -999999999
for i in range(len(Y)):
    if Y[i] > max_Y:
        max_Y= Y[i]
        max_X=X[i]
print(max_X, max_Y)

That’s it! Note that the assignment should only happen when a new maximum Y is found, this is why it has to be under the if-statement and has an indentation level of two. The result is, as expected, (4, 9) .

10 Likes