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

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

# 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

# Student project: Operating system level virtualization (final)

Hi,

here is the final version of my paper:

kuntke_oslv_final

Thank you for reading! 🙂

# Locomotion in Immersive Virtual Environments: final version

You can find the final version of my paper here

# Final version: Active Learning

Tobias and Josi, thank you for your constructive feedback. I tried my best to realize your suggestions and hope you’ll like the result.

The final version can be found here.