Homework – Fighting for breath

The text fighting for breath is a text from Dr. Mark Porter. It was published in BBC Radio Times in 1999 on page 38. The text is easy to understand. But it is not written for a scientific paper. There are no references in this text. Most of the time it uses short sentences which is good. But in the third subsection the first sentences is very long. I think that this sentence could be split up. In the text some vague words are used.  Also in my opinion the use of cursive words is not appropriate for the text as a scientific text. Good is that it just uses abbreviations that are common to use – like UK.

Practice how to describe an algorithm

Linear search in sorted array in prosecode

We consider a sorted array of n elements. To get access to an element at the position i we use a[i]. The input parameter is x. The algorithm goes over all elements in a until he reaches the n-th element or finds the searched element. When x was found, the algorithm returns true, else it returns false.

  1. Initialization:
    1. Fill a with all elements
    2. Sort a
  2. Search:
    1. For each element in a check if a[i] == x
  3. Return:
    1. If the check is, return true
    2. Else return false at the end of the iteration

 

Heapsort in prosecode

With the help of a max-heap you can sort a list l in ascending order. Max-heap is a tree structure, where the element at the root is the biggest one. At the beginning a max-heap is build based of the list. Then the root element gets removed and added to the sorted list. Afterwards the max-heap structure gets restored by putting the new biggest element to the root. Repeat this until the heap is empty.

  1. Initialization:
    1. Fill l with all elements
    2. Build the max-heap base of l
  2. Sort:
    1. Swap(root, l(l.length-1))
    2. length = l-length-1
    3. Restore Heap:
      1. Foreach root in the tree:
      2. Check if root > child1 && root > child2
      3. If not: swap root with child with bigger element.
  3. Continue with 2.a until l.length = 1
  4.  Return:
    1. Sorted l

Asymtptotic cost analysis algorithm in literate code – BubbleSort

Bubblesort is a simple algorithm where an array a with n elements gets sorted. Step by step the algorithm goes over the list until he reaches the end. The biggest element, or the smallest, depending on the order which should be achieved, is at the last position. Repeat this process until the whole array is sorted. In this case we want an ascending order at the end.

The explanation has two parts:

  1. Steps of one iteration
  2. When to stop
  3. Cost analysis

Now we have a more detailed look on the algorithm

  1. Steps of one iteration

Pick the first element i in the array and compare it to the next element a[i+1]. If the element a[i+1] is bigger than i, leave i at its position and continue with the element at a[i+1]. If i is bigger, swap the elements. Afterwards compare the second with the third element in the same way as before. Continue until the last element is reached and do a final swap if needed. Now the biggest element is at the last position.

  1. When to stop

After the first iteration is done, the algorithm starts again at the first element. This time stops at the element at a[n-1], since the last one is already the biggest. When only two elements, the first and the second one, remain, the algorithm does a final check for swapping and finishes afterwards. The elements in a are now in ascending order.

  1. Cost analysis

The algorithm goes through all n elements in one iteration. That means the time effort is O(n). Since the algorithm has one element sorted at the end, it needs to repeated for the complete size of the array, which has an effort of O(n) for the outer loop. Now you have to multiply because both loops are interleaved, so the effort of the whole algorithm is O(n * n) = O(n²).