So long and thanks for all the fish

Some time has passed since our last session. Nevertheless, I want to take the opportunity to write a last post.

We worked on a lot of topics around scientific writing and research, we wrote, we read, we edited. You practised research, writing up, polishing your sentences and paragraphs. In the end, you contributed to a book which I was happy to give you in print in our last session. (By the way, you can find a PDF of our book here.)

You all worked hard on your papers and did a great job editing them according to the reviews. You helped to make the papers of your fellow students better by crafting a review yourself. Thanks for that.

I really enjoyed giving the seminar and working with you. You tremendously contributed to a very relaxed and fun work atmosphere. This gave us the opportunity to ask and answer questions, juggle with ideas, and create fun texts for our writing prompts.

I especially want to thank Norman for his book recommendations he gave in his blog. 🙂 A big thank you goes out again to Josi and Sebastian for their invaluable help with giving feedback to your homework and student project papers.

I hope the tools and techniques I introduced you to will help you with your studies and especially with your master’s thesis.

So long

Katrin

makeitso

Algorithm homework

I finally had the time to finish this homework as well.

 

Linear search

LinearSearch(x,items) searches the items for the given item x . The algorithm starts at the first position in items and iterates over each item while comparing with x. If the one item equals the item x, the algorithm the position of this item, otherwise -1.

  1. Init index variable to zero(0)
  2. Iterate over items and compare the i-th element of items with x
  3. increase the index variable by one and start over with 2
  4. if the i-th item and x are equal return the i otherwise -1

Heapsort

Heapsort(items) is a function to sort a collection of items by using a tree datastructure. The passed items are transformed in a tree-based datastructure with a defined order. Each tree-node is either smaller or equal to his parent node. Next we create a sorted region by removing the largest element in the tree(the root) and inserting this into a array. By repeating this step the sorted array is created and henceforth the tree is shrinked.

  1. create a binary tree from the given array
  2. iterate over the tree and move the root of the tree to a array, the sorted array
  3. update the remaining tree to create a new tree with the root as the largest element
  4. by repeating step you create a sorted array
  5. as soon as the heap is empty we are finished

SelectionSort

SelectionSort(items) is a in-place sort algorithm, which means the items are not moved to different arrays or other structures. It finds the smallest element in the items collection and swaps it with a specified different element.

  1. finding the smallest element in the array
    1. find minimum from start to end
  2. swap the found element with the first element
  3. find the next smallest element in the array
    1. not all elements has to be concerned because the smallest element is on position 0 already so we can start from 1
  4. swap the second smallest element with the second element
  5. repeat step 3 and 4 until we are at the end of the list

In terms of costs this algorithm has a runtime of O(n*n) which makes it inefficient for large lists.

Algorithm

I finally completed the homework of session 9.

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.

You can find my algorithm descriptions here: algorithms

Fighting for Breath

 

The article is about air pollution and how the pollution relates health problems. He states that this relationship is not completely explored and even the air inside houses is affected. After mentioning the political situation, the author closes with an appeal to the reader to reduce pollution. This seems like a logical structure when  talking about this topic. The length of the paragraphs appears to be balanced and the topics are addressed in appropriate depth.

The article seems to be concise, every point is discussed in enough length and no drawn out paragraph catches the eye. The separation of the text is good. In every paragraph, one idea is discussed. The sentences, in the beginning, are short and straightforward but some of the later ones are too long.

The Argumentation and explanations seem reasonable and I can follow them. I personally like his analogies , but sometimes they are not appropriate. References are missing, but that is to be excepted as this  is no  scientific paper.

 

Algorithm descriptions

LinearSearch(v,l) searches the items in list l for the value v. It returns the position of the value or n if the is not in the list, where n is the length of l. The value is compared to every element in the list, denoted by l(i).

  1. (Initialize counter i.) Set i <- 0.
  2. (loop trough every item in l.)
    1. if l(i) = v return i.
    2. i <- i+1.
  3. return n.

InsertionSort(l) sorts the list l and returns it. It loops through each element of the list, finds its location in the sorted list, and inserts it there. The sorted list consists of every visited item.

  1. (Initialize counter i.) Set i <- 1.
  2. (Sort the list.) Loop trough every item in l.
    1. (Initialize counter j.)j is used to search for the correct position to insert l(i). Set j <- i.
    2.  While j is still a valid index ( j > 0 ) and the predecessor of l(j) is greater than l(j) ( l(j-1) > l(j) ).
      1. Swap l(j) and l(j-1).
      2. j <- j-1.
  3. return l.

MergeSort(l) sorts the list l with a divide-and-conquer approach. That means the data is broken down into parts which are processed individually. After that, the preprocessed parts are merged back together again. Overall, the algorithm has a complexity of O(n log n).

Input: unsorted list l.

Output: sorted list l.

 

The major steps of the algorithm are as follows:

  1. Recursive subdivision of the list until each contains 1 item.
  2. Merge sublists until only one is remaining. This is the sorted list.

We now examine these steps in detail.

  1. (Subdivision.)
    1. If a list is empty or has only one element is sorted by definition. In this case, return l.
    2. left, right <- split(l).
      1. This evenly divides all items of l into left and right. This has a constant complexity, since only the midpoint of l needs to be computed.
    3. left <- MergeSort(left)
    4. right <- MergeSort(right)
      1. Recursive calls are used to further subdivide the sublists. This is done until there is until the whole list is divided into sublists of length one. These sublists are then sorted in the Merge function. This has a complexity of  logarithmic since the inputs for the recursive calls are halved at each recursion step.
    5. return Merge(left,right)

function Merge(left, right)

This help function called by the MergeSort function actually does the sorting. The merge has a linear complexity, because each element of the input lists is merged into the result list exactly once.

  1. result <- empty_list.
  2. If none of both lists is empty merge both lists using a zip lock principle. Both left and right are sorted meaning the first element of both is the smallest item in each list. To merge the sublists, the first elements of both sublists are compared and the smaller one is appended to result.
    1. if head(left) <= head(right) then
      1. result <- result + head(left)
      2. left <- tail(left)
    2. else
      1. result <- result + head(right)
      2. right <- tail(right)
    3. head(list) return the first element of list and tail(list) returns every element of list except the first one.
    4. If one of the sublists has any elements has any elements left simply append these elements to result.
    5. return result. This is a sorted list.

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.

Algorithm

With Bubblesort an array can be sorted.

Input: Array a

Output: sorted Array

Variables: n: size of array, i: current position, h

 

Bubblesort(a)

  1. for(n=a.size; n>1; n=n-1)
  2. for(i=0;i<n-1;i=i+1)
  3. If(a[i] > a[i+1])
  4. h=a[i+1]
  5. a[i+1] = a[i]
  6. a[i]=h

 

With Bubblesort an array a can be sorted. It compares two elements e with each other. If they need to be switched this is done. With this algorithm one element is compared with each other element until the comparison is wrong. This is done for all elements.

 

  1. Initialize n with the size of the array and I with 0
  2. for each position n in a and position i in n-1:
  3. Compare value of a[i] with value of a[i+a]
  4. Switch the two elements
    1. Set variable h to value of a[i+1]
    2. Set value of a[i+a] to value of a[i]
    3. Set value of a[i] to h

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. 🙂