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.

Another Author Post

This time I won’t focus on one because I have three authors left that I definitely want to recommend. One of them is another guy, that just posts good stuff in the internet and the other two could be called classics.

Let’s start with the internet guy. His nickname is qntm but n the comments he is mostly called Sam. He published a lot of short stories on his page, along with a few longer ones. His stories range from Sci-Fi and Time Travel to Fantasy and Magic and are sometimes strange and weird, but in a good way. His stories are based around laws of physics. Sometimes he invents own systems in which he tries to write a coherent and logical story. Both Ra and Fine Structure, the longest stories Sam has ever written, are like that.
Ra is a strange mixture between Magic and Sci-Fi. Magic was discovered in the 1970s and has developed into a new field of engineering. It is taught at universities and is researched using the scientific method. The protagonist is a promising student of applied magic and has the goal of reaching space without the help of any machines. The story can be found here.

But maybe you want to try a few short stories first? How about sam513, or The Last-But-One Question (weird and cool) or I don’t know, Timmy, being God is a big responsibility (about Hyper-Computation, therefore weird)? How about a medium sized one like The Four-And-A-Halfth Planet (Time Travel) instead? Really, you should check some of those shorter stories out, they are great! 🙂

On to the classics:

H.P. Lovecraft mostly fabricated a special kind of horror. Not the a-axe-murdering-guy-is-hunting-you-kind, but horror on a far larger scale albeit somewhat concealed. A prime example would be The Call of Cthulhu where the protagonist slowly uncovers knowledge surrounding mighty beings through books, notes and studying strange cults around the world. Those beings are called the Old Ones and pose a great threat to mankind, should they ever awaken.
The Music of Eric Zann is a bit shorter, but goes down a similar route. A bit more insanity and less Old Ones in this one, I think.
All of the works by Lovecraft I already read are very dark. I really like his language. His stories give me a creepy feeling like there is something invisible and dangerous looming right next to me. I love that!

I only read two books (1984 and Animal Farm) by Orwell, but those were absolutely great. Both touch on political topics, which I really like.
1984 describes the most depressing dystopia I ever had the displeasure to think about. But as you are already aware I am drawn to dark and dismal stories, so that’s right up my alley.

I think this will be the last post about authors that I write, but I think I covered the most important ones and more or less in the right order. The only other one that I should have written about is Lewis Carroll. You should check out Alice’s Adventures in Wonderland if you did not read it, yet. 🙂