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²).

Style Analysis

The text we should analyze is a printed version of a BBC radio broadcast from 1999. The title is Fighting for breath.

Sentence Structure

The sentences are very long and often extended with examples. In the third paragraph is a sentence with 60 words! It is better to split the sentences in smaller ones. The text has a lot of – and brackets for examples, which would be better of in subclauses.
Each paragraph has a certain topic and a good length.

Style

The author uses short forms with not and verbs like is and does. Additionally he mentioned analogies and insider knowledge like at the end of the third paragraph“[…] in a pub car park in a Cotswold village near my home.” These points aren’t unusual for a radio broadcast since the language is rather casual there. In a scientific text they should be avoided.

There are some italic words in the text but there isn’t a pattern to say, why they are italic. It is better to stick with a standard formatting.

Writing Prompt: Use every word in your text

In last week’s writing prompt we had to write a text with the words: kittens, a half-eaten pizza, telepathy, a radio call-in show, salt crackers, magic, a six-pack of beer and existential angst. Since I ran out of time I decided to finish the story at home. Here it is:

After a hard day at work I came home and wanted to eat this delicious pizza my girlfriend made. 10 minutes ago I started the oven via my smartphone before arriving at home so the pizza should be all done by now. When I entered the kitchen I was shocked. The oven was open and in there was a half-eaten pizza. My kittens sat in front of the oven, staring at me. I asked them: “Did you ate my pizza?” … Of course they didn’t answer. But who else could have done it? While thinking I noticed that the radio was on. There was a radio call-in show going on and people who called could ask for advice or help. I decided to give it a shot a called the radio sender. “Uhm Hello guys. I just came home and somebody at half of my pizza. Can you help me?”. “Oh that sounds like a serious problem. We cannot help you, be we will send someone to you in the next minutes”.  I hang up, went to the living room and sad down on my sofa. Suddenly smoke starts coming out of the middle of the room. The smoke grew in size and some moments later a human appeared. I asked myself how on earth it was possible to do this. Did he use magic? Then he started talking: “Hey dude. I am you from the future and I am here to help. Don’t be scared, I event brought a six-pack of beer and some salt crackers with me.” I could not believe that I was talking to my future self. He looks very similar to myself, he doesn’t seem that much older. “I cannot tell you how old I am. If I do it will create some time travel problem and both of us will vanish.” Did he just used some telepathy tricks to read my mind or something? This dude is talking about vanishing. The existential angst made me tremble.

Analysis of the paper according Zobel’s checklist

Regarding hypotheses and questions

What phenomena or properties are being investigated? Why are they of interest?

Current approaches for measuring text similarities are using distributional hypothesis, which state that words appearing in the same context tend to be similar. On the one Hand those approaches have problems with words which have a similar or a double meaning. On the other hand documents have different lengths and structure which makes it harder to compare them.
There are already solutions which describe the semantic relationship with a semantic graph. This paper presents an approach for efficient knowledge-graph based semantic similarity.

Has the aim of the research been articulated? What are the specific hypotheses and
research questions? Are these elements convincingly connected to each other?

Yes it has, the authors wanted to find a better performing approach then the currently used ones. They also mentioned 3 hypotheses, which aren’t really measurable in my opinion. The hypothesis are connected together at least. The hypothesis are:

  1. The similarity measure provides a significantly higher correlation with human notions of document similarity than comparable measures
  2. Hypothesis 1 also holds for short documents with few annotations
  3. Document similarity can be calculated efficiently compared to other graph-traversal based approaches

To what extent is the work innovative? Is this reflected in the claims?

There are already approaches in use which tackle the problems mentioned in the first paragraph. The authors want to improve the performance of those approaches which they mentioned on different occasions.

 What would disprove the hypothesis? Does it have any improbable consequences?

Since the hypotheses aren’t really measurable they can be fulfilled when their approach is 10 times faster but at the same time they are also fulfilled with an slight increase of 1.0000001. The hypothesis have also be tested on a lot of other approaches, since they claimed, that they outperformed every other approach. However they only tested a selection of other methods in comparison to their solution.

What are the underlying assumptions? Are they sensible?

The performance of current approaches can be improved even further, which is sensible.
It is important to improve distributional measures of heterogeneous documents. This is also sensible since social networks are still rising in popularity and another language style is used there.
The assumption to outperform every other approach is a brave one. Since they cannot cover everything it is not sensible

Has the work been critically questioned? Have you satisfied yourself that it is
sound science?

I would like to see more measurable hypothesis to evaluate how good their approach really is. As expected, the authors choose only a few other approaches for comparison so I cannot be sure whether or not their hypothesis holds for other cases.

 

Regarding evidence and measurement

What forms of evidence are to be used? If it is a model or a simulation, what
demonstrates that the results have practical validity?

An experiment was used as evidence. At first they showed how different settings influences the performance. Afterwards they compared there best setting to related approaches for multiple-sentence documents and single sentences.

How is the evidence to be measured? Are the chosen methods of measurement
objective, appropriate, and reasonable?

For the first part the authors decided to use Transversal Semantic Similarity, Hierarchical Semantic Similarity and Graph-based Semantic Similarity to measure their different approaches. Additionally they ranked the quality with Normalized Discounted Cumulative Gain.
They also measured the Pearson and Spearman correlation and their harmonic mean, which are used for the second part of their evaluation. I cannot judge if the methods are appropriate because I am not knowledgeable in this area.

What are the qualitative aims, and what makes the quantitative measures you have
chosen appropriate to those aims?

The qualitative aim is to perform better than the established methods. How the authors measured was noted in the text above.

What compromises or simplifications are inherent in your choice of measure?
Will the outcomes be predictive?

Despite saying they want to outperform all alternatives, the author selected a few commonly used ones. This step is understandable but should also be specified at the hypothesis.
I was able to predict the outcome because of the general hypothesis and the freedom to select the comparison products.

What is the argument that will link the evidence to the hypothesis?

Our approach outperforms competing approaches in terms of ranking quality and correlation measures.

To what extent will positive results persuasively confirm the hypothesis? Will
negative results disprove it?

The hypothesis is way to general. Every positive result just fulfills the hypothesis. Every negative result disproves it. Simple as that.

What are the likely weaknesses of or limitations to your approach?

The only weakness the authors mentioned was the bottleneck of the retrieval step of semantically expanded documents from a Jena TDB. In my opinion there is also a weakness in the unspecific hypothesis which reduces the quality of the paper.

Abstract for my paper

I heard that it’s quite hard to write an abstract before writing the actual paper. I have to agree, it was quite a challenge.

Here is my version:

Virtual Reality (VR) appears more often in news and grow in publicity. More and More companies try to get a market share with their own VR system. At this point it is needed to have a closer look on common interaction techniques. This paper focuses on the interaction between user and virtual objects. I will present shared techniques and discuss advantages and disadvantages. Furthermore I have a look at specific input hardware, which can be used in combination with VR. These Hardware often has different techniques which might be useful, if more devices adopt them.

 

The Punctuation Game

  • We live in the era of Big Data with storage and transmission capacity measured, not just in terabytes, but in petabytes (where peta- denotes a quadrillion or a thousand trillion). Data collection is constant, and even insidious with every click, and every “like” stored somewhere for something. This book reminds us that data is anything but “raw”; that we shouldn’t think of data as a natural resource but as a cultural, one that needs to be generated, protected, and interpreted. The book’s essays describe eight episodes in the history of data, from the predigital to the digital. Together, they address such issues as the ways, that different kinds of data, and different domains of inquiry, are mutually defining how data are variously “cooked” in the processes of their collection, and use, and conflicts over what can or can’t be “reduced” to data. Contributors discuss the intellectual history of data as a concept, describe early financial modeling and some unusual sources for astronomical data, discover the prehistory of the database in newspaper clippings, and index cards and consider contemporary “dataveillance” of our online habits, as well as the complexity of scientific data curation.
  • During succession, ecosystem development occurs, but in the long term absence of catastrophic disturbance, a decline phase eventually follows. We studied six long term chronosequences in Australia, Sweden, Alaska, Hawaii, and New Zealand; for each, the decline phase was associated with a reduction in tree basal area and an increase in the substrate nitrogen to phosphorus ratio, indicating increasing phosphorus limitation over time. These changes were often associated with reductions in litter decomposition rates, phosphorus release from litter, and biomass and activity of decomposer microbes. Our findings suggest that the maximal biomass phase, reached during succession, cannot be maintained in the long term absence of major disturbance; and that similar patterns of decline occur in forested ecosystems, spanning the tropical temperate and boreal zones.
  • Facebook’s Graph API is an API for accessing objects and connections in Facebook’s social graph. To give some idea of the enormity of the social graph underlying Facebook, it was recently announced that Facebook has 901 million users and the social graph consists of many types beyond just users. Until recently, the Graph API provided data to applications in only a JSON format. In 2011, an effort was undertaken to provide the same data in a semantically enriched RDF format containing Linked Data URIs. This was achieved by implementing a flexible and robust translation of the JSON output to a Turtle output. This paper describes the associated design decisions, the resulting Linked Data for objects in the social graph, and known issues.

Research for “Interaction in virtual worlds”

R. Dörner, W. Broll, P. Grimm, und B. Jung, Hrsg., Virtual und Augmented Reality (VR / AR). Berlin, Heidelberg: Springer Berlin Heidelberg, 2013.

I started my research with the book from Dörner which was recommended in the three dimentional and advanced interaction lecture. This book covers a lot Topics of AR/VR and also gives so literature recommendations. With the book I was able toi limit my topic and also could see, where the reseach topic is in the general AR/VR field.

After the meeting with our writing tutor I noticed, that i have to limit my research field even more and focused on interaction with virtual objects


R. Mine, „Exploiting Proprioception in Virtual-Environment  Interaction“, in Proceedings of the 24th annual conference on Computer graphics and interactive techniques, 1992, S. 19-26

This dissertation is focusing on the using the body as an interaction tool and proposed new http://writersworkshop.katrin-krieger.de/michael/wp-admin/post-new.phpinteraction methods. This work is quite lengthy and I have yet to see, which are important parts for my topic since I have limited amount of space avaible. The user studies will help to see the impact of interaction methods.


Salisbury, D. Brock, T. Massie, N. Swarup, und C. Zilles, „Haptic rendering: Programming touch interaction with virtual objects“, in Proceedings of the 1995 symposium on Interactive 3D graphics, 1995, S. 123–130.

This paper focusses on haptic feedback for the user. This part of interaction is also quite important so that the user gets a better understanding on how his actions influence the virtual objects.


A. Bowman und L. F. Hodges, „An evaluation of techniques for grabbing and manipulating remote objects in immersive virtual environments“, in Proceedings of the 1997 symposium on Interactive 3D graphics, 1997, S. 35–ff.

This paper takes a look onto manipulation techniques for virtual objects. Thoose techniques are presented and compared. I think it’s good to have a look at this one because of the more detailed view in comparision to dörner’s book


A. Wingrave, B. Williamson, P. D. Varcholik, J. Rose, A. Miller, E. Charbonneau, J. Bott, und J. J. L. Jr, „The Wiimote and Beyond: Spatially Convenient Devices for 3D User Interfaces“, IEEE Comput. Graph. Appl., Bd. 30, Nr. 2, S. 71–85, März 2010.

The last paper i choosed for this blog is the one which analyses the wii mote as an imput device. Interaction techniques are often depending on the input devices, so have a look on thees devices might lead to rare and uncommon techniques.


Besides the book mentioned in the beginning, i focuses on works with a high citation count to look for widely accepted work. When doing this research, i tried to cover most areas and see, if i have to do further limitations.

Summary of Warp Drive Research Key to Interstellar Travel

Harold “Sunny” White is doing warp-drive reaserch for the NASA. He tries to create tiny distorions in spacetime with his experiment and if he succeeds, a new drive can be created. Spacetime along the carfts path gets distorted and allows to travel faster than light.

Harold isn’t alone with his work. Other interessted scientist group up in different oganisations, like 100 year starship project, which try to launch an unmanned interstellar mission. Possible targets are increasing every year, when astronomes discover earthlike planets. Thoose planets must have a certain temperature to allow life.

The current problem is the travel speed. Voyager 1, which was launched 1977, has a travel speed of around 38,6 miles per hour and woul still need atleast 70.000 to reach a nearby star with possible habitable planets.

Warp drive isn’t the only possibility to decrease the travel speed. Another, less hypothetical, drive could use fusion power. Fusion Power is already used in atomic bombs and, if controlled properly, can increase the travel speed by multiple thousands. There is still a lot of research left before the technology can be used in spacecraft though.

Besides the drive, there are plenty of other problematic things left to be recognized. One thing is the interstellar dust which can cause heavy damage on the fast moving objects. Another point are the breaks. The ship needs to slow down at its destination, for example with turning the engines around. For slowing down and for damage a protection, more energy is needed.

At the end, a philosophical point was discussed. If there are intelligent aliens out there, why hasn’t they come to earth until know? Doubt in the importance of interstellar travel is also there. Some advocates see the need of it to secure humanities long term survival in case of catastrophes. The only close planet which is somewhat habitable is mars, but there is a huge effort needed for climate engineering. Researching other possibilities might uncover better options.