How do I learn algorithms 2

10 algorithms

Last update: January 8th, 2020

In this chapter you will learn to approach problems systematically.

10.1 What is an algorithm?

An algorithm is a type of recipe used to solve a problem. For example, if you want to make coffee, you have to follow certain steps:

  1. Insert filter
  2. Pour in coffee
  3. turn on the machine

Of course, the machine may run out of water - you should include this in your recipe:

  1. Insert filter
  2. Pour in coffee
  3. If there is no water in the machine, then
  4. turn on the machine

The step "Adding coffee" actually consists of many sub-steps that we could list in more detail

  1. Insert filter
  2. Do the following 3 times:
    • Fill the spoon with coffee powder
    • Empty the spoon in the filter
  3. If there is no water in the machine, then
  4. turn on the machine

You can of course immediately see that an algorithm looks something like processing code. There are simple steps that speak to you command (= Function call) in Processing. And there are If statements and grind. Your code solves other problems, such as the problem of moving a ball while making sure the ball bounces off the wall correctly. Or your code solves the problem of calculating an average or animating a solar system.

In the next section we look at how we find algorithms.

10.2 Solving Problems

To solve a problem, the first thing you should do is consider what data you have as a starting point, this is yours Input. Then ask yourself what is the goal of your problem i.e. what is the desired one output?

In the next step you have to Ideas generate how you could solve the problem in a program. they collect Methods (Auxiliary variables, If statements, loops) that you feel could play a role in this.

Finally you write Pseudo code. It's like a program, but formulated quite informally. Only then do you go to them implementation - this is also called implementation.

The last step is Testing. Your program not only has to start, it also has to be able to startall possible inputs provide the correct solution. Of course, you cannot test all of the options, but it is important to try all of them Extreme cases to test as an example. What are extreme cases? If you are writing a search algorithm that needs to find a particular element in an array, then you are testing the case that ...

  • ... the search result is right at the front
  • ... the search result is at the bottom
  • ... the array is empty

We'll look at this using examples:

Example 1: calculate the sum

Task: Find the sum 1 + 2 + ... + N

Step 1 (input): The number N

Step 2 (output): The sum 1 + 2 + ... + N

Step 3 (basic idea): Go through the elements step by step and add the current element to an intermediate result. In the end, the intermediate result is also the final result.

Step 4 (methods) Loop to run through, variable for the intermediate result

Step 5 (pseudo code)

  1. New variable result
  2. Loop with run variable i from 1 to N:
  3. The variable result contains the sum

Step 6 (implementation) Now we can implement the whole thing in code, e.g. by writing a function that receives the N as an input parameter:

int sum (int n) {int result = 0; for (int i = 0; i <= n; i ++) {result = result + i; } return result; }

Step 7 (testing) For testing you should look at the special case N = 0:

void setup () {println (sum (0)); println (sum (5)); } 0 15

So it works. Why does N = 0 actually work?

Another example:

Example 2: Find the smallest element

Task: Find the smallest number in an array

Step 1 (input): Array a (int)

Step 2 (output): A number (int), the smallest in a

Step 3 (basic idea): Go through the elements step by step and check that the current element is the smallest. We have to remember what is currently the smallest. To begin with, the smallest element is simply the first element.

Step 4 (methods) Loop to run through, variable for the currently smallest element

Step 5 (pseudo code)

  1. New int variable smallest = a [0]
  2. Loop with run variable i from 1 to (length from a - 1):
    • If smallest> a [i] then smallest = a [i]
  3. Variable smallest contains the smallest element

Step 6 (implementation) We do this by writing a function that receives the array a as input parameter:

int smallest (int [] a) {int smallest = a [0]; for (int i = 1; i a [i]) {smallest = a [i]; }} return smallest; }

Step 7 (testing) We test our function with a "normal" array and then with an extreme case: an empty array.

void setup () {int [] foo = {10, 30, -20, 100}; println (smallest (foo)); int [] boo = new int [0]; // array with zero elements println (smallest (boo)); }

With the array boo, Processing reports an ArrayIndexOutOfBoundsException, i.e. our code is not completely watertight. We need to catch the case that the array has length 0 (no elements):

int smallest (int [] a) { if (a.length == 0) {return 0; // Jump back if length 0} int smallest = a [0]; for (int i = 1; i a [i]) {smallest = a [i]; }} return smallest; }

Now our test works:

-20 0

The solution is not ideal because whoever is calling the function doesn't know whether the array in the second call above was empty or whether 0 was actually the smallest element of a non-empty array. We won't be able to find a better solution until next semester with the help ofExceptions formulate.

Another "classic":

Example 3: Swap two elements in an array

Task: Swap two elements in an array

Step 1 (input): Array a (int) and two indices x and y of the elements to be swapped

Step 2 (output): The same array a, only that the two elements are swapped

Step 3 (basic idea): Retrieve both values ​​and save them in the other index

Step 4 (methods) We have to temporarily store a value in a variable

Step 5 (pseudo code)

  1. New variable temp
  2. temp = a [x]
  3. a [x] = b [y]
  4. b [y] = temp

Step 6 (implementation) We do this by writing a function that receives the array a as input parameter and manipulates the two indices and then a:

void switchElements (int [] a, int x, int y) {int temp = a [x]; a [x] = a [y]; a [y] = temp; }

What should make you suspicious is that the function has no return value. In fact, you are modifying the array directly within the function, although the array is a parameter after all! We see that in testing.

Step 7 (testing) First a "normal" test:

void setup () {int [] a = {3, 2, 1}; println ("before"); println (a); switchElements (a, 0, 2); // swap println ("after"); println (a); } before [0] 3 [1] 2 [2] 1 after [0] 1 [1] 2 [2] 3

In the case of complex objects such as arrays or objects, it is quite common for the array (or the object) to be changed in the function. Nevertheless, caution is called for when using such functions, because what you enter (array a) will look different afterwards.

We are testing another extreme case: An array with one element in which we swap this one element with itself:

void setup () { int [] a = {1}; println ("before"); println (a); switchElements (a, 0, 0); println ("after"); println (a); }

Works just fine:

before [0] 1 after [0] 1

What if you want to swap elements that are not in the array at all, i.e. one of the indices is outside the array limits?

void setup () {int [] a = {1}; println ("before"); println (a); switchElements (a, 0, 1); println ("after"); println (a); }

Here we get an ArrayIndexOutOfBoundsException again. It is a matter of opinion whether this case has to be caught explicitly. You can think about how you would incorporate the interception.

Finally, a slightly more complex example:

Example 4: Sort

Task: Modify an array so that it is sorted in ascending order

Step 1 (input): Array a (int)

Step 2 (output): Array a (int), sorted in ascending order

Step 3 (basic idea): Loop through all elements of a. Make sure that the current element is not smaller than the one in front of the element. Otherwise swap.

Step 4 (methods) We use one loop to iterate through the elements and a second loop to compare the element with all its ancestors. We also use our "switchElement" function from above.

Step 5 (pseudo code)

  1. Loop with run variable i from 0 to (length from b - 1):
    • // Compare current element a [i] with all preceding ones
      Loop with run variable k from 0 to (i - 1):
      • If a [i] (current element) is smaller than a [k] (a preceding element), then swap the two with the switchElement function
  2. The result is in array a (which has now been changed!)

Step 6 (implementation) We do this by writing a function that receives the array a as an input parameter and no return value Has. Array a is changed directly by the function.

void sortArray (int [] arr) {for (int i = 0; i Step 7 (testing) First a completely "normal" example:

void setup () {int [] a = {2, 3, -1, 1}; println ("before"); println (a); sortArray (a); println ("after"); println (a); } before [0] 2 [1] 3 [2] -1 [3] 1 after [0] -1 [1] 1 [2] 2 [3] 3

What would be "extreme cases"? For example that the array is already sorted ...

// case: array sorted correctly void setup () {int [] a = {1, 2, 3}; println ("before"); println (a); sortArray (a); println ("after"); println (a); } before [0] 1 [1] 2 [2] 3 after [0] 1 [1] 2 [2] 3

... or that it is sorted "the wrong way round" ...

// case: array sorted the wrong way round void setup () {int [] a = {3, 2, 1}; println ("before"); println (a); sortArray (a); println ("after"); println (a); } before [0] 3 [1] 2 [2] 1 after [0] 1 [1] 2 [2] 3

... and of course that it is empty.

// case: the array is empty void setup () {int [] a = new int [0]; println ("before"); println (a); sortArray (a); println ("after"); println (a); } before, afterwards

10.3 recursion

Recursion is a method of implementing algorithms based on the fact that a Function F calling itself repeatedly to solve a problem.

For this to work, function F must Problem pto be solved, split into two parts (P1 and P2). P1 is a trivial problem that is solved directly by F, P2 is similar to P, but "smaller" and is solved by calling up P2 again. Sounds like magic? But it works!

Simple example

Let's look at a simple example: The function should output a number of hash characters specified by parameters on the console. For a loop, you would implement it like this:

void setup () {printHashes (5); } void printHashes(int num) {for (int i = 0; i A recursive version of is based on the following insight: The problem P = "print 5 hash characters" can be divided into the two sub-problems P1 and P2 disassemble:

  • P1: Print 1 hash symbol (trivial)
  • P2: Print 4 hash characters (similar, but "smaller" problem)

The first problem is solved directly with a single print (), for the second problem the same function is called with parameter 4.With this call a hash is printed again and the function is called with parameter 3 ...

printHashes (5) printHashes (4) printHashes (3) ...

Now we have to be careful not to get caught in a kind of endless loop. Because if the parameter is called, we don't want to call it afterwards (and then with negative numbers).

... printHashes (1) printHashes (0) printHashes (-1) printHashes (-2) ...

So we have to Base case intercept that only 1 hash character is printed, because here the problem P is identical to the (trivial) sub-problem P1 and we do not have to call the function again.

In the code, the function looks like this:

void printHashes (int num) { // Solve sub-problem P1 directly print ("#"); // rule out that this is the base case if (num> 1) { // Solve sub-problem P2 by recursion printHashes (num - 1); } }

This example was just an explanation. The solution with the loop is also called a iterative process, then the second solution is this recursive procedures.

In the present case it is certainly iterative This is preferable because recursion has some disadvantage:

  • Error-prone: The unfamiliar type of programming makes it easy to make mistakes, e.g. not catching the base case.
  • Performance: For each function call, a programming language must create certain administrative information so that everything runs correctly after the function has been processed. This means that the iterative method is a lot faster and uses less storage space.

Now you're wondering why bother with recursion in the first place? There are a couple of problems where the recursive method is actually easier to program than the iterative method. Two typical areas are Sort and search, both extremely important tasks in programming, even before the age of Google. The fact that recursion comes into play here also has to do with the fact that Tree structures can be run through very easily and intuitively with recursion and trees are among the most important structuring methods in computer science. For example form Directories, subdirectories and files a tree. Another example is the structure and content of a website (Texts, headings, images, links etc.) structured as a tree (the so-called. document object model or DOM).

Examples with returns

Let's look at a slightly less trivial example. We now want to calculate the sum 1 + 2 + .. + N.

Again we would have a relatively easy one iterative Variant on offer:

void setup () {println (sum to (5)); } // Iterative solution int sum to (int end) {int sum = 0; for (int i = 1; i <= end; i ++) {sum = sum + i; } return sum; } 15

We think again how we can solve the problem P = "Sum of 0 to N" disassemble. We use "0 to N" instead of "1 to N" because the formulation is then a little more elegant.

  • P1: Add N to the subtotal 0 to (N-1)
  • P2: Calculate the partial sum 0 to (N-1)

In contrast to the first example, we have to use the solution of P2 for P1. We also have to think about what the Base case is. We want the recursion to end when we are supposed to calculate the sum to 0 (is 0, of course).

As code:

int sumTo (int end) {// base case if (end == 0) {return 0; } // Solve P2 by recursion: int erg = sum to (end - 1); // Solve P1 with the result of P2 return end + add; } 15

Or written in a more compact way:

int sumTo (int end) {// base case if (end == 0) {return 0; } // Solve P1 and P2 return end + sum to (end - 1); }

For the sake of thoroughness, we should consider what happens if the function is called with 0 or negative values: Here we would run into an infinite regress. So let's catch these cases:

int sumTo (int end) {if (end <= 0) {return 0; } return end + sumTo (end - 1); }

Another (classic) example of recursion is the calculation of the "factorial" of a number. The faculty of 5 becomes 5 too! written and is defined by:

5! = 1 * 2 * 3 * 4 * 5 = 120

For the recursive solution we consider again how we can decompose the problem P, the factorial for a number n:

  • P1: Multiply n by the factorial of n-1
  • P2: Calculate the factorial of n-1

Finally we think about that Base case: The factorial of 0 is defined as 1. The function for n-1 may no longer be called here!

As code:

void setup () {println (fak (5)); } int fak (int n) {// base case if (n == 0) {return 1; } // sub-problems P1 and P2 return n * fak (n - 1); } 120

Again, we should consider what happens if someone passes negative values ​​(factorial is not defined for negative values) so that our function does not go into an infinite regress. We just return a 0 in these cases.

int fak (int n) { // error case if (n <0) {return 0; } // base case if (n == 0) {return 1; } // sub-problems P1 and P2 return n * fak (n - 1); }

Example with array

Recursion is usually used for larger data structures, e.g. for arrays that have to be sorted or in which something is searched.

Let us first look again at a simple task that we could easily solve with a loop - that is, iteratively. We want to add up all the numbers in an int array.

Our two sub-problems are here:

  • P1: Add element 0 to the sum of elements 1 to (N-1)
  • P2: Calculate the sum of the elements 1 to (N-1)

A first draft could look like this:

void setup () {int [] num = {5, 8, 4, 20, 1, -7}; println (sum (num)); } int sum (int [] arr) {if (arr.length == 0) {return 0; } return arr [0] + sum (subset (arr, 1)); }

We apply our function recursively to ever shorter sub-arrays, which we create with. The problem with subset is that a completely new array is always created here (consumes memory) and this new array is filled with the aid of the original array (consumes time). This is a very inefficient solution for larger arrays.

In order to solve the whole thing more efficiently, we not only have to pass the array, but also introduce a parameter that defines the start index.

void setup () {int [] num = {5, 8, 4, 20, 1, -7}; println (sumAb (num, 0)); } int sumAb (int [] arr, int start) {if (start> = arr.length) {return 0; } return arr [start] + sumAb (arr, start + 1); }

If we want, we can now define the function to use:

int sum (int [] arr) {return sumAb (arr, 0); }

Merge sort

A more complex example is sorting using "merge sort". Mergesort is based on the knowledge that the following "Merge" problem can be solved easily and efficiently. This problem becomes Not solved recursively. The recursive part of mergesort comes later.

Merge

Problem: Given two already sorted arrays, create one joined together Array that is also sorted.

Example: Given the sorted arrays a = {2, 5} and b = {3, 10}, create an array of length 4 that contains the elements of a and b in sorted order. In this case {2, 3, 4, 10}.

Why is the problem easy? Because you wander through the two arrays a and b at the same time and move the smaller number into a new array r.

int [] merge (int [] a, int [] b) {int [] r = new int [a.length + b.length]; int ai = 0; int bi = 0; for (int ri = 0; ri = a.length) {r [ri] = b [bi]; bi ++; } else {r [ri] = a [ai]; ai ++; }}} return r; }

Merge sort

Now that we've solved the merge problem, we can use the following strategy to get the Array c of length N to sort. We again differentiate between the "trivial" sub-problem P1 and the recursively solving sub-problem P2:
  • P2: Sort the two halves of c with mergesort (). The halves are each N / 2 in length, which means that the problem is significantly reduced.
  • P1: Merge the two sorted halves with merge ().

The Base case is the case that the array to be sorted has length 1. Then the array is simply returned again.

We can visualize this with the array {4, 3, 2, 1}.

As a code:

int [] mergesort (int [] arr) {// base case if (arr.length <= 1) {return arr; } // P2: Recursive call of mergesort // To do this, divide the array ... int middle = arr.length / 2; int [] arr1 = subset (arr, 0, middle); int [] arr2 = subset (arr, middle); // ... and sort the subarrays int [] sarr1 = mergesort (arr1); int [] sarr2 = mergesort (arr2); // P1: Merge with merge int [] result = merge (sarr1, sarr2); return result; }

Note that an array with an odd number is not a problem either. An array {3, 2, 1} is divided into two "halves" {3} and {2, 1}.

Exercises

10.3 a) Potentiation

Write the function that returns the result of the base ^ exponent operation. The parameters and return value should be of type int.

Solve the problem using recursion andNot iterative (i.e. not with a loop).

Test your code e.g. with

void setup () {println (high (5, 2)); println (high (3, 3)); } 25 27

10.3 b) For loop

Program a for loop for exercise purposes only recursive. More precisely, the goal is to run from e.g. 0 to 4 and always print out the running number. You should also control the step size, i.e. whether you run through the loop in steps of 1, 2 or other.

Write the function with three parameters for the start (e.g. 0), the end (e.g. 5, then you should run to 4) and the step size (e.g. 1).

Test your program with

void setup () {recursiveFor ​​(0, 5, 1); println (); recursiveFor ​​(2, 6, 2); }

You should see:

0 1 2 3 4 2 4

10.3 c) Sierpinski triangle *

Program the representation of a Sierpinski triangle (a fractal) using recursion. With this triangle, white parts are repeatedly "punched out" of a triangle. You can try this out with the example below and you can also read the Wikipedia entry.

All you need is a function with six parameters for the three corner points of the triangle in question. You need one more parameter (I named it) to stop the recusion.

(Interactive field: first click, then with cursor keys)

10.3 d) Find the maximum

Write a function that finds the maximum of an array of numbers.

Solve the problem with a single function that gets an int array and returns the maximum.

Use the Processing function found in the Processing Reference.