Homework: Algorithms

Choose a simple algorithm and a standard description of it, such as linear search in a sorted array. Rewrite the algorithm in prosecode. Repeat the exercise with a more interesting algorithm, such as heapsort. Now choose an algorithm with an asymptotic cost analysis. Rewrite the algorithm as literate code, incorporating the important elements of the analysis into the algorithm’s description.

Linear Search as Prosecode
LinearSearch(x,l) searches for the position of the item x in a ordered list l. For this purpose, every item i in the list is compared with x. If an item equals x, its position is returned. Otherwise the algorithm returns an invalid position, when the end of the list is reached.

1. (Initialize) Set the starting position p <– 0.
2. (Search) For each position p in l:
(a) If i at position p equals the searched element x, return p and stop the search.
(b) Otherwise continue with the next position.
3. (Return) If x was not found in the list, return an invalid position Ω.

Heapsort as Prosecode
HeapSort(l) sorts the elements in a list l.
At first, the list is turned into a max heap. A max-heap is basically a complete binary tree with the additional property that each child node are smaller or equal to their parent nodes. This means that the largest value is always at the root node of the binary tree.
A sorted array is created by repeatedly removing the value from the root of the heap and inserting it into the array. After the removal of the root, the heap needs to be updated.

1. (Initialize) Turn the list l into a max-heap.
2. (Sort) The largest value of the heap is copied to a sorted array. Afterwards, the heap has to be updated so that the next largest value becomes the next root. This is repeated until the heap is empty
(a) Take the root r and add it to the array a
(b) Update the remaining heap
3. (Return) If the heap is empty, return a.

BogoSort as Literate Code
BogoSort(l) sorts the elements of a list l.

The major steps of the algorithm are as follows:
1. Generate a permutation of the items of the list.
2. Check if the elements in the permutation are ordered.
3. Return the list or repeat.

We now examine these steps in detail.
1. Generate a permutation of the items of the list.
Basically, we want to shuffle the order of the items in the list at random.
This step is really important as it allows us to reach a performance of O(n) in the best case scenario. The best case scenario means that the first permutation we chose was the right one.

2. Check if the elements in the permutation are ordered.
Each item i in the list l is compared to the next item n. If i is smaller than n in all cases, the list is sorted.

3. Return the list or repeat.
If the second step yields a positive result, the sorted list l is returned. Otherwise, we start again at the first step.

Cost analysis
As mentioned above, this algorithm has a great best case performance of O(n). However, the average case performance is not as good, because the algorithm is often repeated many times. Therefore, its average case performance is O((n+1)!). The worst case, however, means that no solution can be found. Of course, this should only be the case if bad random number generators are used.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Nearly forgot about this homework.

Leave a Reply

Your email address will not be published. Required fields are marked *