algorithms – Data Science, Data Analytics and Machine Learning Consulting in Koblenz Germany

Paul Wagner and Till Speicher won State Competition "Jugend Forscht Hessen" and best Project award using neo4j

Rene — Fri, 16 Mar 2012 11:18:38 +0000

6 months of hard coding and supervising by me are over and end with a huge success! After analyzing 80 GB of Google ngrams data Paul and Till put them to a neo4j graph data base in order to make predictions for fast scentence completion. Today was the award ceremony and the two students from Darmstadt and Saarbrücken (respectivly) won the first place. Additionally the received the “beste schöpferische Arbeit” award. Which is the award for the best project in the entire competition (over all disciplines).
With their technology and the almost finnished android app typing will be revolutionized! While typing a scentence they are able to predict the next word with a recall of 67% creating a huge additional vallue for today’s smartphones.
So stay tuned of the upcomming news and the federal competition on May in Erfurt.
Have a look at their website where you can find the (still) German Documentation. As well as the source code and a demo (which I also include here (use tab completion (-: as in unix bash)
Right now it only works for German Language – since only German data was processed – so try sentences like

“Warum ist die Banane krumm” (where the rare word krumm is correctly predicted due to the relation of the famous question why is the banana curved?
“Das kann ich doch auch” (I am also able to do that)
“geht wirklich nur deutsche Sprache ?” (Is really only German language possible?)

Algorithms exercise: Find mistakes in Wikipedia articles

Rene — Wed, 11 Jan 2012 14:47:20 +0000

Today I started an experiment I created an excercise for coursework in algorithms and data structures that is very unusuale and many people have been criticle if this was a good idea. The idea behind the exercise is that studens should read wikipedia articles to topics related to lectures and find mistakes or suggest things that could be improoved. Thereby I hope that people will do something that many people in science don’t do often enough: Read something critically and carefully and question the things that you have learnt. (more discussions after the exercise)
Read the following wikipedia articles:

Find at least 5 mistakes or passages that could be improved. Write down what is wrong or what could be improved. Give a justification for your statements and write down your suggested new version of this very passage.
To get inspired you can find mistakes by looking at the discussion page of the articles or at the version history. You might also be able to look the same article in versions of other languages!
Here are some example types / things that could possibly be improoved:

pure mistakes
semantics of links
semantics of pictures
articles could explain easy concepts in difficult words
missing cites
missing links to original scientific work
…

Further discussion
I am really excited how many students will try to do this exercise and how well it is accapted and what the quality of the answers will be…
I would also love to receive your feedback, thoughts and comments about this kind of exercise! Mabe you have some ideas that could be extended or you asked students to do similar coursework?

balanced binary search trees exercise for algorithms and data structures class

Rene — Tue, 29 Nov 2011 14:20:40 +0000

I created some exercises regarding binary search trees. This time there is no coding involved. My experience from teaching former classes is that many people have a hard time understanding why trees are usefull and what the dangers of these trees is. Therefor I have created some straight forward exercises that nevertheless involve some work and will hopefully help the students to better understand and internalize the concepts of binary search tress which are in my oppinion one of the most fundamental and important concepts in a class about algorithms and data structures.

Part A: finding elements in a binary search tree – 1 Point

You are given a binary search tree and you know the root element has the value 2. Considering that the path to for finding an element in the tree is unique decide which of the following two lists can be an actual traversal part in order to receive the element 363 from the binary search tree? Why so?

2, 252, 401, 398, 330, 344, 397, 363
2, 252, 397, 398, 330, 344, 401, 363

Part B: Create binary search trees – 1 Point

You are given an empty binary search tree and two lists of the same elements.

10, 20, 5, 15, 2, 7, 23
10, 5, 7, 2, 20, 23, 15

For both lists draw all the trees that are created while inserting one element after the other one.

Part C: skewed binary search trees and traversing trees – 1 Point

Compare the trees from part B to the tree you would get if inserting the numbers in the order of 2, 5, 7, 10, 15, 20, 23
To understand the different tree traversals please give the result of the inorder and preorder traversal applied to the trees from part B and C.

Part D: Balanced binary search trees. Counting Permutations – 2 Point

We realize that trees can have different topologies as soon as the order of the inserted items changes. Since balanced trees are most desired your task is to count how many permutations of our 7 elements will lead to a balanced binary search tree!
To do so it is sufficient to write down all the permutations that will lead to a balanced binary search tree. But you do not have to do this explicitly. It is also ok to write down all classes and cases of permuations and count them.
Compare the number to all permutations of 7 elements (= 7!) and give the probability to end up with a balanced binary search tree when given a random permutation of 7 different elements.

Part E: A closed formular for the probability to create a balanced binary search tree – 2 Extra Points

Your task is to find and prove a formular that states the number of permutations of the natural numbers 1, 2,…, 2^k-1 such that inserting the numbers will create a balanced binary search tree.
Give a closed forumlar for the probability P(k) to end up with a balanced search tree. Give the explicit results for k = 1,…,10